ABC008 C問題 コイン

abc008.contest.atcoder.jp  確率が苦手なので解きます。

基本方針

99点解法

 ABC008全体の結果の方でも少し書いたけれど、コインの並び(N!)に対する全探索。こっちはシミュレーション実装なので今回は扱わない。

100点解法

 各コインが表になる確率を計算して、その総和が表になるコインの枚数、という考え方。確率っていうより期待値って言った方が理解しやすい気がします。

具体的な方針

 あるコインCが裏返るか否かは、コインCの左に存在する、額面が約数のコインの枚数dによって決まります。逆に言えば、額面が約数でないコインはいくら左にあろうが右にあろうが、確率に影響がありません。
 これはつまり、コインCが表になるか否かは、dにのみ関連して決まるということです。そこで、dと確率の関連について考えます。
 d枚の約数コインのみが並んでいる状態を考えます。この状態に対してCをどこか、約数コインの間、あるいは端に挿入することを考えます。すると、Cの左に約数コインが偶数枚存在する(すなわちCが表向きになる)確率は、約数dが奇数ならば\frac{\frac{1}{2}(1+d)}{1+d}=\frac{1}{2}、偶数ならば\frac{\frac{d}{2}+1}{1+d}=\frac{d+2}{2d+2}となります。d枚のコインの並び方にはd!通りの並び方がありますが、いずれの場合も確率は等しいので無視して構いません。Cを挿入する処理をしたのち、Cでも約数コインでもないコインを任意の場所に挿入していくことで全パターンを網羅することができますが、この場合もCの向きが変わることはありません。よって、最終的にコインCが表になる確率pは上記の計算のみで判定できます。
 最後に全てのコインについて表になる確率を足していけば答えになります。 

実装

abc008.contest.atcoder.jp

感想

 順序立てて考えてみると実は単純な問題なんだなぁと。見方を変えるだけ(見方を変えられるとは言ってない)だった。