問題
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(N2)となり満点解答をすることができる。
