SRM339 D1M TestBettingStrategy

TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

勝ったら$bet$は$1$，負けたら次の$bet$を$2$倍にする．勝負に勝つ確立は毎回$prob$である．はじめ$initSum$所持していて，$rounds$回行い，$goalSum$以上になる確立を求める．

$$ dp[i][j][k] := iターン目に所持金jでk回負けた時の確立 $$

何回負けたかを持つと$bet$が$(1 << k)$で求まる．後は$bet$が所持金を超えないならば，勝つ，負ける，それぞれの場合に遷移させる．勝った場合は$k$は$0$になる．$goalSum$以上超えた場合は終わりなので，$j$は$goalSum$未満しか見ない．最後には，全てのラウンド内で$goalSum$以上になったものを全て足す．

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

double dp[55][1005][10];

class TestBettingStrategy {
  public:
  double winProbability(int initSum, int goalSum, int rounds, int prob) {
      memset(dp, 0, sizeof(dp));
      dp[0][initSum][0] = 1;

      double p = prob / 100.0;

      rep(i, rounds) {
          rep(j, goalSum) {
              rep(k, 10) {
                  int bet = (1 << k);
                  if(j >= bet) {
                      dp[i+1][j + bet][0] += dp[i][j][k] * p;
                      dp[i+1][j - bet][k+1] += dp[i][j][k] * (1 - p);
                  }
              }
          }
      }

      double ans = 0;
      REP(i, 1, rounds + 1) {
          REP(j, goalSum, 1005) {
              rep(k, 10) {
                  ans += dp[i][j][k];
              }
          }
      }

      return ans;
  }
};