CODE FESTIVAL 2014 上海 : E - Game

これは割とすんなり解けた。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_e

問題

N個のステージのゲームをクリアしたい。
各ステージは1～3の難易度のいずれかであり、各難易度のステージに対し、１回チャレンジしてクリアできる確率はそれぞれP1,P2,P3である。

1回コインを入れると、下記の通り最大４回までチャレンジできる。

• 初回のチャレンジでクリアできなければ終了。初回のチャレンジでクリアできれば、２回目に挑む。
• ２回目のチャレンジでクリアできなければ終了。２回目のチャレンジでクリアできれば、３回目に挑む。
• ３回目のチャレンジでクリアできなければ終了。３回目のチャレンジで難易度が2か3のステージをクリアできれば、おまけの４回目に挑める。

各難易度のステージの数と、クリア確率が与えられたとき、全ステージをクリアするまでの必要コイン数の期待値を求めよ。

解法

単純に各難易度の残りステージ数と、現在何回目のチャレンジかを持ってメモ化再帰すればよい。
初回チャレンジのみ、クリアまでにかかるコイン数の期待値は確率の逆数であり、２回目以降はコインが不要なことに注意。

int N[3],P[3];
double prob[3];
double memo[101][101][101][4];

double dpdp(int n1,int n2,int n3,int tr) {
	if(memo[n1][n2][n3][tr]>=0) return memo[n1][n2][n3][tr];
	memo[n1][n2][n3][tr]=1e10;
	
	if(tr==0) {
		if(n1>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], 1/prob[0]+dpdp(n1-1,n2,n3,1));
		if(n2>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], 1/prob[1]+dpdp(n1,n2-1,n3,1));
		if(n3>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], 1/prob[2]+dpdp(n1,n2,n3-1,1));
	}
	if(tr==1) {
		if(n1>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[0]*dpdp(n1-1,n2,n3,2)+(1-prob[0])*dpdp(n1,n2,n3,0));
		if(n2>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[1]*dpdp(n1,n2-1,n3,2)+(1-prob[1])*dpdp(n1,n2,n3,0));
		if(n3>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[2]*dpdp(n1,n2,n3-1,2)+(1-prob[2])*dpdp(n1,n2,n3,0));
	}
	if(tr==2) {
		if(n1>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[0]*dpdp(n1-1,n2,n3,0)+(1-prob[0])*dpdp(n1,n2,n3,0));
		if(n2>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[1]*dpdp(n1,n2-1,n3,3)+(1-prob[1])*dpdp(n1,n2,n3,0));
		if(n3>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[2]*dpdp(n1,n2,n3-1,3)+(1-prob[2])*dpdp(n1,n2,n3,0));
	}
	if(tr==3) {
		if(n1>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[0]*dpdp(n1-1,n2,n3,0)+(1-prob[0])*dpdp(n1,n2,n3,0));
		if(n2>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[1]*dpdp(n1,n2-1,n3,0)+(1-prob[1])*dpdp(n1,n2,n3,0));
		if(n3>0) memo[n1][n2][n3][tr]=min(memo[n1][n2][n3][tr], prob[2]*dpdp(n1,n2,n3-1,0)+(1-prob[2])*dpdp(n1,n2,n3,0));
	}
	return memo[n1][n2][n3][tr];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N[0]>>N[1]>>N[2];
	cin>>P[0]>>P[1]>>P[2];
	FOR(x,3) prob[x]=P[x]/100.0;
	FOR(i,101) FOR(j,101) FOR(k,101) FOR(x,4) memo[i][j][k][x]=-1;
	FOR(x,4) memo[0][0][0][x]=0;
	
	_P("%.12lf\n",dpdp(N[0],N[1],N[2],0));
}

まとめ

若干面倒だけど、難しさはないね。