mayoko’s diary

プロコンとかいろいろ。

AtCoder Grand Contest 003

解法

全ての数が異なるので, ソートされた後それぞれの数がどこに移動するかが決まっている, ということと, 操作 2 が「偶数番目のみ, 奇数番目のみを入れ替えることができる」ということに対応している, ということがポイントです。

最終的に行きたいポイントは決まっているので, 最後に偶数番目になる数が奇数番目にある場合は入れ替えなければならないし, 逆もまた然りです。これに必要な回数は(最終的な偶奇と最初の偶奇がバラバラな数字の数)/2 です。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vi A(N);
    vi B, C;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (i%2 == 0) B.push_back(A[i]);
        else C.push_back(A[i]);
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    int b = 0, c = 0;
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        if (b < B.size() && A[i] == B[b]) {
            b++;
            if (i%2 == 1) ans++;
        }
        if (c < C.size() && A[i] == C[c]) {
            c++;
            if (i%2 == 0) ans++;
        }
    }
    cout << ans/2 << endl;
    return 0;
}