AtCoder Grand Contest 003 C - BBuBBBlesort!

問題URL

C - BBuBBBlesort!

解法

まず、数列の要素は互いに相異なるので、要素を小さい順からと置き換えても問題ありません。
そうすると、この問題は、与えられた操作を行って、左からと並び替える問題と考えることができます。

操作2が何を行っているかを考えてみます。

とありますが、3つのうち、2つめの要素(つまり真ん中の要素)は、順番を反転させても変わらないので、1つ目と3つ目の要素の反転を行っていると見ることができます。
そして、操作2は何度行っても全体のスコアに影響を及ぼさないことから、数列のうち偶数(奇数)番目の要素同士は互いを好きに並び替えてよいことがわかります。

操作1が何を行っているかを考えてみます。

とあります、これはつまり、数列の要素の中で隣あう偶数番目と奇数番目の要素のスワップが行えることを示しています。

つまり、並び替える前の数列の要素の偶奇がその要素を左からのインデックス()の偶奇と等しくないときにのみ操作1を行えばよいです、そのような要素の数をとしておきます。
並び替える前の要素が偶数で、その要素を左からのインデックス()が奇数というような要素がある場合、必ず同じ数だけ、並び替える前の要素が奇数で、その要素を左からのインデックスの()が偶数というような要素が存在します。操作1を1回行うと、それぞれ一つづつ偶奇を反転させることができるので、をで割ったものが答えです。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


int main()
{
    int N;cin >> N;
    vector<int> v;
    map<int, int> mp;
    for(int i = 0;i < N;i++){
        int b;cin >> b;
        v.push_back(b);
        mp[b] = i;
    }
    int cnt = 0;
    for(auto a : mp){
        v[a.second] = cnt;
        cnt++;
    }
    int ans = 0;
    //for(int i = 0;i < v.size();i++)cout<<v[i]<<endl;
    for(int i = 0;i < N;i++){
        if((v.at(i) % 2) != (i % 2))ans++;
     }
    cout<<ans/2<<endl;
}