V-Sort

各位置を頂点とし、許される交換に対応する無向辺を張る。同じ連結成分内では任意の並べ替えができるため、各成分の現在値の多重集合と目標値の多重集合が等しいことが必要十分条件である。位置 $A_i,B_i$ の目標値はいずれも $i$ である。

• サブタスク 1（$X=Y=0$）：交換できるのは $A_i,B_i$ だけである。両方の目標値が $i$ なので、最初からすべて正しくなければならない。$O(N)$ 時間で確認する。
• サブタスク 2（$X=Y=1$）：二つの成分は $A_1,B_2,A_3,B_4,\ldots$ と である。それぞれに から が一度ずつ必要である。頻度を調べれば時間・空間ともに となる。 では二つの孤立頂点となる。
• サブタスク 3（$X=0$）：$Y=0$ ならサブタスク 1 と同じである。$Y>0$ なら $A_i,B_i$ がつながり、添字を ずつ移動できるため、成分は添字を で割った余りごとに分かれる。位置 の値 が を満たし、各値が全体で二度ずつ現れることを調べる。時間・空間ともに である。
• サブタスク 4（$N\leq5$）：愚直解法として $2N$ 頂点に Floyd–Warshall 法を適用し、各成分の現在値と目標値をソートして比較する。時間計算量は $O(N^3)$、空間計算量は $O(N^2)$ である。
• サブタスク 5（$N\leq3\,000$）：隣接行列を作り、各頂点で全頂点を調べる DFS により成分を求め、頻度を比較する。時間・空間ともに $O(N^2)$ である。ファイル内の $\sum N\leq3\,000$ より となる。
• サブタスク 6：各頂点の高々二つの隣接頂点を添字から直接計算し、非再帰 DFS を使う。現在値の頻度を増やし、目標値の頻度を減らす。触れた要素だけを確認して初期化すれば、時間・空間ともに $O(N)$ となる。成分ごとに頻度配列全体を初期化してはいけない。

$X=N$ または $Y=N$ なら対応する種類の辺はない。孤立頂点も確認する。値の重複があるため総和だけの比較では不十分である。全体の時間計算量は $O(\sum N)$ となる。添字と頻度の絶対値は $1\,000\,000$ 以下であり、符号付き 64 ビット整数を超える演算は不要である。

Solution written by GPT