I - Coins

キーワード

解説

$i = 0,1,\dots,N, ~ j = 0,1,\dots,N$ に対して、 $dp_{i,j}$ を次のように定義する。

$i$ 枚目までのコインのうち $j$ 枚が表である確率

$dp_{0,1} = 1, dp_{0,j} = 0$ である。 $i$ 枚目までのコインのうち $j$ 枚が表であるのは、 $i$ 枚目が表かつ $i-1$ 枚目までのうち $j-1$ 枚が表であるか、 $i$ 枚目が裏かつ $i-1$ 枚目までのうち $j$ 枚が表である場合である。

したがって、次のように遷移式を書くことができる。

dp_{i,j} = dp_{i-1,j-1} \times p_i + dp_{i-1,j} \times (1 - p_i)

今回知りたいのは、 $N$ 枚のコインのうち半分以上が表である確率だから、

\sum_{i = \lceil \frac{N}{2} \rceil}^{N} dp_{N,j}

が最終的な答えとなる。

計算量は $O(N^2)$ である。

提出コード

int main() {
    int n; cin >> n;
    vector<double> P(n); rep(i, 0, n) cin >> P[i];
    vector<vector<double>> dp(n+1, vector<double>(n+1, 0));
    dp[0][0] = 1;
    rep(i,1,n+1) dp[i][0] = dp[i-1][0] * (1 - P[i-1]);
    rep(i,1,n+1) rep(j,1,n+1) {
        dp[i][j] = dp[i-1][j-1] * P[i-1] + dp[i-1][j] * (1 - P[i-1]);
    }
    double ans = 0;
    rep(i, (n+1)/2, n+1) ans += dp[n][i];
    cout << fixed << setprecision(10) << ans << endl;
}

H - Grid 1