Coins [Educational DP Contest / DP まとめコンテスト I]

https://atcoder.jp/contests/dp/tasks/dp_i

前提知識

• 確率DP

解説

https://atcoder.jp/contests/dp/submissions/3947967

確率DPをする。
dp[i][omote] := i枚のコインを投げて表の枚数がomoteとなる確率
uraを保持しなくてもいいのか？という問題があるが、ura=i-omoteなので保持しなくてもいい。

遷移は表が出る、裏が出るの二択。
あとは、ura＜omoteとなる確率をすべて足せば答え。
数学の「積の法則」「和の法則」がしっかりわかってないと厳しい。

int N; double P[3010];
double dp[3030][3030];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i];
 
    dp[0][0] = 1;
    rep(i, 0, N) rep(omote, 0, N + 1) {
        dp[i + 1][omote] += dp[i][omote] * (1 - P[i]);
        dp[i + 1][omote + 1] += dp[i][omote] * P[i];
    }
 
    double ans = 0;
    rep(omote, 0, N + 1) if (N - omote < omote) ans += dp[N][omote];
    printf("%.10f\n", ans);
}