https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c
$N$要素からなる2つの整数列$A, B$が与えられる。$A$の要素を2つ選んでswapする操作を$N-2$回まで行うことで、任意の$i$について$A_i \lt B_i$となるようにできるかを判定せよ。
まず、$A, B$をソートしたときに$A_i \lt B_i$となっていない場所がひとつでもあれば、どうやっても無理であることがわかる。そうでなければ、(必要なswap回数はともかく)条件を満たせるAの並びが少なくとも１つは存在する。
操作前から操作後への置換を巡回置換に分解したときに連結成分が$n$個になったとすると、必要なswap数は$N-n$になる。これは置換をグラフとして表したときの最小全域森の辺の数である。
はじめに$B$をソートして、ソートによる$B$の要素の入れ替えを$A$にも適用する。以降この順序を初期状態とする。初期状態から$A$をソートしたときの置換をサイクルグラフにしたときに、連結成分が2つ以上であれば$N-2$回までのswapでソートできることになるので、可能である。
ソートの置換が1つの巡回置換で構成される場合であっても、ソートされた状態から$A_i, A_{i+1}$をswapしても条件を満たすような$i$がひとつでも存在すれば可能である(連結成分が1つではなくなるため)。これは、$A_{i+1}\leq B_i$であるような$i$が存在することに相当する。
置換の連結成分の個数を調べるにはUnion-Find treeが適している。
置換の性質をよく知らなかった。