Educational DP Contest I - Coins

問題

atcoder.jp

問題概要

コインがN枚あり、i番目(1-index)のコインの表が出る確率がp[i-1]、裏が出る確率が1-p[i-1]である。
N枚のコインを投げたとき、表の個数が裏の個数を上回る確率を求めよ。

解法

dp[i][j] : i番目(1-index)のコインまで投げたときに
(表の枚数)-(裏の枚数)=j
となる確率。
0≦i≦N、-N≦j≦N

これだとjが負の数になることがあるので調整する。

dp[i][N+1+j] : i番目(1-index)のコインまで投げたときに
(裏の枚数)-(表の枚数)=j
となる確率。
0≦i≦N、1≦N+1+j≦2*N+1

dp[i][N+1+j]=dp[i-1][N+j]*(1-p[i-1])+dp[i-1][N+2+j]*p[i-1]

i=0かつj=0の時はdp[i][N+1+j]=1
i=0かつj≠0の時はdp[i][N+1+j]=0

答えは
i=Nかつj<0の時のdp[i][N+1+j]の総和

ソースコード

signed main() {
	int N;
	cin >> N;
	vector<double>p(N);
	rep(i, N) {
		cin >> p[i];
	}
	vector<vector<double>>dp(N + 1, vector<double>(2 * N + 3));
	rep(i, N + 1) {
		for (int j = (-1) * N; j <= N; j++) {
			if (i == 0) {
				if (j == 0) {
					dp[i][N+1+j] = 1;
				}
				else {
					dp[i][N+1+j] = 0;
				}
			}
			else {
				dp[i][N + 1 + j] = dp[i - 1][N + j] * (1 - p[i - 1]) + dp[i - 1][N + 2 + j] * p[i - 1];
			}
		}
	}
	double ans = 0;
	rep(i, N + 1) {
		for (int j = (-1) * N; j <= N; j++) {
			if (i == N && j < 0) {
				ans += dp[i][N + 1 + j];
			}
		}
	}
	cout << fixed << setprecision(20) << ans << endl;
}

コメント

dp[i][j] : i枚目のコインまで投げたとき、表がj枚でる確率
にした方が簡単だった。