AtCoder Educational DP Contest T - Permutation
こちらの問題の解法を理解したので書き残す。
…と思ったけど、言葉にできるほどきちんと理解していないことに気付いた。
とりあえず、中途半端な状態だけど書き残すことにする。
順列の位置を横軸、要素の値を縦軸にした折れ線グラフを考える。
たとえば\(\{ 0, 1, 3, 2 \}\)という順列の場合、以下のようなグラフになる。
この順列に<が与えられたときは青い矢印の2か所に、>が与えられたときは赤い矢印の3か所に要素を追加できる。
青い矢印に追加すると\(\{ 0, 1, 3, 2, 4 \}\)、\(\{ 0, 1, 4, 2, 3 \}\)になり、赤い矢印に追加すると\(\{ 0, 1, 4, 3, 2 \}\)、\(\{ 0, 2, 4, 3, 1 \}\)、\(\{ 1, 2, 4, 3, 0 \}\)になる。
…こんな感じだと思うんだけど、やっぱりうまく説明できない。きちんと理解するのが難しい。イメージ的には、順列の長さをひとつずつ増やしていく感じ。\(\{ 0 \}\) → \(\{ 0, 1 \}\)\(\{ 1, 0 \}\) → \(\{ 0, 1, 2 \}\)\(\{ 1, 0, 2 \}\)\(\{ 0, 2, 1 \}\)\(\{ 1, 2, 0 \}\)\(\{ 2, 0, 1 \}\)\(\{ 2, 1, 0 \}\) → ... と増やしていくと最終的に長さ\(N\)の順列が重複なく不足なく全部列挙できて、そこから条件を満たさない遷移をなくす。
たとえば長さ\(2\)の順列に>という条件があれば、\(\{ 0, 1 \}\) → \(\{ 0, 2, 1 \}\)\(\{ 1, 2, 0 \}\)、\(\{ 1, 0 \}\) → \(\{ 2, 1, 0 \}\)という遷移しかすることはなくて、\(\{ 0, 1, 2 \}\)\(\{ 1, 0, 2 \}\)\(\{ 2, 0, 1 \}\)への遷移は条件を満たさないので行わない、みたいな感じ。少しだけ桁DPの「\(N\)を超えるような数字は選ばない」という考え方に似ている。
より一般化すると、次のことがいえると思う。
- すべてを重複なく不足なく列挙するような遷移を考える
- 条件を満たさない遷移をなくす
順列の作り方には他にもあって、たとえば「空の数列\(\{\}\)に、\(0\)から順に任意の位置に要素を追加していく」みたいなのもある。こちらは挿入DPと呼ばれるもので、別の問題ではこちらの遷移を使ったりする。この問題でこちらの方法を適用しようとするとドツボにハマる（ハマった）。
ある遷移でうまくいかなそうであれば別の遷移を考えてみる、というのもありかもしれない。けれど、実際にそれで別の遷移が見つかるかどうかは微妙なところ。
EDPCの問題は残り4問！
