半分並べ替え

誤っている位置の集合を $M=\{i\mid P_i\ne i\}$ とし、$m=|M|$ とする。

$m=0$ なら答えは $0$ である。

$1\le m\le N$ なら答えは $1$ である。誤っている位置をすべて選び、ちょうど $N$ 個になるまで固定点を追加すれば、1 回の並べ替えですべてを正しい位置にできる。

以下、$m>N$ とする。2 回の並べ替えで選ぶ位置集合を $A,B$ とする。$|A|=|B|=N$ より、

$$|A\cap B|=|\{1,\cdots,2N\}\setminus(A\cup B)|$$

が成り立つ。$A\cup B$ の外側の位置は一度も操作されないので、最初から固定点でなければならない。

固定点が 1 つ以上存在する場合、答えは $2$ である。$m>N$ なので 1 回では不可能であり、1 つの固定点を両方の選択集合の外側に置くことで常に 2 回以内に整列できる。

次に固定点が 1 つもない場合を考える。このとき $A\cup B$ の外側には位置を置けないので、上の等式から $A\cap B=\varnothing$ となる。したがって $A,B$ は全位置を二分する。$A$ の位置は 1 回目でしか操作されないため、1 回目の終了時点ですべて正しくなければならない。

順列をサイクル分解する。あるサイクルの一部だけを $A$ に入れると、その中の少なくとも 1 位置が必要とする値が $B$ に残る。よって $A$ はいくつかのサイクル全体の合併でなければならない。逆に、長さの合計がちょうど $N$ になるサイクルを選べれば、それらを 1 回目で、残りを 2 回目で整列できる。

したがって固定点がない場合、2 回で整列できるための必要十分条件は、サイクル長の一部の和がちょうど $N$ になることである。この条件は部分和 DP により $O(N^2)$ で判定できる。

そのような部分集合が存在すれば答えは $2$、存在しなければ答えは $3$ である。後者では 2 回が不可能である一方、最初の 1 回で固定点を 1 つ作れば、さらに高々 2 回で整列できる。

よって答えは常に $0,1,2,3$ のいずれかである。各テストケースの計算量は $O(N^2)$、メモリ使用量は $O(N)$ である。

Solution written by GPT5.6