ABC008 コイン
例の表
https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0
所感
最初から俺はさんすうだぞみたいな顏をしてくれれば解ける
問題概要
N枚の区別できるコインが与えられる。各コインには整数が書かれている。以下の操作を行ったとき、表向きになっているコインの期待値を求めよ。
1. すべてのコインを表向きにする。
2. 左端のコインから順に、現在見ているコインよりも右側 (それ自身を除く) にあるコインのうち、現在見ているコインに書かれている整数の倍数が書かれているコインすべての裏表をひっくり返す。
取った方針
期待値の線形性より、各場所にある各コインが表になっている確率を求めてそれの総和を取ればよい。
コインCが場所iにあるときそれが表になる確率をP[C][i] とおくと、それは以下のように求められる。
Cの左に置く約数の選び方 * Cの左に約数を置く場所の場合の数 * Cの左に置く約数の並べ方 * jの右に約数を置く場合の数 * jの右に置く約数の並べ方 * Cの約数ではない数の並べ方
これを求めて総和を取ると解になる。
正しい方針
興味があるのはCとCの約数となる数であることを考えると表になっている確率はより簡単に求められる。
Cとその約数である数のみを並べることを考えると、Cの約数がS個あったとして、左から1...S+1番目にCがある場合の数はすべて等しい。
つまり、Cとその約数のみの列を並べ変えたときCの左に偶数個並ぶ確率を求めればよく、Sが奇数なら1/2、Sが偶数なら(S+2)/(2S+2) となるので、その総和を求めればOK
得られた知見
・期待値の線形性
・興味のあるもの以外を省くと見通しがよくなるパターン
解くのに必要な要素
・期待値の線形性
周辺調査によって得られた知見
特になし
