AGC003-C：BBuBBBlesort!

問題

https://beta.atcoder.jp/contests/agc003/tasks/agc003_c

長さ N の数列 a_N が与えられる。以下の操作をして、数列を単調増加にするよう並べ替える時、操作 1 の最小回数を求めよ。

1. 数列の連続する 2 つの要素を選び、その 2 つの順番を反転する。
   
2. 数列の連続する 3 つの要素を選び、その 3 つの順番を反転する。
   

考え方

操作 2 を考えると、偶奇ごとに数を swap するのは任意にしてよいことがわかる。
ソート後の数列を考えると、もとの数列とソート後の数列で index の偶奇が異なる数 a_i については少なくとも 1 回は操作 1 によって偶奇を入れ替えなければならない。偶数ごと奇数ごとの swap は任意にできるので、偶奇を入れ替えるための操作は高々 1 回でよいことがわかる。

また、ある数 a_i について、もとの数列の index とソート後の数列の index の偶奇が異なる場合、別のある 1 つの数 a_j についても偶奇が異なる。a_i と a_j の 2 つの数は 1 回の操作 1 で同時に偶奇を揃えることができる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] a = in.nextIntArray(n);
            int[] as = a.clone();
            Arrays.sort(as);

            long ans = 0;
            for (int i = 0; i < n; i++) {
                int idx = Arrays.binarySearch(as, a[i]);
                if (abs(i - idx) % 2 == 1) ans++;
            }

            out.println(ans/2);
        }

ポイント

• 満たすべき状態を考える

類題

雑記

偶奇ごとの数列に分けてソートした後、1の操作で転倒数を求めればよいのかな、、、と思いましたが違いました()