問題
最初にコインをinitSum個持っており、goalSum個まで増やしたい。
rounds回のラウンドがあり、最初のラウンドはコインを１個かけ、勝ったら１個もらえる。
負けるとそのコインは失い、次は２倍のコインをかけなければいけない。
勝った場合は賭けた分のコインはもらえる。
またあらかじめ、勝つ確率はprobになるとわかっている。
goalSum個までコインが増えたら辞めてもよいが、賭ける分のコインが無くなったらゲームを終えなければならない。
このとき、コインがgoalSum個になる確率を求める。
解き方
ｄｐの問題。
状態に「ラウンド数」、「連続で負けた数」、「現在のコインの数」を持ち、
値に「確率」を持たせればよい。
ｄｐの更新のさせ方が最大・最小をとるのか、加算していくのかで途中つまづいた。
また問題文のスコアの条件を正しく読みとれなくつまずいてしまったので、
きちんと問題文を読むことが大事。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
double dp[51][10][1001];
class TestBettingStrategy {
public: double winProbability(int initSum, int goalSum, int rounds, int prob) {
double p=prob/100.0;
memset(dp,0,sizeof(dp));
dp[0][0][initSum]=1.0;
FORE(r,0,rounds){
FORE(j,0,10){
int cost=1<<j;
FORE(k,cost,goalSum){
if(dp[r][j][k]>0){
dp[r+1][0][k+cost]+=dp[r][j][k]*p;
dp[r+1][j+1][k-cost]+=dp[r][j][k]*(1.0-p);
}
}
}
}
double ret=0.0;
FORE(i,0,rounds+1)ret+=dp[i][0][goalSum];
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
double dp[51][10][1001];
class TestBettingStrategy {
public: double winProbability(int initSum, int goalSum, int rounds, int prob) {
double p=prob/100.0;
memset(dp,0,sizeof(dp));
dp[0][0][initSum]=1.0;
FORE(r,0,rounds){
FORE(j,0,10){
int cost=1<<j;
FORE(k,cost,goalSum){
if(dp[r][j][k]>0){
dp[r+1][0][k+cost]+=dp[r][j][k]*p;
dp[r+1][j+1][k-cost]+=dp[r][j][k]*(1.0-p);
}
}
}
}
double ret=0.0;
FORE(i,0,rounds+1)ret+=dp[i][0][goalSum];
return ret;
}
};