ゆらのふなびと

競プロ, Python, C++

ABC008 C - コイン

競プロ 期待値

期待値の問題って初めてだった。

問題

C: コイン - AtCoder Beginner Contest 008 | AtCoder

問題文

高橋君は裏表が区別できる N 枚のコインを持っている。コインの大きさは異なり、それぞれのコインには 1 つずつ正の整数が書かれている。

これらのコインを無作為に (N! 通りの組み合わせがすべて同じ確率で出てくるように) 一列に並べる。その後、以下の手順を実行する。

すべてのコインを表向きにする。 左端のコインから順に、現在見ているコインよりも右側 (それ自身を除く) にあるコインのうち、現在見ているコインに書かれている整数の倍数が書かれているコインすべての裏表をひっくり返す。 高橋君はこの操作を終了した後に表を向いているコインの枚数の期待値が知りたい。

あなたは高橋くんの代わりに、期待値を計算するプログラムを作成してほしい。

部分点

  • N≦8 を満たすデータセット 1 に正解した場合は、99 点が与えられる。

  • 追加制約のないデータセット 2 に正解した場合は、さらに 1 点が与えられ、合計で 100 点が得られる。

解法

部分点解法

N <= 8 なので、コインの並びは高々8! = 40320。この程度なら、すべての順列について結果をシミュレーションし、表となったコインを数え上げ、最後に全通りの数(N!)で割ればよい。

import itertools

def fact(n):
    if n == 1:
        return 1
    else:
        return fact(n-1)*n

N = input()
coins = []
for i in xrange(N):
    coins.append(input())
ans = 0
for elem in itertools.permutations(coins, N):
    side = [True for _ in xrange(N)]
    for i in xrange(N):
        for j in xrange(i+1, N):
            if elem[j] % elem[i] == 0:
                side[j] = not side[j]
    ans += side.count(True)
print 1.0*ans / fact(N)

pythonの順列機能、初めて使ったけど便利！

満点解法

www.slideshare.net

公式の解説を参考にした。なるほど！

まず前提として、

期待値 = 確率の和

である。そこで、各コインに対して、最終的に表である確率を考え、その和を求めるという方法をとる。

あるコインCが最終的に表を向くか否かは、Cとその約数が書かれたコインSの並びのみに依存する。より具体的にはCの左側にあるSの個数Iに依存し、

  • Cの左側にSが偶数個→Cは表(例:SSSSCSS)
  • Cの左側にSが奇数個→Cは裏(例:SSSCSSS)

となる（例において、SとC以外のコインは省略している）。これはさらに簡単にできる。

  • Cが左から奇数番目→Cは表
  • Cが左から偶数番目→Cは裏

今知りたいのはCが表となる確率、すなわちCが左から奇数番目となる確率である。これはSの偶奇によって決まる。

  • Sが奇数のとき: 1/2
  • Sが偶数のとき: ((S+1)/2)/(S+1) = (S+2)/(2S+2)

よって解法は以下のようになる。

  1. 各コインCについて、その約数となるコインの数Sを求める
  2. 上記の式にしたがって確率を求め、足し合わせる
N = input()
coins = []
for i in xrange(N):
    coins.append(input())
ans = 0
for i in xrange(N):
    S = 0
    for j in xrange(N):
        if j != i and coins[i] % coins[j] == 0:
            S += 1
    if S % 2 != 0:
        ans += 1.0/2
    else:
        ans += 1.0*(S+2)/(2*S+2)
print ans

結構数学的な考察を必要とする問題だった。自分で思いつくのは難しいけど、解説を読んで納得。

「期待値は確率の和」、覚えましたし。