[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; }
ディスカッション
ピンバック & トラックバック一覧
[…] [AtCoder] ABC 194 D – Journey | ヤマカサの競技プログラミング問題 方針 確率 ( … […]