AOJ 0353 Sort

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0353

解法

とりあえず観察しないとよくわからない。
僕は観察してもよくわからなかったので、確実に言えることを探すことにした。
まず、一番小さい数は、左端に到達したら以降はもう動かない。その後に、二番目に小さい数が左から二番目の位置に到達したら以降は動かない。以下同様。
この事実を使うなら、まだ位置が確定していない値のうちで、最も小さい値が目的の位置に移動するまでにどのような変化が起こるか観察すべきだ。
そこで、次に位置を確定させる値に注目したとして、その値が適切な位置に移るまでを考える。
1 から i - 1 番目までは確定しているとする。次に注目するのは i 番目に小さい数である。その数が位置 j にあるとしよう。
この数が位置 i に到達するまでに発生するスワップ回数は、j - i 回である。これは考えてみると当然である。
これは、i から j 番目までの数字の並びは、スワップ回数に全く関係ないことを意味する。したがって、次に注目したい数が今どの位置にあるのかさえわかればよい、ということにほかならない。
この位置を効率よく探索するにはどうすればよいだろうか？要素がごっそり移り変わるので、単純なセグツリを使うということはできない（平衡二分木なら可能かも）。
これを考えるためには、後ろに追いやった数の並びについて、確実に言えることはなにかに注目しなければならない。
そして、いろいろ試すとわかるが、後ろに追いやられた値の全体としての並びは複雑でつらい気持ちになる。
しかしよく観察すると、後ろに追いやられた数の中で最小の値は、常に末尾に存在することに気がつく。
我々が必要なのは次に確定させたい値、それはつまり（選んでない中で）一番小さな値であり、その候補となる値以外の位置はどうでも良い。
そしてその候補となるのが、後ろに追いやった数の集合で最も小さい値である。
それらの位置は、前から位置を確定させるごとに後ろに追いやった数の集合の要素数さえわかれば、累積和の要領で求めることができる。

これまでの考察から、以下の解法を得る。

小さい値から順に注目し、前から位置を確定させていく。
このとき、注目した値を目的の位置に移るまでに後ろに追いやる数の集合をまとめ上げてしまう。この集合は、含まれる中で最も小さいものを得られるようなものにする（priority_queue など）。
注目した値が適切な位置に至るまでのスワップ回数は、まとめ上げた集合の要素数（の合計）に等しい。ただし注目している値自身は除く。
以降、この集合は分解することなく管理する。次に確定させる値のときも同様に、自身の位置から目的の位置までにある集合をまとめ上げ、自分以外を後ろに追いやるようにする。
これを最後の要素になるまで繰り返すと、答えが得られる。
集合のまとめ上げにマージテクを行えば、O(N(logN)^2) で解ける。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    { // compress
        auto b = a;
        sort(begin(b), end(b));
        for(int i = 0; i < n; ++i) {
            a[i] = lower_bound(begin(b), end(b), a[i]) - begin(b);
        }
    }

    using S = priority_queue<int, vector<int>, greater<>>;
    function<void(S&, S&)> merge = [] (S& s1, S& s2) {
        if(s1.size() < s2.size()) swap(s1, s2);
        while(!s2.empty()) {
            s1.push(s2.top()); s2.pop();
        }
    };

    queue<shared_ptr<S>> que;
    for(int i = 0; i < n; ++i) {
        auto q = make_shared<S>(); q->push(a[i]);
        que.push(move(q));
    }
    ll ans = 0;
    for(int i = 0; i < n; ++i) {
        auto s = que.front(); que.pop();
        while(s->top() != i) {
            auto v = que.front(); que.pop();
            merge(*s, *v);
        }
        s->pop();
        ans += s->size();
        que.push(s);
    }

    cout << ans << endl;
}

感想

難しい。解説するのも（言葉だけだと）難しい。
かといって図を載せて解説する元気もなく…（公式解説を読んでください）。
よくこんな問題思いつくなあ。