AtCoder Regular Contest 031 C - 積み木

問題

　全て高さが違う個の積み木が1列に並べられている。隣り合う積み木を交換する操作ができるとき、一番高い積み木から順に左右へ低くなっていくような状態へ変化させるのに必要な最小の操作回数を求めよ。

解法

　一番大きな積み木から位置を確定させていくとして、ある積み木を確定させるときには今の位置から左側、右側について自分より大きな積み木がある個数がわかれば、小さい方へ交換していけばいい。これはBinary Indexed Treeを用いることでで求めることができるので、全体でこの問題が解けた。

反省

　1時間43分(0WA)でAC。最初の30分くらいは眠くて何も考えられなかった。そこからバブルソートの交換数みたいな感じで、自分より大きいものの数が重要になってくるんだろうというところまでは考察できた。一番高い積み木の位置を決めて、左右についてまず求めて、一番高い積み木の位置をずらしたときの差分を計算していくことでとかにならないかなと考えていたものの、わからなかったので1時間15分くらい経ったところで解説スライドを見た。

　BinaryIndexedTreeを知らなかったのでこのページとかを調べて実装する。1-indexというのが厄介でちょっと手間取ったりした。(i & -i)で最右ビットが求めるのすごい。

　小さい方から確定させていくというのがよくわからなくて、結局大きい方から確定させていく方針で通した。小さい方からやっていく場合BITの値を直接いじらないといけないのかな？

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class BinaryIndexedTree {
public:
    //1-indexed
    //(i & -i)はその番号が管理する区間の長さを表す
    //参考:http://hos.ac/slides/20140319_bit.pdf
    BinaryIndexedTree(ll n) : bit_(n + 1, 0) {}
    void add(ll a, ll w) {
        for (ll i = a; i < bit_.size(); i += (i & -i)) {
            bit_[i] += w;
        }
    }
    ll sum(ll a) {
        ll result = 0;
        for (ll i = a; i > 0; i -= (i & -i)) {
            result += bit_[i];
        }
        return result; 
    }
private:
    vector<ll> bit_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> B(N);
    vector<ll> index(N + 1);
    for (ll i = 0; i < N; i++) {
        cin >> B[i];
        index[B[i]] = i + 1;
    }

    BinaryIndexedTree bit(N);

    ll ans = 0;
    for (ll i = N; i >= 1; i--) {
        ll left = bit.sum(index[i]);
        ll right = N - i - left;
        ans += min(left, right);
        bit.add(index[i], 1);
    }

    cout << ans << endl;
}