ARC147 B - Swap to Sort (500, 緑)

お気持ち

本番に考えたこと
- 奇数に青丸、偶数に赤丸を書いて、青と赤が交互に並ぶように考えた。
- 操作Aで青赤青赤...を作ってから、操作Bをする方法が最適と思っていてWA。
  - 反例: P = (2, 4, 1, 3) 最適解は1だが、上記では3回かかってしまう。
- 場所の偶奇が合っているかで青丸、赤丸の中に〇×を書いて頑張って考察した。
勘で解くならこうしたい
- P_i <-- P_i mod 2 として (0, 1, 0, 1, ...) を作ってもよさそう。偶数番Flipをして (0, 0, ...) を作る問題にできそう。
- 操作Aは、(0, 0) <-> (1, 1)、(0, 1) <-> (0, 1)、(1, 0) <-> (1, 0)、2個飛ばしのswapは (0, 0) <-> (0, 0), (1, 1) <-> (1, 1), (0, 1) <-> (1, 0) になるから、(1, 1) -> (0, 0) を使いたい。
- 操作Bで 1 をできるだけ前に持ってきてから、1, 1 を0, 0 にしていって、最後に操作Bで P をバブルソートしたら解けそう。
- 以下の考察により正しいことが分かる。

考察

初期地点が $i$ のものを目的地 $P_i$ に移動したい。
（操作Bでは）その差の偶奇が変化しないため、 $Q_i = |P_i - i|$ % 2と置いてみたい。
任意の順列 $P$ に対して、 $Q_i = |P_i - i|$ % 2とすると $Q_0 + Q_2 + ... = Q_1 + Q_3 + ...$ になるのが美しくて、感動した。
証明すると新しい知識が得られる問題は、楽しい👍

ソースコード

//Q_i = |P_i - i| % 2としたとき、任意の順列Pに対して(Q_0+Q_2+Q_4+...)=(Q_1+Q_3+Q_5+...)なの、美しい。
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
typedef pair<char, int> P;

int n;
int p[400], q[400];

int main() {
    int i, j;

    cin >> n;
    rep(i, n) { cin >> p[i]; p[i]--; q[i] = abs(p[i] - i) % 2; }
    
    vector<P> ans;
    rep(i, n) {
        for (j = i; j >= 2; j -= 2) {
            if (q[j - 2] < q[j]) {
                swap(q[j - 2], q[j]);
                swap(p[j - 2], p[j]);
                ans.push_back(P('B', j - 2));
            }
        }
    }

    for (i = 0; i + 1 < n; i += 2) {
        if (q[i] == 1 && q[i + 1] == 1) {
            q[i] = 0; q[i + 1] = 0;
            swap(p[i], p[i + 1]);
            ans.push_back(P('A', i));
        }
    }

    rep(i, n) {
        for (j = i; j >= 2; j -= 2) {
            if (p[j - 2] > p[j]) {
                swap(p[j - 2], p[j]);
                ans.push_back(P('B', j - 2));
            }
        }
    }

    cout << ans.size() << endl;
    rep(i, ans.size()) {
        cout << ans[i].first << " " << ans[i].second + 1 << endl;
    }
    return 0;
}