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

はじめに
当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。
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本(初級者向け)
通称蟻本(中級・上級者向け)
-
前の記事
【競プロ精進日記】AtCoder ABC160 2020.04.01
-
次の記事
記事がありません
コメントを書く