【競プロ精進日記】AtCoder ABC146 F-Sugoroku

2020.04.01
競プロ

1. はじめに
2. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

F

F – Sugoroku
好きです。
ぱっとみ、和がNになるようにDPするのかと思いますが、それでは\(O(NM)\)となり間に合いません。
そこで、双六によりM以下の移動が必ずできることを考えると、連続でM以上のゲームオーバーマスが存在しない限り必ずゴールできます。
どのように移動するのが最短かですが、各マスについて最も遠いマスから移動してくるのが最短です。
なぜなら、移動元の「現在のマスから最も遠いマス」はスタートから最も近いからです。
もし、そのマスに移動できるならばスタートから近ければ近いほど最短で移動できます。
なぜなら、あるマスよりスタートから遠いマスに移動したほうが最短になることはありません（M以下の移動が必ず行えるため）。
ここまでわかれば、各マスiについて、i-mマスからiマスまでの間で到達可能な最小のマスの位置を記録していきます。
ゴールまで記録できれば、ゴールからスタートに戻っていった経路が最短手数でゴールできる経路です。
この経路は最短手数が同じ場合でも必然的に、辞書式順序になります（5 2ではなく2 5を採用する、なぜならゴールから最も遠いマスを記録しているので）。
https://atcoder.jp/contests/abc146/submissions/11401550

競プロerになるための2冊↓
通称TLE本（初級者向け）