F - Simultaneous Swap Editorial by Kiri8128
A を固定する方法2 つの配列を扱う問題では、片方を固定して考えると考えやすくなることがあります。
まず \(A\) と \(B\) が多重集合として異なる場合は不可能なので、多重集合が一致するとして考えます。
\(A\) の要素が相異なる場合は、 \(A\) 側が昇順になるようにソートして考えます。例えば
\[A: 1, 2, 3, \cdots \\ B: 4, 5, 6, \cdots\]
の状態で \(i=1,\ j=2,\ k=3\) として操作すると
\[A: 2, 1, 3, \cdots \\ B: 6, 5, 4, \cdots\]
となりますが、 \(A\) 側を固定すると結局
\[A: 1, 2, 3, \cdots \\ B: 5, 6, 4, \cdots\]
となります。結局 \(B\) 側において長さ 3 の巡回置換が行われたことになります。この要領で任意の長さ 3 の巡回置換ができることが分かります。 また一般に、長さ 3 の巡回置換の積で書ける置換は偶置換全体の集合と一致することが知られています。 よって転倒数の偶奇を調べれば判定できます。
\(A\) が同じ要素を複数含む場合は、あえてそれらを区別して考えると、 \(B\) 側で偶奇の入れ替えの自由度ができるので必ず可能であることが分かります。
posted:
last update: