読者です 読者をやめる 読者になる 読者になる

足跡-sokuseki-

りかの日進月歩の記録

ABC008 C コイン

数学ができないので。
期待値問題は苦手です。

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

問題概要

 N 枚のコインを無作為に一列に並べる。左端から順に、そのコインよりも右側にある、そのコインに書かれた数  C_i の倍数が書かれたコインをすべてひっくり返す。最終的に表を向いている(偶数回反転した)コインの枚数の期待値を求めよ。

制約
 1 \le N \le 100
 1 \le C_i \le 10^9


満点解法

期待値は、起こりうる確率を足し合わせることで求められる。よって、各コインについて、並べ方によって表を向く確率を計算して、それを足し合わせるという方針。

今見ているコインをCとすると、Cをひっくり返すことに関わるコインはCの約数が書かれているコインのみである。よって、Cの約数が書かれているコインの数に注目する。

Cが表を向いている(偶数回ひっくり返えす)とき、Cの左側にはCの約数が書かれたコインが偶数枚ある。
このことから、Cの約数が書かれたコインの数をSとすると、
Cが表を向いている場合の数は

  • Sが奇数のとき  \frac{S+1}{2} 通り
  • Sが偶数のとき  \frac{S}{2}+1 通り

となる。
よって、Cが表を向いている確率は

  • Sが奇数のとき  \frac{ \frac{S+1}{2} }{S+1} = \frac{1}{2}
  • Sが偶数のとき  \frac{ \frac{S}{2} +1 }{S+1} = \frac{S+2}{2S+2}

であるので、これを各コインについて足し合わせればよい。

計算量は  O(N^2)


Submission #1241223 - AtCoder Beginner Contest 008 | AtCoder


感想

数学は苦手。
今回は解説を見たけど、期待値問題を自力で解けるようになりたい。