yukicoder - No.995 タピオカオイシクナーレ

タピオカの動きは独立であるので、それぞれのタピオカ毎に期待値を考えるとよい。


状態が変わる確率(内 \rightarrow 外、外\rightarrow 内) \rightarrow \dfrac{p}{q} \\
状態が変わらない確率(内 \rightarrow 内、外\rightarrow 外) \rightarrow 1 - \dfrac{p}{q}

である。


p_{in} ^ {(k)} = k回目にタピオカがミルクティーに入ってる確率
\\
p_{out} ^ {(k)} = k回目にタピオカがミルクティーの外にある確率

とすると、


\displaystyle p_{in} ^ {(k + 1)} = \left(1 - \frac{p}{q}\right) \ p_{in} ^ {(k)} + \frac{p}{q} \  p_{out} ^ {(k)}
\\
\displaystyle p_{out} ^ {(k + 1)} = \frac{p}{q}  \ p_{in} ^ {(k)} +  \left(1 - \frac{p}{q}\right) \  p_{out} ^ {(k)}

この漸化式を頑張って解いてもいいのだが、よくみると、


\displaystyle
\begin{bmatrix}
p_{in} ^ {(k + 1)} \\ \\
p_{out} ^ {(k + 1)} \\
\end{bmatrix}
=
\begin{bmatrix}
1-\dfrac{p}{q} & \dfrac{p}{q}\\
\dfrac{p}{q} & 1 - \dfrac{p}{q} \\
\end{bmatrix}
\begin{bmatrix}
p_{in} ^ {(k)} \\ \\
p_{out} ^ {(k)} \\
\end{bmatrix}

となってることが分かる。(よく分からない人は、実際に行列の積をとってみると上の漸化式になってると分かると思う)

以上から、


\begin{bmatrix}
p_{in} ^ {(K)} \\ \\
p_{out} ^ {(K)} \\
\end{bmatrix}
=\begin{bmatrix}
1-\dfrac{p}{q} & \dfrac{p}{q}\\
\dfrac{p}{q} & 1 - \dfrac{p}{q} \\
\end{bmatrix}
^{K}
\begin{bmatrix}
p_{in} ^ {(0)} \\ \\
p_{out} ^ {(0)} \\
\end{bmatrix}

となることが分かる。K乗は繰り返し2乗法をすることで O(\log K)ですることができる。


\begin{bmatrix}
p_{in} ^ {(0)} \\ \\
p_{out} ^ {(0)} \\
\end{bmatrix}
=
\begin{bmatrix}
1 \\ \\
0 \\
\end{bmatrix}
\quad (1 \leq i \leq M)
\\ \\
\begin{bmatrix}
p_{in} ^ {(0)} \\ \\
p_{out} ^ {(0)} \\
\end{bmatrix}
=
\begin{bmatrix}
0 \\ \\
1 \\
\end{bmatrix}
\quad (M + 1 \leq i \leq N)

であるので、 K回目に各タピオカが中にいる確率と外にいる確率がわかるだろう。

よって求める期待値 Eは


E = \displaystyle \sum_{i = 1} ^ {N} b_{i} \cdot (i番目のタピオカがK回目にミルクティーの中にいる確率)

提出コード

yukicoder.me