ARC 162

Mon, May 12, 2025

A. Ekiden Race

https://atcoder.jp/contests/arc162/tasks/arc162_a

B. Insertion Sort 2

https://atcoder.jp/contests/arc162/tasks/arc162_b

自力 AC. 1時間近く掛かった。

実験により 2 1 がダメ、3 2 1 もダメなことから転倒数が奇数の場合は無理だと予想がついた。また、2つの数字を移動させるということなので転倒数の偶奇も移動によって変わらない。

構成法について、小さい数字から順に左に移動させていくことを考える。目当ての場所に移動させるには後述の通り多くとも 2 回の移動で済むため、$N \leq 10^3$ という制約では $2 \times 10^3$ 回以下の操作で必ず昇順に並べることができる。

$P_1, \cdots, P_p$ までは昇順に並んでおり、次に移動させるべき数字 $p+1$ が $k$ 番目にあるとする。このとき $k < N$ と $k = N$ で場合分けする。

$k < N$ のとき、$i = k$, $j = p$ とすることで、目当ての数字を $p+1$ 番目に移動させることができる。

$k = N$ のとき、$i = k-2$, $j = N$ とし、目当ての数字より左にある 1,2 個を末端に移動させることで $k < N$ の状態にすることができる。ここで $P$ は偶置換であるので $p+1$ が右端にあるとき、左2つは $p+1$ よりも大きい数字である。

以上より、目当ての数字は目当ての場所に2回以下の操作で移動させることができる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vint P(N);
    rep(i, N) {
        cin >> P[i];
        P[i]--;
    }

    // 転倒数をチェック
    {
        vector<pair<int, int>> ids;
        rep(i, N) {
            ids.emplace_back(P[i], i);
        }
        sort(all(ids));
        fenwick_tree<int> fw(N);
        int tento = 0;
        for (auto [_, i] : ids) {
            tento += fw.sum(i, N);
            fw.add(i, 1);
        }
        if (tento % 2 == 1) {
            yesno(false);
            return;
        }
    }

    vector<pair<int, int>> histories;
    int cnt = 0;
    int nx = 0;
    int sorted_pos = -1;
    while (true) {
        if (is_sorted(all(P)))
            break;
        cnt++;
        int pos = distance(P.begin(), find(all(P), nx));
        if (pos < N - 1) {
            sorted_pos++;
            histories.emplace_back(pos + 1, sorted_pos);

            vint tmpP;
            rep(i, sorted_pos) {
                tmpP.push_back(P[i]);
            }
            tmpP.push_back(P[pos]);
            tmpP.push_back(P[pos + 1]);
            rep2(i, sorted_pos, N) {
                if (i == pos || i == pos + 1)
                    continue;
                tmpP.push_back(P[i]);
            }
            nx++;
            swap(tmpP, P);
        } else {
            vint tmpP;
            pos -= 2;
            rep(i, N) {
                if (i == pos || i == pos + 1)
                    continue;
                tmpP.push_back(P[i]);
            }
            tmpP.push_back(P[pos]);
            tmpP.push_back(P[pos + 1]);
            histories.emplace_back(pos + 1, N - 2);
            swap(tmpP, P);
        }
    }

    yesno(true);
    cout << cnt << endl;
    for (auto [i, j] : histories)
        cout << i << ' ' << j << endl;
}