TopCoder SRM 339 Div1 Medium TestBettingStrategy

問題

nドルを賭け、勝つとnドルがもらえ、負けるとそのnドルを失うギャンブルがある。
次のような方針で賭けをする。

• 最初は1ドルを賭ける
• 負けた場合、前のラウンドの倍のお金を賭ける
• 勝った場合、前のラウンドの掛け金にかかわらず1ドルをかける

最初initSumドルのお金を持っていて、roundsラウンド回（途中でやめてもよい）賭けをする。
一回のラウンドで勝つ確率がprob%のとき、お金をgoalSum以上に出来る確率を求めよ。

制約条件

initSum,goalSum≦1000
1≦rounds≦50
0≦prob≦100

方針

動的計画法による。
dp[i][j][k]を、iラウンド目まで賭けをして、現在の持ち金がjであり、今までにk回連続で負けているような確率とする。
kから次のラウンドの掛け金がわかるので、テーブルを更新していくようなDPができる。

ソースコード

double dp[2][12][1001];

class TestBettingStrategy {
	public:
	double winProbability(int initSum, int goalSum, int rounds, int prob) 
	{
		memset(dp[0],0,sizeof(dp[0]));
		dp[0][0][initSum]=1;
		int cur=0, next=1;
		rep(i,rounds){
			memset(dp[next],0,sizeof(dp[next]));
			rep(j,1001)rep(k,11)if(dp[cur][k][j]){
				if(j>=goalSum||j<(1<<k))dp[next][k][j]+=dp[cur][k][j];
				else{
					dp[next][0][min(1000,j+(1<<k))]+=dp[cur][k][j]*prob/100;
					dp[next][k+1][j-(1<<k)]+=dp[cur][k][j]*(1-prob/100.0);
				}
			}
			swap(cur,next);
		}
		double ans=0;
		for(int i=goalSum;i<=1000;i++)rep(j,12)ans+=dp[cur][j][i];
		return ans;
	}
};