ABC#008 C.コイン

その他 参加ログ

問題

N(1<=N<=100)枚の区別でき、裏表のあるコインに正の整数が書かれている。
これを無作為に一列に並べ以下の操作をする。
1.最初にすべて表にする
2.左端から淳に、そのコインより右にあり、かつ、そのコインの倍数であるコインをすべて裏表を変える
最終的に、コインが表を向いているコインの枚数の期待値を求める。

考え方

解説：　http://www.slideshare.net/chokudai/abc008

各コインについて、表となっている確率を求め、期待値は{そのコインが表(=1枚) * 表となる確率}となるので、全部の確率を足しあげればよい。
コインiの表裏が変わる可能性があるのは、コインiの数値より小さい数値をもつ＆約数になっているもの。この個数をS_iとする。
コインiが表となる確率は、S_i+1枚のコインの並び替えで、コインiより左に偶数枚くる確率と同じなので、S_iが奇数なら1/2、偶数ならfloor(S_i+1)/(S_i+1)。

解いた方法

コインiが表となる確率＝コインiが表となる回数/N!、なので、回数を数えてしまった。。。


コインiの左側にコインがl枚、右側にコインがr枚あるとする。
●○●○□○○●●

左側にS_iから偶数枚(0,2,4,...)が来てればよいので、そのようになる組み合わせの数を考えると、
(S_i枚の割り振り方と左右にくるコインの枚数がvalidな時に、)

・左側にくる約数コインm枚の選び方　Comb(S_i, m)
・左側にくる約数でないコインl-m枚の選び方　Comb(l+r-S_i, l-m)
・左側のどこに約数コインを置くかの選び方　Comb(l, m)
・右側のどこに約数コインを置くかの選び方　Comb(r, S_i-m)
・左側にくる約数コインm枚の並べ方　m!
・右側にくる約数コイン(S_i-m)枚の並べ方　(S_i-m)!
・左側にくる約数でないコイン(l-m)枚の並べ方　(l-m)!
・右側にくる約数でないコイン(r-S_i+m)枚の並べ方　(r-S_i+m)!

をすべてかけたものが表となる回数となる。(裏となる回数＝N!-表の回数)
これをコインiの位置についてすべて足し合わせたものが、コインiが表となる回数。

しかし、Nが大きい場合に膨大な数になってしまうので、計算は対数を取って行い、確率値を求めてから元に戻した。