kmjp's blog

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

Google Code Jam 2018 Round2 : B. Graceful Chainsaw Jugglers

シンプルな問題設定だけどちょっと考える。
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);
}

まとめ

これはすんなり思いついてよかった。