ABC189 - F - Sugoroku2

https://atcoder.jp/contests/abc189/tasks/abc189_f

概要

マス目が0からNまであるすごろくが存在していて、あなたは1からMまですべての数が等確率で出るルーレットを持っている。あなたは最初にマス0にいて、マス目Nを目指して、以下のように進む。

• マス目$ i $にいるとき、ルーレットで$ j $が出た時にはマス目$ i + j $へ移動する。移動先の$ i + j $が$ N $を超えた場合は、ゴールしたと見なす。

そして、このすごろくにはK個の初めに戻るマス$ {A[i]} $があり、そこにたどり着いてしまうとマス0に戻されてしまう。

この時、ゴールするまでのルーレットの数の期待値はいくつでしょう？

制約：$ 1 \leq N, M \leq 10 ^ 5, 0 \leq K \leq 10, 0 < A[1] < \dots < A[N] < N $

考え方

1. 期待値DPなので、漸化式を立てて後ろから$ dp[0] $まで逆算すればよさそう。
2. 毎回の遷移では連続する$ M $個の$ dp[] $の値を見るので、これをしゃくとりで毎回$ O(1) $で両端の増減をすれば遷移自体も$ O(1) $となり、全体で$ O(N) $となりOK。
3. 初めに戻るマスが厄介。初めに戻るマスのゴールまでの手数の期待値は$ dp[0] $だが、$ dp[0] $こそが今求めようとしてるもの(循環してて、気持ち悪い)
4. しかし、DPで持つ値は単純にスカラー値ではなく、(a$ dp[0] $ + b)のようなベクトル形式で持てば、一元連立方程式を解くことに帰着できる。(今回の場合は漸化式タイプなので掃き出し法せずにそのまま順に代入し続けて最後に方程式を解く)
5. AC

考察

もし初めに戻らないなら

初めに戻るマスが存在しないとき、これは単純な期待値DPとなる。以下のようにDPテーブルを定めて、$ N - 1 $から$ 0 $の順序で計算すればよい。

$$ dp[i] := マスiからゴールまでの手数の期待値 $$

このとき、ゴールを超えてもゴール扱いなので、便宜的にゴールの後ろに$ N + 1, N + 2, \cdots, N + M $までマス目が続いているとして、$ dp[N] $から$ dp[N + M] $まではすべてゼロとなる。(もうすでにゴールに到達してるので、ルーレットを回す必要はない)

この時、遷移式はこのように考えられる。マス目$ i $でのかかる手数のは、「ルーレットで$ j(1 \leq j \leq M) $を出して、マス目$ i + j $に行く」のパターンで網羅できる。 これらのすべての$ j $について、ルーレットの性質上確率は平等なので、$ \frac{1}{M} $だけの確率で各パターンが選ばれる。

これを漸化式にすると、

$$ dp[i] = \frac{1}{M}(dp[i + 1] + \cdots + dp[i + M]) $$

この漸化式を愚直に計算すると、$ O(NM) $の計算量がかかり間に合わない。しかし、$ i $は1ずれたら$ dp[i + 1] + \cdots + dp[i + M] $は$ dp[i] $を新たに足して、$ dp[i + M] $を引けば$ i - 1 $に対する和となる。このようなしゃくとり法な手法を用いることで、最初の$ M $個の加算で$ O(M) $、1回の遷移ごとに2つの数の増減で$ O(1) $となるので、この動的計画法の遷移は$ O(N + M) $で完遂できる。

そして、$ dp[0] $がマス0からゴールまでたどり着くのに必要な手数の期待値となるのだ。

初めに戻るマスの厄介なところ

さきほどは初めに戻るマスが存在しない場合の解法を考え、$ dp[i] $を定めた。ここで、初めに戻るマスでの$ dp[i] $を定めてみよう。

$$ dp[i] = dp[0] $$

初めに戻るので、当然ながらマス0からゴールまでたどり着く手数の期待値$ dp[0] $が$ dp[i] $となる。

しかし、$ dp[N - 1], dp[N - 2], \cdots $と計算していたのは他でもない$ dp[0] $を求めるためであり、これでは循環してしまうのだ。

循環の処理

ここまでは$ dp[0] $は漸化式を計算して最後に機械的に求まる値として考えていた。つまり、最終的には

$$ dp[0] = 漸化式の計算結果 $$

となっていた。しかし、ここで右辺にも$ dp[0] $の項が現れても、移行すれば同様に一元方程式として解けるのだ。

ならば、$ dp[i] $の計算では数値だけでなく、数値＋$ dp[0] $の係数を持たせればよい。

こうすれば、最後の$ dp[0] $の計算の右辺にも$ dp[0] $が出てくるが、それは移項して簡単に求めることができる。

なお、到達不能の処理だが、あらかじめ$ M $個連続して初めに戻るマスがあるのかを見てもよいし、先ほどの$ dp[0] $の式の計算の右辺で$ dp[0] $の係数が1ならば、明らかに恒等式として成り立たないのでそれでも判別できる。(この場合は、係数の差がぴったり0というのは誤差があるので、absが$ 10 ^ {-9} $のEPSより小さいと判別すべき)

計算量は$ O(N + M) $

循環の処理　その2

先ほどはそもそも、二次元ベクトルを持たせるDPをしていたが、最終的な形は見ての通り一次方程式であった。ということは、二次元ベクトルではなく、そもそも$ dp[0] $にかりそめの値を代入して計算し、最後につじつまがあるかを二分探索できる(一次方程式なので、単調性が担保される)。これで解くこともできる(これがメジャーなの...?)

計算量は$ O(T(N + M)) $、$ T $は二分探索の回数

蟻本の類題

期待値DPで、一筋縄にも止まらなくて気持ち悪いと思ってる人向けにおすすめの蟻本の類題がある。

第2版p.257のランダムウォーク

最大10*10のフィールド内で、SからGまで行きたい。人は上下左右に動ける。
ただし、いくつかの壁が存在しており、壁のあるマスや外に出てはいけない。
ランダムウォークなので、次に行けるすべての候補のマス二は等確率で移動する。
SからGに行く手数の期待値は？(確実に行けることは保証される)

グリッド例)
S......
.#####.
...#...
...#...
...#...
......G

この問題では、期待値は一筋縄に求められない。 なので、$ (i, j) $にたどり着く手数の期待値を変数(最大100個)として見て、それを持つ連立方程式として、掃き出し法で解いている。 期待値DPはDPといえど、やはり元は連立方程式であり(DPの形をしてる場合はたまたま繰り返し代入で綺麗に求まるパターン)、そうやって考えると循環的な部分も変数と置いて、それを解くようにするのは自然な考えである。

ACソースコード

C++　解法1で行った。自前でpoly構造体を作り、$ d\ _ zero * dp[0] + val $とDPの値を持たせた。

最後に

これ自力で20分解いたのマジで偉いわ。