考察
まずAとBのmultisetが一致する必要がある。値が全て異なる場合、各操作はAとBの両方で一回ずつswapするので、二列の反転数の和の偶奇が不変。最後に一致した状態ではその和は偶数だから、初期値が奇数なら不可能である。
十分性は左から位置を確定する構成で示せる。x=1,…,N−2 について A_x≠B_x なら、未確定suffixから A_x=B_y となる y>x を取り、z>x, z≠y を選ぶ。操作 (i,j,k)=(y,z,x) はA_xを保ったままB_xをA_xへ直し、確定済みprefixを変えない。
採用する候補: multiset一致、重複の有無、反転数和の偶奇で判定し、全異値時はprefixを固定する構成を使う。
不変量が必要条件を与え、prefix構成が偶奇条件の十分性を示す。
棄却する候補: 操作列を状態探索する。
順列対の状態数は指数的になる。
典型の発動条件
置換parity不変量
発動条件: 二列へ同時に互換を施す。
反転数の偶奇変化を追う。
重複によるparity自由化
発動条件: 同値要素があり識別順を交換しても観測列が変わらない。
一方のparityを任意に反転できるとみなす。
問題固有の要素
同時swap制約は全相異時だけ効き、重複一組があるだけでparity障害が消える。
別の問題へ持ち帰る視点: 重複を持つ並べ替えでは置換符号が一意でなくなる。
正当性
全異値なら操作ごとに二つの反転数がともに反転し、その和の偶奇は保たれる。一方、位置xを直す操作 (y,z,x) はAのswap位置がy,z、Bのswap位置がy,xなので、xより前の値を変えずB_xだけをA_xへ合わせる。未確定suffixのmultiset一致は各段で保たれ、x≤N−2 ではyと異なるzを選べる。最後の二位置は一致するかswap違いだけである。swap違いなら反転数和は奇数となるため、初期偶数条件の下では起こらず、最後にA=Bとなる。
重複値があれば、等しい二要素に異なる識別ラベルを付け、そのラベルをA内で交換しても実配列は変わらない。この交換で反転parityを反転できるので、ラベルを選んで反転数和を偶数にし、同じ構成を適用できる。
実装上の注意
- multiset不一致を先に除外し、parityだけなら反転数全値でなくmod2更新でよい。
復習の核
- 小Nの状態BFSと比較し、重複なしの奇偶両例、重複あり、multiset不一致を確認する。
計算量と制約
時間
O(N log N)、multiset sortと反転parity。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 2\times 10^5; 1\leq A_i,B_i\leq N; All values in the input are integers.
出典