CODE FESTIVAL 2016 Elimination Tournament Round 2 (Parallel) A - 迷子の高橋君 / Takahashi is Missing!

問題

https://beta.atcoder.jp/contests/cf16-tournament-round2-open/tasks/asaporo_e

数直線上に Aさんと Bさんがいる。Aさんと Bさんの距離は L だけ離れている。Aさんと Bさんはそれぞれ同時に動く。Aさんは 現在地を xとすると x -1, x, x +1のいずれかに動くことができる。Bさんは 現在地を ｘ とすると 確率ｐでｘ－１に、確率１－ｐでｘ＋１に動く。AさんとBさんが同じ位置になるまで Aさんと Bさんは動き続ける。Aさんと Bさんの動きは離散的だとする。すなわち X から X +1に動く時、X +0.5などの値は取っていないとする。A さんは B さんと同じ位置になるように動く。 A さんが最適な動きをしたときの動く回数の期待値はいくらか求めよ。

アプローチ

Aさんと Bさんの距離 L が奇数のとき A さんは必ず一度その場から動かない動きをする必要がある。 なぜなら A さんと B さんそれぞれ両方とも その場から動くとき L の偶奇が保たれるため A さんと B さんが出会う、つまり L=0 になることはないからである。 よって距離 L が 奇数のとき A さんは最初のターンで動かないとしても一般性を失わない。これは A さんが B さん の現在地 から離れる方向に１だけ離れた位置からスタートしたと考えても良い。 L が偶数のときは A さんは B さん との距離をつめる方向に動くのが最適である。 A さんと B さんの距離をL =２R とした時の残りのターン数の期待値を E(R) とする。このときE(R+1)＝ｐE(R-1) + ( 1 - p )E(R) + 1が成り立つ。この式は一般項が求まるのでO(１）で答えが求まる。

Submission #2107181 - CODE FESTIVAL 2016 Elimination Tournament Round 2 (Parallel)