Codeforces #437 C. Gotta Go Fast

手こずったけど解けて良かった。
http://codeforces.com/contest/866/problem/C

問題

N個のステージを順にクリアしていくゲームを考える。
各ステージのクリア時間は２通りで、確率P[i]でF[i]かかり、(1-P[i])でS[i]かかる。

クリアにかかった時間がR以下になるようにしたい。
途中、(その後R以下でクリアできる見込みが少ないと判断した場合)時間もクリアしたステージもリセットして最初からやり直すことができる。
最適に行動した場合、クリアまでにかかる時間(リセットした場合のそれまでの時間も含めた時間の総和)の期待値を最小化せよ。

解法

ARC#016 Dが参考になる。
D: 軍艦ゲーム - AtCoder Regular Contest 016 | AtCoder

現在のステージと経過時間に関し、条件達成確率とその場合の期待値を考える。
現在のまま頑張るよりも、リセットした方が期待値が小さいなら戻ることにする。

とはいえリセット時の期待値がそもそも求めたい値なのでこの判断はできない。
そこで、リセット時の期待値を二分探索しよう。
リセット以外に関しては状態遷移がDAGを成すのでDPで計算できる。

二分探索で仮置きした値と実際の計算値が一致する場合にそこが解。

int N,R;
int F[101],S[101];
double P[101];
double dp[52][5250];
double prob[52][5250];


double hoge(double v) {
	int i,j;
	ZERO(dp);
	for(i=R+1;i<=5200;i++) dp[N][i]=v;
	for(int i=N-1;i>=0;i--) {
		FOR(j,5001) {
			dp[i][j]+=(F[i]+dp[i+1][j+F[i]])*P[i];
			dp[i][j]+=(S[i]+dp[i+1][j+S[i]])*(1-P[i]);
			dp[i][j]=min(dp[i][j],v);
		}
	}
	return dp[0][0];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>R;
	double LL=0,RR=1e9;
	FOR(i,N) {
		cin>>F[i]>>S[i]>>P[i];
		LL+=F[i];
		P[i]/=100.0;
	}
	
	FOR(i,R+1) prob[N][i]=1;
	for(i=N-1;i>=0;i--) {
		FOR(j,5001) {
			prob[i][j]+=prob[i+1][j+F[i]]*P[i];
			prob[i][j]+=prob[i+1][j+S[i]]*(1-P[i]);
		}
	}
	
	
	FOR(i,90) {
		double M=(LL+RR)/2;
		if(hoge(M)<M) RR=M;
		else LL=M;
	}
	
	_P("%.12lf\n",(LL+RR)/2.0);
	
	
}

まとめ

ARC#016 Dの解法が印象深かったので、覚えていてよかった。