足跡-sokuseki-

りかの日進月歩の記録

技術室奥プログラミングコンテスト #3 E - デフレゲーム

競技プログラミング AtCoder

E - デフレゲーム

問題概要

N 面のサイコロがあり、前に出た面がもう一度出るまでサイコロを振り続ける。
前に出た面がもう一度出るまでの出た目の総和の期待値を求めよ。
1 \le N \le 5 \times 10^5

解法

期待値の線型性より
\displaystyle \sum_{i=1}^N （サイコロを i 回振ったときの目の総和） \times （ i+1 回目で初めて目が重複する確率）
を求めればよいことがわかる。

サイコロを i 回振ったときの目の総和は、サイコロを i 回振ったときの目の総和の期待値を考えると良くて、
サイコロを1回振ったときの目の期待値が \frac{N+1}{2} なので、サイコロを i 回振ったときの目の総和の期待値は \frac{N+1}{2} \times i となる。

また、 i+1 回目で初めて目が重複する確率は、初めの i 回は目が重複せず、 i+1 回目にいままで出た i 個の目のうちどれかが出ればいいので
\frac{N}{N} \times \dots \times \frac{N-i+1}{N} \times \frac{i}{N} = \frac{_{N} P _{i}}{N^i} \times \frac{i}{N}
になる。
よってこれらの積の和が答えとなる。

Submission #4013511 - 技術室奥プログラミングコンテスト #3