ABC189 F Sugoroku2
まず, ゴールすることが不可能かどうかは「振り出しに戻る」マスが$ M個以上連続しているかどうかを調べておけばよい.
以後, ゴールすることが可能な場合を考える. まずは「振り出しに戻る」マスがない場合を考えてみる.
$ f_i := マス$ iにいるときにマス$ Nに到達するまでの手数の期待値 とすると, $ f_i = \frac{1}{M}(f_{i+1}+f_{i+2}+...+f_{i+M}) + 1と計算できる. これは逆から$ f_{i+1}+f_{i+2}+...+f_{i+M}を差分更新することによって$ O(N)で処理できる.
「振り出しに戻る」マスがある場合, 次のようにして式を作ることはできる.
・$ f_i = f_0 (マス$ iが「振り出しに戻る」マスの場合)
・$ f_i = \frac{1}{M}(f_{i+1}+f_{i+2}+...+f_{i+M}) + 1 (そうでない場合)
しかしこれでは$ f_0が$ f_iを調べている時点でまだ求まっていないため, 計算できない. そこで$ f_0 = xとおいておく. すると$ f_0はすべて調べた後, $ Ax + Bのような形になっており, $ x = Ax + B, これを解いて$ x = \frac{B}{1-A}となる!
よってこの問題を$ O(N)で解くことができた.