I - Coins(動的計画法⑪)

問題

N 枚のコインがあります。 (N は正の奇数)

コインには 1, 2, …, N と番号が振られています。 

各 i (1 ≦ i ≦ N) について、コイン i を投げると、確率 p_i で表が出て、確率 1 − p_i で裏が出ます。

すべてのコインを投げた時に、表の個数が裏の個数を 上回る確率 を求めてください。

解法・ソースコード

メモ化テーブルを i 枚目までで表が j 回出る確率 で作成します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#--------- 入力例1 ----------
coins = [0.30, 0.60, 0.80]
#--------- 入力例2 ----------
# coins = [0.50]
#--------- 入力例3 ----------
# coins = [0.42, 0.01, 0.42, 0.99, 0.42]
#----------------------------
n = len(coins) # コインの枚数

# memo[i, j] = i枚目までで表がj回出る確率
memo = {}
memo[0, 0] = 1 # 初期値(表が出る確率100%)

for i in range(1, n + 1): # コインi枚目
for j in range(n + 1): # 表がj回でる確率
if j == 0: # 必ず裏になる場合
memo[i, 0] = memo.get((i - 1, 0), 0) * (1 - coins[i - 1])
else: # [1つ左上の確率に表の出る確率をかけた数値]+[1つ上の確率に裏の出る確率をかけた数値]
memo[i, j] = memo.get((i - 1, j - 1), 0) * coins[i - 1] + memo.get((i - 1, j), 0) * (1 - coins[i - 1])

print('【メモ化テーブルの内容】')
for i in range(n + 1):
for j in range(n + 1):
print('{:.02f}'.format(memo.get((i, j), 0)), end=' ')
print()
print()

# 表の個数が裏の個数を上回る確率を合算
print('解:', sum(memo[n, j] for j in range(n//2 + 1, n + 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となります。)