この解説は本解説のおまけの、操作回数が \(3500\) 回以下となるような操作列を構築するものです。本解説の内容を前提とするため、まだ本解説を読んでいない方はそちらを先に読むことをおすすめします。

swap 操作が基本的に \(3\) 回で行えることにより、\(A\) を好きな順番に並び替えることが \(3N\) 回の操作で実現できます。よって、\(A\) と \(B\) を多重集合として一致させることが出来れば \(3N\) 回の操作で \(A = B\) とすることが出来ます。

マッチさせる要素同士の差の絶対値の総和は小さい方がいいので、\(A\) の中で \(i\) 番目に小さい項を最終的に \(B\) の中で \(i\) 番目に小さい項と一致させることを考えます。

主に以下のような流れで \(A\) と \(B\) を多重集合として一致させます。ここで、\(A\) の中でマッチ相手より小さい要素を -、大きい要素を +、等しい要素を = と表記します。

• + か - が存在する間、以下を繰り返し行う。
  • + と - のどちらかである要素のみを取り出し、swap 操作を用いて - - - … - - - + + + … + + + の順番になるようにする。・・・①
  • 左にある + から順に + である間、左にある - であって最も近いものと操作をする。・・・②

この解法の回数を解析します。まず、② の操作が行われる回数を解析します。これは、\(A,B\) をソートした列を \(A',B'\) としたとき \(\frac{\sum |A'_i - B'_i|}{2}\) と等しいです。ここで、\(D'_i = A'_i - B'_i\) としましょう。\(D'\) を固定したときに \(A',B'\) を復元することを考えると、\(D'\) の条件は以下のようになります。

• \(\sum D'_i = 0\)
• \(\sum |D'_i - D'_{i+1}| \le M\)

この条件を満たし、かつ \(\sum |D_i|\) を最大化するようなものは \(-\frac{M}{2}\) を \(\frac{N}{2}\) 個、\(+\frac{M}{2}\) を \(\frac{N}{2}\) 個並べたものとなります。よって、② の操作回数は \(\frac{NM}{4}\) 回で抑えられます。

次に、① の操作回数を考えます。まず、① は (並び替えたい + の個数) 回の swap 操作で実現できます。よって、1 回目の ① の操作回数は \(\frac{3N}{2}\) 回で抑えられます。2 回目以降の ① の操作回数は、「全ての + を通ってもまだ - であるような要素の個数」の総和となります。そして、その個数は \(M\) で抑えられます。なぜならば、そのような要素が \(1\) 個存在するごとに \(D\) の最大値が \(1\) 減るからです。よって、① の操作回数は \(\frac{3N}{2} + 3M\) 回で抑えられます。

上記の途中で \(A_1\) と \(A_N\) の swap が求められてしまう場合もありますが、そのような回数は簡単に定数回に抑えられるか \(\sum D\) が小さいケースのいずれかとなります。

よって、この解法の全体の操作回数は \(\frac{3N}{2} + 3M + \frac{NM}{4} + 3N = \frac{NM}{4} + \frac{9N}{2} + 3M\) 回となります。そして、この解法は \(NM\) にかかる定数倍が最善な解法であることも分かります。