AtCoder AGC 003 C - BBuBBBlesort! (水色, 600 点)

楽しかった

問題へのリンク

問題概要

長さ の数列 が与えられる。どの 2 要素も互いに相異なることが保証される。これに対し

1. 隣り合う 2 要素を swap する
2. 連続する 3 要素を反転する

という操作を行ってソートしたい。ただし、1 の使用回数を最小にしたい。1 の使用回数の最小値を求めよ。

制約

• 

考えたこと

とりあえず座標圧縮して、数列が の順列であるとしてよい。

こういう操作系の問題は、操作をわかりやすく言い換えることが肝要なイメージ。2 番目の「連続する 3 要素の反転」とは、すなわち「 と の swap」である。ここで真ん中の要素は変わらないことに注意する。つまり 2 番目の操作によって

• の 0, 2, 4, ... 番目の要素のなす集合は不変
• の 1, 3, 5, ... 番目の要素のなす集合は不変

ということになる。こういう不変量を見出す考察もよくみる。不変量を見出すことでしばしば

• これだけの回数は絶対必要になる

という証明ができて、実際にその回数が達成できることを具体的に構成する、という流れは本当によく見る。今回も例外でなく、

• の偶数番目と奇数番目のメンバー入れ替えに必要な回数は絶対に必要
• 具体的には、 として、 の要素数 (= の要素数) から の共通部分の要素数を引いた値が絶対に必要

ということが言えて、それが十分であることも言える。十分であることを示すのに鍵となるのは

• 偶数番目同士、奇数番目同士では、任意の並び替えができる

ということ。つまり

• 入れ替えたい偶数番目と奇数番目の要素たちが隣り合う位置に来るようにして
• その 2 要素を隣接 swap して入れ替えて

というのを繰り返したあと

• 偶数番目と奇数番目についてそれぞれソートする

という風にすれば OK。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<int> A;

long long solve() {
    vector<int> alt;
    for (int i = 0; i < N; ++i) alt.push_back(A[i]);
    sort(alt.begin(), alt.end());
    for (int i = 0; i < N; ++i) {
        int it = lower_bound(alt.begin(), alt.end(), A[i]) - alt.begin();
        A[i] = it;
    }
    vector<int> nums(N, 0);
    for (int i = 1; i < N; i += 2) nums[i]++, nums[A[i]]++;
    int res = 0;
    for (int i = 1; i < N; i += 2) if (nums[i] == 2) ++res;
    return N/2 - res;
}

int main() {
    while (cin >> N) {
        A.resize(N);
        for (int i = 0; i < N; ++i) cin >> A[i];
        cout << solve() << endl;
    }
}