LoginSignup
0

More than 3 years have passed since last update.

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

Posted at

yukicoder No.995 → 問題リンク
数学的な解法と行列累乗を使う解法がある。今回は前者。

解法

$p/q$ といちいち言うのは面倒なので、以降は $r=p/q$ とする。
実際の実装でも、$p/q$ をなんらかの変数に入れておくと楽に実装できるだろう。

タピオカは確率 $r$ で移動し、$1-r$ で移動しないので、反復試行の確率により、タピオカが $i$ 回移動する確率は$$P_i:={}_K\mathrm{C}_ir^i(1-r)^{K-i}$$である。

最初からミルクティーに入っていたタピオカが最終的にミルクティーの中にいる確率は、タピオカが偶数回移動した場合なので、$P$ の偶数番目の項の和となる。
数式できちんと書くと$$\displaystyle\sum_{i=0}^{\lfloor K/2 \rfloor}P_{2i}$$である。

ここで、二項定理より$$\bigl((1-r)+r\bigr)^K=\sum_{i=0}^K P_i \tag{1}$$$$\bigl((1-r)-r\bigr)^K=\sum_{i=0}^K (-1)^iP_i\tag{2}$$が成り立つ。
$(1)$ と $(2)$ を足し合わせると、奇数番目の項は+と-で打ち消し合い、偶数番目の項だけが2倍された形で残る。
また、$(1)$ の左辺は $1$ であり、$(2)$ の左辺は $(1-2r)^K$ である。
よって、最初からミルクティーに入っていたタピオカが最終的にミルクティーの中にいる確率は$$\frac12\bigl(1+(1-2r)^K\bigr)$$となる。

最初はキッチンにあったタピオカが最終的にミルクティーの中にいる確率は、タピオカが奇数回移動した場合なので、$P$ の奇数番目の項の和となる。
今度は $(1)$ から $(2)$ を引くと、偶数番目の項は打ち消し合い、奇数番目の項だけが2倍された形で残る。
よって、最初はキッチンにあったタピオカが最終的にミルクティーの中にいる確率は$$\frac12\bigl(1-(1-2r)^K\bigr)$$となる。

期待値は (美味しさ) $\times$ (ミルクティーに入る確率) なので、求める答えは$$(\ b\ の先頭\ M\ 項の和\ )\times\frac12\bigl(1+(1-2r)^K\bigr)+(\ b\ の末尾\ N-M\ 項の和\ )\times\frac12\bigl(1-(1-2r)^K\bigr)$$
となる。$K$ 乗を求めるには繰り返し二乗法を使えばよい。

提出コード

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0