Google Code Jam 2014 Round 2 : A. Data Packing

なんとか自分の解ける問題を早解きしてRound3進出できた。
https://code.google.com/codejam/contest/3014486/dashboard#s=p0

問題

N個のデータがあり、各容量はS[i]である。
1枚のCDに、合計容量がXを超えない範囲で1個または2個のデータを格納することができる。
最小何枚のCDがあればすべてのデータを格納できるか。

解法

容量が大きい順にCDに格納していく。
まずCDに1つ目S[i]のデータを格納した場合、残ったデータのうちX-S[i]以下で最大のものを同じCDに詰めていけばよい。
O(X+N)で処理できる。

int N,X,S[701];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	cin>>N>>X;
	
	ZERO(S);
	FOR(i,N) cin>>x,S[x]++;
	int ret=0;
	for(i=X;i>=1;i--) {
		while(S[i]) {
			S[i]--;
			ret++;
			j=X-i;
			for(j=X-i;j>=1;j--) {
				if(S[j]) {
					S[j]--;
					break;
				}
			}
		}
	}
	
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

AとはいえRound2にしては簡単な問題。