kmjp's blog

競技プログラミング参加記です

Zepto Code Rush 2014 : A. Feed with Candy

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種類を交互に食べる、という条件が問題文からわかりにくかった…。