問題
C – コイン
解説を読めば理解はできるけど、自分は思いつけるようになるのだろうか？
順列 99点回答
コインの順列に対して全探索を行います。
Pythonでは、itertools.permutations(iterable, r=None) を使うことで、順列を簡単に求めることができます。
例えば、[2, 4, 8] というコインの順列は、以下のように取り出すことができます。
>>> import itertools
>>> lst_coin = [2, 4, 8]
>>> list(itertools.permutations(lst_coin))
[(2, 4, 8), (2, 8, 4), (4, 2, 8), (4, 8, 2), (8, 2, 4), (8, 4, 2)]コードは下記のようになります。
import itertools
N = int(input())
lst_coin = [int(input()) for _ in range(N)]
permutations_coin = list(itertools.permutations(lst_coin))
ans = 0
count = 0
for perm_coin in permutations_coin:
# heads:=1 tail:=0
lst_heads_tail = [1 for _ in range(N)]
for i in range(N):
for j in range(i+1, N):
if perm_coin[j] % perm_coin[i] == 0:
if lst_heads_tail[j] == 1:
lst_heads_tail[j] = 0
else:
lst_heads_tail[j] = 1
ans += sum(lst_heads_tail)
count += 1
print(ans/count)
期待値 100点回答
それぞれの順列ごとに最終的に表になる枚数を数える、そして足し合わせる、という発想から転換します。
あるコイン\(C\)が最終的に表を向くためには、その左側に\(C\)の約数となるコインが偶数枚置かれている必要があります。
つまり、あるコイン\(C\)とその約数の順列を考えた時、あるコイン\(C\)が奇数番目に置かれる順列が、該当する順列になります。
\(C\) の約数が書かれたコインの枚数を\(S\)とします。
\(S\) 枚のコインの順列は \(S!\) 通りありますが、それぞれの確率は等しいので個別に考える必要はなく、 あるコイン\(C\)が奇数番目に置くことができるのは何通りあるかだけを考えます。
このようなコイン \(C\) の置き方は、\(S\) が奇数であれば\(\frac{S+1}{2}\)通り、 \(S\) が偶数であれば\(\frac{S}{2} + 1\)通り存在します。
また、コイン \(C\) の置き方は全体では \(S+ 1\)通り存在するので、それぞれの確率は、 \(S\) が奇数であれば\(\frac {\frac{S+1}{2}}{ S+ 1 }=\frac{1}{2}\)、 \(S\) が偶数であれば\(\frac{\frac{S}{2} + 1} { S+ 1 }=\frac{S+2}{2S+2} \) となります。
この確率を各コインについて足し合わせることで、答えが求まります。
import itertools
N = int(input())
lst_coin = [int(input()) for _ in range(N)]
p_ans = 0
for i in range(N):
# あるコインCの約数となるコインを求める。
lst_divisor = []
for j in range(N):
if i != j and lst_coin[i]%lst_coin[j]==0:
lst_divisor.append(lst_coin[j])
# 約数となるコインの枚数を求める。
s = len(lst_divisor)
# あるコインCが奇数番目に置かれる確率を求める。
if s%2 == 1:
p = 1/2
else:
p = (s+2) / (2*s + 2)
p_ans += p
print(p_ans)