なんとか自分の解ける問題を早解きして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にしては簡単な問題。