AtCoder Beginner Contest 146 F - Sugoroku

解法

$M$ 個の連続するゲームオーバーマスがある場合はゴール不可能なので、そうでないことを仮定します。「最小ターン数」と「辞書順最小」、それぞれに注目します。

ゴールするための最小ターン数はDP等で求めることができます（後で具体的に説明します）。そのターン数が $X$ であると求められたとします。このとき、 $X$ ターンでゴールできる辞書順最小の移動パターンはどうやって求めれば良いでしょうか。

辞書順最小の基本は「前から貪欲」です。ここでの「貪欲」とは、条件を満たす（ $X$ ターンでゴールする）ことが可能な範囲で、今考えているターンの移動をなるべく小さくする…ということを前から順番に繰り返していくことを指します。

つまり1ターン目での移動先は、スタートから1ターンで移動可能で、かつ「そこから残り $X-1$ ターンでゴールできる」ようなマスのうち最も近いマスになります。こうやって移動先を決めた後、2手ターン目、3ターン目と同様に移動先を決めていくことで答えを求めることができます。

これが解法のアウトラインです。そしてこの「 $i-1$ ターン目にいるマスから移動可能で、残り $X-i$ ターンでゴールできるマスのうち最もスタートに近いマス」を求めるのにいくつか方法があります。

方法1：DPで全マスについて求める

全てのマス $i$ について、「マス $i$ から最小何ターンでゴールできるか？」をDPで求めます。この値を $dp\lbrack i \rbrack$ とします。

これはゴール地点の値 $dp\lbrack N \rbrack = 0$ を初期条件として後ろから求めていくと良いです。そしてスタート地点の値 $dp\lbrack 0 \rbrack$ がスタートからゴールまでの最小ターン数になります。

このDPの求め方も工夫しようと思えば色々ありますが、考え方として一番シンプルなのは $dp\lbrack i\rbrack$ を

$i$ がゲームオーバーマスなら $dp\lbrack i\rbrack = \infty$
そうでなければ、そこから1ターンで移動可能な $dp\lbrack i+1\rbrack, ..., dp\lbrack i+M\rbrack$ の最小値に1を足したもの

として決めるもので、区間最小値はセグメント木やスライド最小値などで求められます。 $M$ 個の連続するゲームオーバーマスがないという仮定のもとでは、 $dp\lbrack i+1\rbrack, ..., dp\lbrack i+M\rbrack$ の最小値は必ず $\infty$ でない値になります。

これで $dp\lbrack \cdot \rbrack$ の値が全て求められます。欲しかったのは「 $i-1$ ターン目にいるマスから移動可能で、残り $X-i$ ターンでゴールできるマスのうち最もスタートに近いマス」なので、今いるマスから移動可能なマスを順番に見ていって、初めて $dp\lbrack \cdot \rbrack$ の値が減るところに移動する…ということを繰り返していくと、これが求めるべき経路になります。

方法2：逆から見て、ゴールから移動可能な最大距離を移動し続ける

上記の方法で既に解けているのですが、別解を考えてみましょう。

先ほど求めたDPテーブルは、実は以下の性質を満たしています。（スタート側を「左」と表記します）

ゲームオーバーマスを除いて、 $dp\lbrack \cdot \rbrack$ の値は左から見て単調減少であること。
$dp\lbrack \cdot \rbrack$ の値が同じマスは、ゲームオーバーマスを除いて連続した区間になり、その幅は $M$ 以下であること。
$dp\lbrack \cdot \rbrack = x$ である最も左のマスと、 $dp\lbrack \cdot \rbrack = x+1$ である任意のマスとの間の距離は $M$ 以下であり、必ず1ターンで移動できること。

これは移動の向きを逆回しにして、ゴールから幅優先探索のように考えると直感的に理解できます。

f:id:betrue12:20191125221457p:plain

図のように、ゴールからの遷移を考えると $dp\lbrack \cdot \rbrack = 1$ のマスたちは幅 $M$ 以下の区間に連続します。そしてこれらのうち最も左のマスから見て左側の、距離 $M$ 以内にある移動可能マスが全て $dp\lbrack \cdot \rbrack = 2$ になります。これはそのまま帰納法での証明ロジックにもなります。

特に重要なのは3.の「 $dp\lbrack \cdot \rbrack = x$ である最も左側のマスと、 $dp\lbrack \cdot \rbrack = x+1$ である任意のマスとの間は必ず1ターンで移動できる」ことです。この性質が成り立つためには、1ターンに移動可能なマス数が $1$ 以上 $M$ 以下であるという本問題の設定が効いています。短い移動が許されない場合は「進み過ぎたせいでゲームオーバーマスを回避できない」等の状況が起こり得ます。

この性質を発見できれば、全マスについてDPをする必要は必ずしもないことが分かります。欲しいのは「 $i-1$ ターン目にいるマスから移動可能で、残り $X-i$ ターンでゴールできるマスのうち最もスタートに近いマス」でした。ゴールから見て（逆向きに）移動できるマスのうち最も左にあるマスに移動することを繰り返せば、それらは全て「残り $X-i$ ターンでゴールできるマスのうち最もスタートに近いマス」になり、必ずスタート地点まで辿り着くことができます。

これが「後ろから貪欲」と言われている解法の正体です。「辞書順最小＝前から貪欲」の「貪欲」とそもそも指す意味が違うので混乱しがちですね。整理します。

辞書順最小の解を求めるためには、前から順番に「合計ターン数の最小性が崩れない範囲で、一番近い移動先」を選んでいくのが最適である。これが「前から貪欲」の貪欲が指すもので、解法の正当性の大前提である。
この「一番近い移動先」たちを求める方法の1つとして、後ろから順番に「移動できる一番遠い移動先」を選んでいく方法がある。これが「後ろから貪欲」の貪欲が指すもの。
- この方法が成立するためには、1ターンに移動可能なマス数が $1$ 以上 $M$ 以下であるという本問題の設定が効いている。