[1] はじめに

この問題は、最適化と構築の融合問題です。条件を整理しながら、一歩ずつ考察を重ねていくことで、正答にたどり着けます。

[2] 操作 \(A\) の回数の最小値を求める

\(P_i\) の偶奇に着目します。\(P_i\) と \(i\) の偶奇が一致するような \(i\) を良いインデックス、そうでない \(i\) を悪いインデックスとします。さらに、悪いインデックスの個数を \(P\) の不一致度とし、各操作で \(P\) の不一致度がどのように変化するかを考えます。

操作 \(A\) において、\(P\) の不一致度は「\(2\) 増加する」「変わらない」「\(2\) 減少する」のいずれかです。このことは、以下のように場合分けすることでわかります。操作前の段階で、

• \(i,i+1\) がともに良いインデックスのとき：\(P\) の不一致度は \(2\) 増加します。
• \(i,i+1\) がともに悪いインデックスのとき：\(P\) の不一致度は \(2\) 減少します。
• \(i,i+1\) のうち一方が良いインデックスで、もう一方が悪いインデックスのとき：\(P\) の不一致度は変わりません。

また、操作 \(B\) において、\(P\) の不一致度は変わりません。

以上のことと、\(P\) の最終形（昇順にソートされたもの）の不一致度が \(0\) であることを合わせると、次のことが分かります。

• 操作 \(A\) は、少なくとも \(\,\frac{1}{2}\times(\) \(P\) の初期状態の不一致度 \()\) 回必要

注意：\(P\) が \((1,2,\ldots,N)\) の順列である限り、\(P\) の不一致度は必ず偶数であることが証明できます。

[3] \(P\) の不一致度を \(0\) にする

操作 \(A\) をちょうど \(\,\frac{1}{2}\times(\) \(P\) の初期状態の不一致度 \()\) 回行うことで、\(P\) の不一致度を \(0\) にする方法を考えます。

[2]の場合分けにより、操作 \(A\) の回数を \(\,\frac{1}{2}\times(\) \(P\) の初期状態の不一致度 \()\) に抑えるためには、\(i,i+1\) がともに悪いインデックスであるような \(i\) に対してのみ操作 \(A\) を行うことが可能です。

良いインデックスと悪いインデックスの並びが次のような時には、容易に実現可能です（O は良いインデックスを、X は悪いインデックスを表しています）。

OOXXOXXO

しかし、次の場合は少し難しいです。

XOXOOXOX

そこで、操作 \(B\) を何回でも行えることを利用して、予め次のように悪いインデックスを端に集めておくことにします。

XXXXOOOO

すると、操作 \(A\) をちょうど \((\) \(P\) の初期状態の不一致度 \() \times \frac{1}{2}\) 回行うことで、\(P\) の不一致度を \(0\) にすることが可能となりました。

注意：操作 \(B\) のみを行うことで悪いインデックスを端に寄せることが可能なのは、\(P\) が \((1,2,\ldots,N)\) の順列であるため、偶数の悪いインデックスの個数と奇数の悪いインデックスの個数が等しいからです。

[4] \(P\) を昇順に並び替える

\(P\) の不一致度が \(0\) になったので、すべての \(i\) について、\(i\) と \(P_i\) の偶奇が一致しています。なので、\(P_i>P_{i+2}\) であるような \(i\) を見つけて \(i\) について操作 \(B\) を行う、ということを繰り返すと \(P\) を昇順に並び替えることが可能です。

[5] 操作回数の合計の見積もり

最後に、操作回数の合計が \(10^5\) 回以内に収まるかを確認しておきましょう。

悪いインデックスを端にそろえるために必要な操作 \(B\) の回数は高々 \(\frac{N}{4}\times\frac{N}{2}\) 回です。

操作 \(A\) の回数は高々 \(\frac{N}{2}\) 回です。

最後に \(P\) を昇順に並び替えるために必要な操作 \(B\) の回数は高々 \((\frac{N}{2})^2\) 回です。

\(N=400\) のとき、これらの合計は \(60200\) 回なので、十分 \(10^5\) 回以内に収まります。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;
int p[405];
vector<pair<char,int>> ans;
void f(char c,int i){
    ans.emplace_back(c,i+1);
    swap(p[i],p[i+1+c-'A']);
}
int main(){
    int N; cin >> N;
    for(int i=0;i<N;i++) cin >> p[i];
    for(int i=0;i<N;i++) for(int j=0;j<N-2;j++) if(p[j]%2!=p[j+2]%2 && p[j]%2!=j%2) f('B',j);
    for(int i=0;i<N-1;i++)if(p[i]%2!=p[i+1] && p[i]%2==i%2) f('A',i);
    for(int i=0;i<N;i++) for(int j=0;j<N-2;j++) if(p[j]>p[j+2]) f('B',j);
    cout << ans.size() << endl;
    for(auto x:ans) cout << x.first << ' ' << x.second << endl;
}