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$ 枚以上なら表の方が多くなる。
そのため、表が $0$ 枚、$1$ 枚、$2$ 枚以上となる確率を管理する。

最初は、表が $0$ 枚である確率だけが $1$ である。

{1.0, 0.0, 0.0}

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

{0.70, 0.30, 0.0}

$2$ 枚目のコインでは、表の確率が $0.60$ である。
表が $0$ 枚の確率を求める。
$0.70\times0.40=0.28$ となる。

表が $1$ 枚の確率を求める。
$0.70\times0.60+0.30\times0.40=0.54$ となる。

表が $2$ 枚以上の確率を求める。
$0.30\times0.60=0.18$ となる。

{0.28, 0.54, 0.18}

$3$ 枚目のコインでは、表の確率が $0.80$ である。
表が $0$ 枚の確率を求める。
$0.28\times0.20=0.056$ となる。

表が $1$ 枚の確率を求める。
$0.28\times0.80+0.54\times0.20=0.332$ となる。

表が $2$ 枚以上の確率を求める。
$0.18+0.54\times0.80=0.612$ となる。

{0.056, 0.332, 0.612}

表の方が多くなる確率は $0.612$ なので、答えは $0.612$。

特になし。

特になし。