[AtCoder] ABC 078 C – HSI

2019年5月14日2019年5月15日

問題

方針

\( n \) 回目で操作が終了する確率

ある試行で操作が終了する確率は、

\[ p = \dfrac{1}{2^M}\]

となります。また、ある試行で操作が終了しない確率は、\( q = 1 – p\) となります。\( n \) 回目の試行で操作が終了する確率 \( p_n \) は、

\[ p_n = pq^{n – 1} \]

となります。これは、\(n – 1 \) 回操作が失敗して、\( n \) 回目に操作が成功する確率となります。

\( 1 \) 回目から \( n \) 回目で操作が終了する時間の総和

\( 1 \) 回プログラムを実行するのにかかる時間 \( t \) は、

\[ t = 1900M + 100(N – M) \]

\( m \) 回目で操作が終了するときに掛かる時間は、\( mt\) なので、\( 1 \) から  \( n \) 回目で操作が終了する時間の総和  \( X_n \) は、

\[X_n = tp + 2tpq + \cdots + ntpq^{n – 1} \]

となります。

極限を求める

求める期待値 \( X \) は、

\[ \displaystyle \lim_{ n \to \infty } X_n = X \]

を求めれば良いことが分かります。

\[ \begin{eqnarray}
X_n &=& tp + 2tpq + \cdots + ntpq^{n – 1} \\
qX_n &=& tpq + 2tpq^2 + \cdots (n – 1)tpq^{n – 1} + ntpq^n
\end{eqnarray}  \]

上式より、

\[ \begin{eqnarray}
(1- q)X_n &=& tp(1 + q + \cdots + q^{n – 1}) – ntpq^n \\
X_n &=& tp \dfrac{1 – q^n}{(1 – q)^2} – \dfrac{ntpq^n}{1 – q}
\end{eqnarray}  \]

となります。ここで、 \( 0 \lt q \lt 1\) なので、\( X_n \) は収束します。よって、

\[ X = \dfrac{tp}{(1 – q)^2} = \dfrac{t}{p} = 2^Mt \]

となります。

コード

提出したコード