EDPC I - Coins

コイン

考え方

ABCでいうと、D問題級。

「表が半分より多い確率」だけを継承してもしょうがないので、「表が $j$ 枚出る確率」を全部継承する。

コインが $0$ 枚のときは「$0$ 枚の確率は $1$、それ以外は $0$」で初期化する。
その後は $i$ 枚目までで $j$ 枚表が出るには

のどちらか、と考えて $2$ つの確率の和を計算していけばいい。
（全部表や全部裏の場合、片方しか値がないことに注意）

最終的に $n$ 枚での確率を全部出したら、半分より多く表が出る範囲を合計すればいい。
もしくは、dp[(N+1)/2] を「半分以上」をまとめたものに対応させてもよい。

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

入力を受け取る。

n: 3
p: {0.30, 0.60, 0.80}

今回は、表が $2$ 個以上なら表の方が多くなる。
そのため、dp[2] には表が $2$ 個以上になる確率をまとめて入れる。

最初は、表が $0$ 個である確率が $1$ である。

dp: {1.0, 0.0, 0.0}

$1$ 枚目のコインを見る。
表が出る確率は $0.30$、裏が出る確率は $0.70$ である。

dp: {0.70, 0.30, 0.0}

$2$ 枚目のコインを見る。
表が出る確率は $0.60$、裏が出る確率は $0.40$ である。

dp: {0.28, 0.54, 0.18}

$3$ 枚目のコインを見る。
表が出る確率は $0.80$、裏が出る確率は $0.20$ である。

dp: {0.056, 0.332, 0.612}

dp[2] の $0.612$ が答え。

特になし。

特になし。