Zepto Code Rushに参加。
ABCを解いたもののかなり手こずってしまい、レートを落とす結果に。
http://codeforces.com/contest/436/problem/A
問題
初期状態ではXのジャンプが可能である。
ここにN個の飴があり、それぞれの種類と高さと量が与えられる。
プレイヤーはジャンプで届く高さの飴を食べることができ、その際飴の量の分ジャンプの高さが増す。
なお、飴は2種類あり、交互に食べなければならない。
最大何個の飴を食べられるか。
解法
出来るだけ多くの飴を食べたいので、食べられる高さのうち最も量が多いものをGreedyに食べればよい。
飴を交互に食べる、という縛りがあるので、1個目の飴を0番と1番の両種類で初めて見て、結果の良い方を選ぶと答え。
int N,X; int T[2001],H[2001],M[2001]; int NN[2]; int vis[2001]; void solve() { int f,i,j,k,l,x,y; cin>>N>>X; FOR(i,N) { cin>>T[i]>>H[i]>>M[i]; } int ma=0; FOR(i,2) { x=0,j=i,y=X; ZERO(vis); while(1) { k=-1; FOR(f,N) if(vis[f]==0 && T[f]==j && H[f]<=y) { if(k==-1 || M[f]>M[k]) k=f; } if(k==-1) break; vis[k]=1; y+=M[k]; j^=1; x++; } ma=max(ma,x); } cout << ma << endl; }
まとめ
2種類を交互に食べる、という条件が問題文からわかりにくかった…。