今年もなんとか突破できた。
https://code.google.com/codejam/contest/5314486/dashboard#s=p0
問題
N組の訪問者がおり、それぞれG[i]人からなる。
1パックPピース入りのチョコレートがある。
訪問者に1ピースずつ与えよう。
その際、一旦パックの封を切ると、その中身を配り切るまで次の封を開けられない。
また、ある組の訪問者にチョコレートをあげ始めるとその組全員にいきわたるまで他の組にチョコレートを上げられない。
チョコレートを与える組の順を任意にできるとき、組で最初にチョコレートをもらう人が、開封直後のピースをもらうケースを最大化したい。
最大何組その条件を満たせるか。
解法
G[i]の具体的な数字は関係なく、結局mod Pした人数のみ関係する。
以下 f(x) := (G[i]%Pがxであるような組の数) とする。
あとはDPでもよいし地道に条件分岐させてもよい。
基本的に、できるだけ少ない組を複数合わせてPの倍数にするのがアプローチとなる。
- P=2の場合
- f(0)となる組にチョコをあげれば、f(0)組条件を満たせる。
- あとはf(1)となる組にチョコをあげていくと、その中で奇数番目の組が条件を満たす。
- P=3の場合
- f(0)となる組にチョコをあげれば、f(0)組条件を満たせる。
- あとはG[i]%P=1の組と2の組をペアにしていくと、2組に1組は条件を満たせる。
- 残るはG[i]%P=1の組と2の組いずれかの種類だけなので、3組に1組は条件を満たせる。
- P=4の場合
- f(0)となる組にチョコをあげれば、f(0)組条件を満たせる。
- G[i]%P=1の組と3の組をペアにしていくと、2組に1組は条件を満たせる。
- また、G[i]%P=2の組2つで1組は条件を満たせる。
- 残るf(2)は0か1である。1の場合、G[i]%P==1またはG[i]%P==3の組を2つ合わせれば、3組で1組は条件を満たせる。
- 残る組のG[i]%Pは1種類しかないのでそれら同士を組み合わせよう。
int N,P; int G[101]; void solve(int _loop) { int f,i,j,k,l,x,y; int num[5]={}; cin>>N>>P; FOR(i,N) { cin>>x; num[x%P]++; } int ret=num[0]; if(P==2) { ret += (num[1]+1)/2; } else if(P==3) { x = min(num[1],num[2]); ret += x; num[1]-=x; num[2]-=x; ret += (num[1]+2)/3; ret += (num[2]+2)/3; } else { x = min(num[1],num[3]); ret += x; num[1]-=x; num[3]-=x; ret += num[2]/2; num[2] %= 2; if(num[2]>0 && num[1]>=2) { ret++; num[1]-=2; num[2]=0; } if(num[2]>0 && num[3]>=2) { ret++; num[3]-=2; num[2]=0; } if(num[2]) { ret++; } else { ret += (num[1]+3)/4; ret += (num[3]+3)/4; } } _P("Case #%d: %d\n",_loop,ret); }
まとめ
むしろ本番DPが思いつかず愚直に場合わけしてしまった。