東京工業大学プログラミングコンテスト2015 I - そーっとソート

これほんと感動しました。

問題

ttpc2015.contest.atcoder.jp

解法

右端から揃えていく感じでやります。

例えば, 4, 2, 5, 3, 1 という順列があったとします。右端は 5 にしたいですが, 5 になっていないので右端の 1 を動かします。ルールにより, 1 の場所から 1 だけずれてる 3 と交換します。
4 2 5 3 1 -> 4 2 5 1 3
右端は 3 になりましたが, これも目的と違います。ということで, 動かします。さらに動かします。
4 2 5 1 3 -> 4 3 5 1 2 -> 4 3 2 1 5
ここで, 右端が 5 になってくれました。嬉しいです。これを 4, 3, 2, 1 とやっていけば良いです。

このようなアルゴリズムでは, N を右端に揃えたい場合, たかだか N 回の操作で N が右端に来ることが保証されるので, 十分指定された回数以内に間に合います。

const int MAXN = 55;
int A[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<pii> ps;
    int cur = N-1;
    while (cur >= 0) {
        while (A[cur] != cur+1) {
            ps.emplace_back(cur, cur-A[cur]);
            swap(A[cur], A[cur-A[cur]]);
        }
        cur--;
    }
    cout << ps.size() << endl;
    for (auto p : ps) {
        cout << p.first+1 << " " << p.second+1 << endl;
    }
    return 0;
}