C - Swaps 2 Editorial by QCFium


\(A'_i = A_i + i\) とすると、問題文の操作は \(A'\) で見ると \(A'_i\)\(A'_{i + 1}\) を交換することになります。
よって、\(A_i \leftarrow A_i + i, B_i \leftarrow B_i + i\) とした上で以下の問題を解けば良いことになります :
\(i\) を選んで \(A_i\)\(A_{i + 1}\) を交換することを繰り返し、\(A = B\) とすることができるかを判定せよ。できるなら最小の操作回数を求めよ。

もし \(A, B\) をそれぞれ集合として見たときに等しくなければ \(A = B\) とするのは不可能です。
\(A_i\) を最終的に \(B_{s_i}\) に持ってくる、というような数列 \(s\) を決めれば、操作回数の最小は \(s\) の転倒数なので \(O(N \log(N))\) で求めることができます。
問題は \(A, B\) は同じ要素を複数含む可能性があるので \(s\)\(1\) つに定まらないことですが、実は以下のように最適な \(s\) が求まります。

  • 同じ値 \(c\)\(A_{i_1}, A_{i_2}, A_{i_3}, \dots, A_{i_n} (i_1 < i_2 < i_3 < \dots < i_n)\) 及び \(B_{j_1}, B_{j_2}, B_{j_3}, \dots, B_{j_n} (j_1 < j_2 < j_3 < \dots < j_n)\) に現れるとする
  • \(s_{i_1}, s_{i_2}, s_{i_3}, \dots, s_{i_n}\) が自由に並び替え可能である。しかし、\(i < j, s_i > s_j\) のとき \(s_i\)\(s_j\) を交換すると \(s\) の転倒数は減るので、そのような操作を繰り返してできる \(s_{i_k} = j_k\) が最適である

posted:
last update: