CS Academy: Sorting Steps

公式の解説が鮮やかだったけど、英語がちょっと読みにくかったので日本語解説を作ってみたくなりました。

問題概要

原文 → CS Academy

長さ の配列をバブルソートすることを考える (どんな実装かは、原文にサンプルコードがあるのでそちらを参照してください)。

ソートが完了した時の、"steps" の値を出力せよ。

解説

なんとなくセグ木とかを使いたい気持ちになりますが、公式の解説を見るとソートをするだけで解いているのでビックリです。どうやれば解けるのか、詳しく見ていきましょう。なお、説明のため、 := 配列の 番目の値 とします。 (ここからの内容はほぼ公式解説と同じです)

まず、 := 番目の要素より左にあり、かつ値が よりも大きい要素の個数 と定義します。もしも全ての について ならば、既にソート済みです。

ここで重要な考察として、バブルソートを ステップ進めると、 を満たす全ての の値がそれぞれ 減少します。 なぜなら、それを満たす要素それぞれについて、自分より左にある要素の中で最大の要素とスワップされ、自分より左にあって自分より大きい要素の個数が 個減るからです。全ての の値が (= ソート済み) になるために必要なステップ数が 回であることは明らかなので、あとは を求められれば OK です。

全ての を求めるのであれば前述の通りセグ木等を使う必要がありますが、今回必要な値は だけなので、もっとシンプルに解くことができます。

まず、どのような要素が の候補になりえる・またはなりえないかを考えます。これについて、 ソート前配列の 番目の要素について、その右に自分より小さい要素があるならば、 が になることはない という重要な考察ができます。

これを簡単に証明します。 であって である組 を考えます。このとき、 の計算において 番目の要素を考慮すると が成り立つことがわかります。これにより、自分より小さい要素が自分より右にあるならば の候補になりえないことが示せました。 (個人的にここの部分が一番巧妙だと思います。)

つまり、 の候補になる要素は、 自分より小さい要素全てが自分より左の位置にあること を満たす必要があります。そしてそのような候補について、 は (ソート済みの状態であるときのインデックス) - (ソート前の状態であるときのインデックス) で計算できます。よって、元のインデックスの情報を保持しながら配列をソートして、前述の計算の を取れば良いです。

ソースコード

ほぼ Writer 解と同じですが・・・。

signed main() {
    int N; cin >> N;
    vector<pii> v(N);
    rep(i,0,N) {
        int p; cin >> p;
        v[i] = make_pair(p, i);
    }
    sort(v.begin(), v.end());

    int ans = 0;
    rep(i,0,N) {
        chmax(ans, v[i].second - i);
    }
    cout << ans + 1 << endl;
    return 0;
}

こういうシンプルな考察ができる頭になりたい。