シンプルな問題設定だけどちょっと考える。
https://codejam.withgoogle.com/2018/challenges/0000000000007706/dashboard/00000000000459f3
問題
R個の赤いボールとB個の青いボールを何人かに振り分ける。
その際、以下のように振り分けたい。
- 全員最低1個のボールを持つ。
- 赤青両方のボールの所持数が一致する人はいない。
最大何人にボールを振り分けられるか。
解法
O(R^2*B^2)でもなんと通ってしまうらしいが、もう少し速い方法を紹介。
当然ながら、皆にできるだけ少ないボールを持たせた方が振り分ける人を増やせる。
もし赤ボールr個青ボールb個持つ人がいるとするならば、赤ボールがr個以下で青ボールがb個以下の人がすでに存在するはずである。
よって、この人が存在するにはR≧(1+b)*r*(r+1)/2かつB≧(1+r)*b*(b+1)/2でなければならない。
そのため、r,bの取りうる範囲は実際はO(√RB)個程度と少ない。
あとは残った赤ボール青ボールを状態とし、その状態に対し割り当て済みの人数の最大化をするようなDPを行えばよい。
以下はテストケース毎にDPをしているが、1回だけDPしておいてあとはテストケース毎にテーブル参照するという手もある。
int T,testcase; int R,B; int from[501][501]; void solve(int TC) { int i,j,k,l,r,x,y; string s; cin>>R>>B; ZERO(from); FOR(x,501) FOR(y,501) from[x][y]=-10101; from[R][B]=0; int ma=0; FOR(x,40) FOR(y,40) if(x*(x-1)/2*(y+1)<=R && y*(y-1)/2*(x+1)<=B && x+y>0) { for(i=x;i<=R;i++) for(j=y;j<=B;j++) { from[i-x][j-y]=max(from[i-x][j-y],from[i][j]+1); ma=max(ma,from[i-x][j-y]); } } _P("Case #%d: %d\n",TC, ma); }
まとめ
これはすんなり思いついてよかった。