Min Swaps [CSAcademy #50 E]

https://csacademy.com/contest/round-50/task/min-swaps/

概要

N要素の順列Pがある。
この順列の要素を任意回スワップすることで隣接する要素の差の総和を最大化したい。
最大化するときにスワップする回数の最小値は？
Nは偶数で2<=N<=100000

解法

まず、隣接する要素の差の総和が最大化される場合を考えてみる。
とりあえず全探索解を探して規則性を探ってみよう。

void test() {
    vector<int> v;
    rep(i, 0, N) v.push_back(i + 1);
    int ma = 0;
    vector<vector<int>> vv;
    do {
        int sm = 0;
        rep(i, 0, N - 1) sm += abs(v[i] - v[i + 1]);
        if (ma < sm) {
            ma = sm; vv.clear();
        }
        if (ma == sm) vv.push_back(v);
    } while (next_permutation(v.begin(), v.end()));

    printf("[%d]\n", ma);
    fore(v, vv) {
        rep(i, 0, N) printf("%d,", v[i]);
        printf("\n");
    }
}

これを動かすとこんな感じ。

[1]
1,2,
2,1,
[7]
2,4,1,3,
3,1,4,2,
[17]
3,5,1,6,2,4,
3,5,2,6,1,4,
3,6,1,5,2,4,
3,6,2,5,1,4,
4,1,5,2,6,3,
4,1,6,2,5,3,
4,2,5,1,6,3,
4,2,6,1,5,3,
[31]
4,6,1,7,2,8,3,5,
4,6,1,7,3,8,2,5,
4,6,1,8,2,7,3,5,
4,6,1,8,3,7,2,5,
4,6,2,7,1,8,3,5,
4,6,2,7,3,8,1,5,
4,6,2,8,1,7,3,5,
4,6,2,8,3,7,1,5,
4,6,3,7,1,8,2,5,
4,6,3,7,2,8,1,5,
4,6,3,8,1,7,2,5,
4,6,3,8,2,7,1,5,
4,7,1,6,2,8,3,5,
4,7,1,6,3,8,2,5,
4,7,1,8,2,6,3,5,
4,7,1,8,3,6,2,5,
4,7,2,6,1,8,3,5,
4,7,2,6,3,8,1,5,
4,7,2,8,1,6,3,5,
4,7,2,8,3,6,1,5,
4,7,3,6,1,8,2,5,
4,7,3,6,2,8,1,5,
4,7,3,8,1,6,2,5,
4,7,3,8,2,6,1,5,
4,8,1,6,2,7,3,5,
4,8,1,6,3,7,2,5,
4,8,1,7,2,6,3,5,
4,8,1,7,3,6,2,5,
4,8,2,6,1,7,3,5,
4,8,2,6,3,7,1,5,
4,8,2,7,1,6,3,5,
4,8,2,7,3,6,1,5,
4,8,3,6,1,7,2,5,
4,8,3,6,2,7,1,5,
4,8,3,7,1,6,2,5,
4,8,3,7,2,6,1,5,
5,1,6,2,7,3,8,4,
5,1,6,2,8,3,7,4,
5,1,6,3,7,2,8,4,
5,1,6,3,8,2,7,4,
5,1,7,2,6,3,8,4,
5,1,7,2,8,3,6,4,
5,1,7,3,6,2,8,4,
5,1,7,3,8,2,6,4,
5,1,8,2,6,3,7,4,
5,1,8,2,7,3,6,4,
5,1,8,3,6,2,7,4,
5,1,8,3,7,2,6,4,
5,2,6,1,7,3,8,4,
5,2,6,1,8,3,7,4,
5,2,6,3,7,1,8,4,
5,2,6,3,8,1,7,4,
5,2,7,1,6,3,8,4,
5,2,7,1,8,3,6,4,
5,2,7,3,6,1,8,4,
5,2,7,3,8,1,6,4,
5,2,8,1,6,3,7,4,
5,2,8,1,7,3,6,4,
5,2,8,3,6,1,7,4,
5,2,8,3,7,1,6,4,
5,3,6,1,7,2,8,4,
5,3,6,1,8,2,7,4,
5,3,6,2,7,1,8,4,
5,3,6,2,8,1,7,4,
5,3,7,1,6,2,8,4,
5,3,7,1,8,2,6,4,
5,3,7,2,6,1,8,4,
5,3,7,2,8,1,6,4,
5,3,8,1,6,2,7,4,
5,3,8,1,7,2,6,4,
5,3,8,2,6,1,7,4,
5,3,8,2,7,1,6,4,

すると、N/2とN/2+1が両端にあり、N/2よりも小さい数がN/2の添字とパリティが一致する添字に配置され、N/2+1よりも大きい数がN/2+1の添字とパリティが一致する添字に配置されることが分かる。
あとは、この状況になるように貪欲にスワップする回数を数え上げていく。

int N, A[101010];
#define INF INT_MAX/2
int B[101010];
//---------------------------------------------------------------------------------------------------
int check() {
    int L = N / 2;
    int R = N / 2 + 1;

    rep(i, 0, N) B[i] = A[i];

    int res = 0;
    if (B[0] != L) {
        rep(i, 1, N) if (B[i] == L) {
            swap(B[0], B[i]);
            res++;
            break;
        }
    }

    if (B[N - 1] != R) {
        rep(i, 0, N - 1) if (B[i] == R) {
            swap(B[i], B[N - 1]);
            res++;
            break;
        }
    }

    int c = 0;
    rep(i, 1, N - 1) {
        if (i % 2 == 1) {
            if (B[i] < R) c++;
        }
        if (i % 2 == 0) {
            if (B[i] > L) c++;
        }
    }

    return res + c / 2;
}
void solve() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    int ans = INF;
    ans = min(ans, check());
    reverse(A, A + N);
    ans = min(ans, check());

    printf("%d\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}