コインが表になる期待値を計算する

問題

AtCoder Beginner Contest 008 C

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

ソースコード

解説

全ての順列を列挙する計算量はN!となってしまい、満点解答できない。 そのため、それぞれのコインに着目し最終的に表になる確率を算出する。その後それらの確率を足し合わせる事で期待値を計算する。 よって、入力で与えられたコインそれぞれに着目する

それぞれのコインに対して最終的に表になる確率を求める

0 <= i < Nにおいてi番目のコインをCiとする。 このCiが最終的に表になるかを考える。 コインが反転する条件は「Ciの約数がCiより左側に幾つ存在するか」なので、まず、Ciの約数の個数を算出する(int getCountOfDivisors(int num))。また、Ciの約数以外の数字はCiが反転するか否かに関係しないので無視。

「Ciとその約数の順列」におけるCiの位置によりCiの確率を計算

ここで、Ciの約数の数をcountOfDivisorsと置く。 countOfDivisorsにCiを加えたcountOfDivisors + 1の並びの中で、Ciが裏側になるには偶数番目にCiが置かれる時である。 Ciが偶数番目になる確率は、countOfDivisors + 1が奇数か偶数なのかで変わるのでそれぞれ場合分け。

countOfDivisors + 1 => 偶数の場合

偶数番目はピッタリ半分あるので確率は1/2。

countOfDivisors + 1 => 奇数の場合

偶数番目に置ける通りは、(countOfDivisors + 1)から１を引いた数から２で割った分。 元々置ける場所はcountOfDivisors + 1通りなので、 確率は((countOfDivisors + 1 - 1)/2) / countOfDivisors + 1 となる。

これらの処理によってCiが最終的に裏になる確率が求まる。 今回は表の数を期待を求めたいので、表になる確率をPCiと置くと、 PCi = 1 - Ciとなる。(全ての確率から裏が出る確率を引いたもの)

全てのコインが表になる確率を足し合わせる事で期待値を算出

最後に、0 <= i < Nの範囲で PCiの合計を計算することで期待値を求める事ができる。 この場合の計算量はO(N²)となり満点解答をすることができる。