競技プログラミング用 知識集積所
ABC413E - Reverse 2^i
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
反転のルールが煩雑に見えて、実は「全体を2^b個ずつの区間に分けて、1つの区間内を逆順にする」ということしか言っていない。
しかも、
しかも、
1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1 5 6 7 8 4 3 2 1 5 6 7 8 1 2 3 4
のようにすれば、実は反転を使って前後半のswapができる。
逆に前後半のswapができれば、
1 2 3 4 5 6 7 8 5 6 7 8 1 2 3 4 7 8 5 6 1 2 3 4 8 7 5 6 1 2 3 4 8 7 6 5 1 2 3 4 8 7 6 5 3 4 1 2 8 7 6 5 4 3 1 2 8 7 6 5 4 3 2 1
と反転ができる。
ということは、許可された行為がswapだとして考えても、問題に影響はない。
（操作回数が無限に許されるし、それを答えるわけでもないので）
イメージとして、完全2分木型のモビールがくるくる回る様子が近いかもしれない。
あれも、反転でもswapでも、あまり大した差はない。
（操作回数が無限に許されるし、それを答えるわけでもないので）
イメージとして、完全2分木型のモビールがくるくる回る様子が近いかもしれない。
あれも、反転でもswapでも、あまり大した差はない。
さて、その上で辞書順最小を求める方法を考える。
辞書順最小は、後ろの数字の並びをどれだけ犠牲にしても前の数字を小さくするのが正義、という貪欲法（未作成）が常套手段。
つまり、モビールの各接点において、そこにぶら下がっている中で最小の値が左側に来るようにしておけばよい。
辞書順最小は、後ろの数字の並びをどれだけ犠牲にしても前の数字を小さくするのが正義、という貪欲法（未作成）が常套手段。
つまり、モビールの各接点において、そこにぶら下がっている中で最小の値が左側に来るようにしておけばよい。
これは、やることがほぼマージソートなので、そのマージ部分を「毎回大小比較せずに、先頭だけ見て小さい方を前半に全部並べてしまう」ように改造すればよい。
