問題
https://yukicoder.me/problems/no/1922
解法
として一般性を失いません。
回の操作を行ったとして、値 が 回目の操作で に属したなら 、 に属したなら とします。
操作前の値 の位置を 、 回の操作後の値 の位置を とします。
また、各 に対して、 を 2 進数として解釈した値を とします。
このとき、任意の に対して次が成り立ちます。
- ならば、 の大小関係と の大小関係は一致する
- ならば、 の大小関係と の大小関係は一致する (i.e. 元の順番を保つ)
従って、 を満たす を与える であって、 が最小であるようなものを構築すれば良いです。
これは次のような貪欲法により達成されます。
- とする。
- 各 に対して、
- ならば、 とする。
- ならば、 とする。
実装
https://yukicoder.me/submissions/831860
スマホコーディングなのでインデントがめちゃくちゃです。覚えてたら後で直します。
問題の一般化について
2 個の部分列を取り出して連結する操作ではなく 個の部分列を取り出して連結する操作である場合も、操作を 進数で解釈することで同様に解くことができます。