内容別リスト/高速化系/バックトラック - 競技プログラミング用 知識集積所【7/12更新】

---

雑な説明

終了状態から逆再生しながら何かを調べるアルゴリズム。
終了となる状況が限られていたり、最後の状態が指定されているときに用いる。

レベル

ABCのC問題以降。

アルゴリズム内容

例えば、以下のような問題。

ホワイトボードあり、最初は1と書いてある。
以下の2種類の操作を自由に行える。
- 書いてある数をその3倍より1小さい数に書き換える
- 書いてある数をその3倍より1大きい数に書き換える
ホワイトボードに書いてある数を200にできるか？
できるなら、その方法は？

この程度の数なら全パターン試しても間に合うが、ゴールとなる数値が大きいとTLEする。
そこで、終了状態に指定があることに目をつけて、ゴールからの逆算を考える。

最後に200になるわけだが、そのでき方は実は67*3-1=200しかない。
なぜなら、199は3の倍数ではないから。

ではその67はというと、そのでき方は実は22*3+1=67しかない。
なぜなら、68は3の倍数ではないから。

同様に繰り返していくと、

200←67←22←7←2←1

という列ができ、これを1側から見ることで答えは

可能である
方法は、「小さい、大きい、大きい、大きい、小さい」の順にやる

とわかる。

このように、

• 前からやるとデータが枝分かれしまくる
• 後ろからやるとデータが枝分かれしないor少ない
• 終了状態がはっきりしているor候補が少ない

場合には逆再生してバックトラックで解くとうまくいくことがある。

注意点

関連アルゴリズム

動的計画法

再帰的問題、つまり「少し小さい問題の答えがわかっていれば簡単に答えが出る」というタイプの問題を高速に解くアルゴリズム。
具体例の構築にバックトラックを合わせて用いることがよくある。

最長共通部分列

アルゴリズム中で動的計画法とバックトラックを用いる。

最長増加部分列

アルゴリズム中で動的計画法とバックトラックを用いる。