AtCoder ARC #057 : B - 高橋君ゲーム

なんか最近ARCがBから難しい？
http://arc057.contest.atcoder.jp/tasks/arc057_b

問題

N日の各日にA[i]回ずつゲームをする。
ゲームを1回行うと、その結果は勝ち負けのいずれかとなる。
(i-1)日目までの合計勝率よりi日目の合計勝率の方が高い場合、i日目は機嫌が良い。

合計勝利回数がK回となる勝ち方のうち、機嫌が良い日の最大数を求めよ。

解法

dp(x,y) := x日目までに機嫌がいい日がy日あるような勝ち方のうち、勝利回数最小値
とする。解はdp(N,y) ≦ Kとなる最大のyを答えればよい。

K回しか勝利できないのに、なぜ最小値だけ考えればよいかを考えてみる。
仮にdp(N,y)＜Kであるような勝ち方が合ったとする。
後は後ろの日から順に負けた試合のうち(K-dp(N,y))試合を勝ちにすれば、合計K回勝ちに出来る。
また、その場合後ろの日の勝率が増すだけなので、y日よりも機嫌がいい日が増えることはあっても減ることはない。

ただし例外としてsum(A)==Kの場合だけは常時勝率100%で機嫌がいい日は1日にしかならない点に注意。

あとはdp(x,y)を埋める事を考えよう。
dp(x,y)が分かっている状況で、x+1日目の状況がどうなるかを考える。
x日目までにy日機嫌がいいなら、(x+1)日目は全試合負けてもy日機嫌がいいのは変わらないのでdp(x+1,y) = dp(x,y)
一方(x+1)日目に何試合勝てば(x+1)日目が機嫌がよくなり、計(y+1)日機嫌がよくなるかを考えよう。

sum(A[1..x])=Sとする。(x+1)日目にA[x+1]試合中p試合勝利するとすると、なら(x+1)日目は機嫌がいい。
この式を変形するとなら良いので、dp(x+1,y+1) = min(dp(x,y+1), dp(x,y) + dp(x,y)*A[x+1]/S +1)とすればよい。

int N,K;
int A[2020];
ll mi[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(x,2020) FOR(y,2020) mi[x][y]=1<<30;
	
	cin>>N>>K;
	ll sum=0;
	mi[0][0]=0;
	FOR(i,N) {
		cin>>x;
		
		if(i==0) {
			mi[1][1]=1;
			mi[1][0]=0;
		}
		else {
			FOR(j,i+1) if(mi[i][j]<1<<30) {
				//good
				ll y=mi[i][j]*x;
				y=(y/sum)+1;
				if(y<=x) mi[i+1][j+1]=min(mi[i+1][j+1],mi[i][j]+y);
				//same
				mi[i+1][j]=min(mi[i+1][j],mi[i][j]);
			}
		}
		
		sum+=x;
	}
	
	if(sum==0) return _P("0\n");
	if(sum==K) return _P("1\n");
	
	for(i=N;i>=0;i--) if(mi[N][i]<=K) return _P("%d\n",i);
	_P("0\n");
	
}

まとめ

なんとか避けて良かった。