解法

基本的には $A$ をソートできればよい。ソートに必要な操作回数は置換をサイクル分解すれば分かる。もし完全なソートに $N - 1$ 手かかるなら、すべての隣接 $2$ 項を swap してみればよい。$O(N \log N)$。

  1. とりあえず $B_1 \le B_2 \le \dots \le B_N$ であるように $A, B$ を並べ替えてから考える。
  2. ひとまず手数のことを忘れて置換 $p \in \mathfrak{S} _ N$ を作っていく。 これは $A _ {p_1} \le A _ {p_2} \le \dots \le A _ {p_N}$ とするのが最適。 この結果を $B$ と比較し順序制約を確認し、だめならどうやってもだめ。
  3. 与えられた置換を実行するための操作回数を求めたい。これはサイクル分解をすればよい。まず $i \to p_i \to p _ {p_i} \to \dots \to i$ のようにしてできるサイクルの集合を考える。操作を $1$ 回行うごとにサイクルはひとつ増やせ、サイクルの個数が $N$ になればソート済みである。これは明らかに最適なので、操作回数の最小値が求まる。
  4. このとき $N - 2$ 手以下で済んでいれば終了である。そして $N - 1$ 手かかってしまうのは全体がひとつのサイクルであるときのみである。
  5. $p$ を修正して $N - 2$ 手で済むような $q$ に組み替えたい。これは $q = (i~j)p$ と互換をすることに等しい。ここで試す $i, j$ は素朴には $O(N^2)$ 通りだが、これは $i = j + 1$ であるもの (つまり隣接互換) に限ってよいので $O(N)$ 個である。よって $p$ を修正して適切な $q$ を作れるかどうかは $O(N)$ で判定できる。
  6. 十分性だけでなく必要性「$p$ を互換によって修正して得られる置換 $q = (i~j)p$ で適切なものがないならばどんな置換 $r$ も要件を満たさない」も示す必要がある。証明は次のようになる: そのような $q$ が存在しないと仮定しよう。この仮定は $\forall i.~ B _ i \lt A _ {p _ {i + 1}}$ に等しい。$p$ を作った直後に確認した順序制約 $\forall i.~ A _ {p_i} \le B_i$ と合わせると $A _ {p_1} \le B_1 \lt A _ {p_2} \le B_2 \lt \dots \lt A _ {p_N} \le B_N$ が得られる。これは $p$ 以外には順序制約を満たす置換がないことを意味する。

メモ

  • 本番ではよく分からないまま適当にして AC した。閉路への分解という語すら考察中に出てきてなかったので、たぶん頭を付け忘れていたのだろう
  • 「サイクル分解」と言われれば自明だった。本番でなぜこれが解けなかったのか不思議だ

リンク