問題

$A_1, \cdots, A_N$ と $B_1, \cdots, B_N$ がある。以下の操作を $N-2$ 回以下行って、 $A_i \leq B_i$ にできるか判定する。

$1 \leq i, j \leq N$ を選択し、 $A_i$ と $A_j$ の値を入れ替える

考察

$B$ が昇順であると仮定する。 $A$ を昇順にソートして比較するとき、 $A_i \leq B_i$ を満たさない $i$ が存在すれば、実現不可能である。以下、これは満たされていると仮定する。

$A$ をソートするのに $N-2$ 回以下ならば実現可能である。以下では、 $A$ のソートに $N-1$ 回かかった場合について考える。

次の補題を利用する（証明は後述）

$N$ -順列 $P$ を選択ソートで昇順に並び替えるときに必要な交換回数が $N-1$ 回なら、 $P$ の任意の2要素を交換した順列 $P^\prime$ は $N-2$ 回の交換で昇順にできる

$A, B$ ともに昇順になっているので、 $A_j$ と $A_{j+1}$ を交換して $A_i \leq B_i$ が成り立つ $j$ 、すなわち $A_{j+1} \leq B_j$ になるような $j$ が存在するか判定すればいい。

証明

[補題] $N$ -順列 $P$ を選択ソートで昇順に並び替えるときに必要な交換回数が $N-1$ 回なら、 $P$ の任意の2要素を交換した順列 $P^\prime$ は $N-2$ 回の交換で昇順にできる

$P$ は、昇順に並んだ $N$ -順列 $E (= [1, 2, \cdots, N])$ と $E$ の任意の要素 $p_0$ から、次の操作を $N-1$ 回行って作ることができる。

今まで交換していない番号 $p_i$ と $p_0$ を交換する。

$P$ の交換すうr2要素 $x, y$ のうち、 $x = p_0$ としても、 $P$ を作るために選んだ番号の列 $[p_1, p_2, \cdots, p_{N-1}]$ が存在し、 $y = p_k$ なる $k(1\leq k \leq N-1)$ が存在する。 $P^\prime$ は、 $x$ を $p_k$ から、 $P$ を作ったときと逆順に操作を行えば、 $k$ 回の操作で $p_0\sim p_k$ の $k+1$ 要素を昇順に戻すことができた。残りの $N-k-1$ 要素は、 $N-k-2$ 回の交換で任意の順番に並び替えられるので、 $N-k-2$ 回以下で全体を昇順に戻すことができた。よって、 $P^\prime$ 全体は $N-2$ 回以下の交換で昇順にできる。