[AtCoder] ABC078 C – HSI

HSI

https://beta.atcoder.jp/contests/abc078/tasks/arc085_a

解答の式は導出できましたが、僕の導出の仕方は遠回りしていました。

考え方

1回のプログラムの提出にかかる時間は、\( t = 1900M + 100(N – M)\) です。また、ある試行で操作が終了する確率は、

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

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

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

これらを元に \( 1 \) から  \( n \) 回目で操作が終了する時間の総和  \( X_n \) は、

\[ X_n = tp_1 + 2tp_2 + \cdots + ntp_n \]

となります。よって、

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

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

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

上記より、

\[ \begin{eqnarray}
(1- p)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 < q < 1\) なので、\( X_n \) は収束します。よって、

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

となります。

感想

計算としては良くある等比級数の問題だと思いました。久しぶりにこのような計算を行いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする