問題
N 枚のコインがあります。 (N は正の奇数) コインには 1, 2, …, N と番号が振られています。 各 i (1 ≦ i ≦ N) について、コイン i を投げると、確率 p_i で表が出て、確率 1 − p_i で裏が出ます。 すべてのコインを投げた時に、表の個数が裏の個数を 上回る確率 を求めてください。
解法・ソースコード
メモ化テーブルを i 枚目までで表が j 回出る確率 で作成します。
[Google Colaboratory]
1 | #--------- 入力例1 ---------- |
実行結果に表示される【メモ化テーブルの内容】の見方ですが、一番左上から一番右下への確率は、すべてのコインが表 になる確率です。
一方、一番左上から一番左下への確率は、すべてのコインが裏 になる確率を表します。
[実行結果(入力例1)]
【メモ化テーブルの内容】 1.00 0.00 0.00 0.00 0.70 0.30 0.00 0.00 0.28 0.54 0.18 0.00 0.06 0.33 0.47 0.14 解: 0.612
表の個数が裏の個数を上回るような各ケースの確率を計算すると、次のようになります。
- (コイン1,コイン2,コイン3)=(表,表,表) となる確率は、0.3×0.6×0.8=0.144
- (コイン1,コイン2,コイン3)=(裏,表,表) となる確率は、0.7×0.6×0.8=0.336
- (コイン1,コイン2,コイン3)=(表,裏,表) となる確率は、0.3×0.4×0.8=0.096
- (コイン1,コイン2,コイン3)=(表,表,裏) となる確率は、0.3×0.6×0.2=0.036
よって、表の個数が裏の個数を上回る確率は、0.144 + 0.336 + 0.096 + 0.036 = 0.612 です。
[実行結果(入力例2)]
【メモ化テーブルの内容】 1.00 0.00 0.50 0.50 解: 0.5
表になる確率が0.5(50%)のコインを1枚だけ投げるので、正解は明らかに 0.5(50%) です。
[実行結果(入力例3)]
【メモ化テーブルの内容】 1.00 0.00 0.00 0.00 0.00 0.00 0.58 0.42 0.00 0.00 0.00 0.00 0.57 0.42 0.00 0.00 0.00 0.00 0.33 0.49 0.18 0.00 0.00 0.00 0.00 0.33 0.48 0.18 0.00 0.00 0.00 0.20 0.42 0.31 0.08 0.00 解: 0.3821815872
【メモ化テーブルの内容】で見ると、一番下の段の右半分を合算した 0.3821815872 が解となります。
(【メモ化テーブルの内容】では簡易化するため小数点第2までしか表示していません。端数を含めて計算すると0.3821815872となります。)