[AtCoder] ABC 194 D – Journey

問題

方針

確率 \( p \) が起こるまでの期待値

確率 \( p \) が起こるまでの期待値を \( E \) とします。\( i \) 回目に初めて確率 \( p \) が起こるときの確率は \( (1-p)^{i – 1}p \) なので、

\[ E = \sum_{i=1}^{\infty} i(1-p)^{i – 1}p \]

となります。ここで、\( E_n = p + 2(1-p)p + \cdots + n(1-p)^{n-1}p \) とすると、

\[ E = \lim_{n \to \infty}E_n\]

となります。

\begin{eqnarray}
E_n &=& p + 2(1-p)p + \cdots + n(1-p)^{n-1}p\\
(1-p)E_n &=& (1-p)p + \cdots + (n-1)(1-p)^{n-1}p + n(1-p)^np
\end{eqnarray}

より、

\[ E_n = 1 + (1-p) + \cdots + (1-p)^{n-1} – n(1-p)^n\]

となるので、

\begin{eqnarray}
E_n &=& 1 + (1-p) + \cdots + (1-p)^{n-1} – n(1-p)^n\\
&=& \dfrac{1 + (1-p)^n}{p} – n(1-p)^np
\end{eqnarray}

となります。\( 0 < 1 – p < 1\) より、

\[ \lim_{n \to \infty}E_n = \dfrac{1}{p}\]

となります。

\( i – 1 \) 種類の頂点を選んでから新たらしい頂点を選ぶまでの期待値

\( i – 1 \) 種類の頂点を選んでから新たらしい頂点を選ぶまでの期待値を \( E_i \) とします。すでに頂点 \( 1 \) は選ばれているので、\( E_1 = 0 \) です。\( N \) 個の頂点を選ぶまでの期待値を \( E \) とすると、

\[ E = \sum_{i=2}^{N}E_i\]

となるので、\(E_i \) を求めます。ここで、\( p_i \) を \( i-1 \) 種類の頂点をすでに選んだ状態から、新しい頂点を選ぶ確率とすると、新しい頂点の数は \( N – (i – 1) \) なので、

\[ p_i = \dfrac{N – i + 1 }{N}\]

となります。したがって、

\begin{eqnarray}
E &=& \sum_{i=2}^{N}E_i\\\
&=& \sum_{i=2}^{N}\dfrac{1}{p_i}\\
&=& \sum_{i=2}^{N} \dfrac{N}{N – i + 1}
\end{eqnarray}

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    double e = 0;
    for (int i = 2; i <= N; i++) {
        e += (double) N / (N - i + 1);
    }
    printf("%.9f\n", e);
    return 0;
}