2015-11-21

はじめに

Codeforces Round #332 Div. 2 Prob. C. Day at the Beach

問題：http://codeforces.com/contest/599/problem/C

解けなかったのでブログに書いておく。

考え方

重複がある数列をソートしたいとき、ある区間でのソートが全体でのソートと一致した数列になるかどうか、という問題はその区間での各数字の出現回数が一致することを調べればよい。

→mapで数えて一致するかどうかを確認する。毎回map全部数えても間に合うようだけどマンハッタン距離を持つようにしたら早くなりそう。

→別解：ソート前とソート後の配列の、同じ区間同士を比べている、ということを用いると複数の解法がある。例えば（左からなめるなら）lmaxとrminを比べるなど。

まったく気づかなかった。RMQを使うことを考えたり（ライブラリにないので途中まで実装したり）、右方向、左方向に貪欲で区間分けしていって統合することを考えたりしていたら時間切れ。

解答

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);

    long long n;
    cin >> n;

    vector<long long> h(n,0);
    for(int i = 0; i < n; ++i){
        cin >> h[i];
    }

    vector<long long> sorted_h(h);
    sort(sorted_h.begin(), sorted_h.end());

    map<long long,long long> counts;

    long long diff=0,ret=0;
    for(int i = 0; i < n; ++i){
        if(counts.find(h[i]) == counts.end()){
            counts[h[i]]=0;
        }

        diff-=abs(counts[h[i]]);
        counts[h[i]]+=1;
        diff+=abs(counts[h[i]]);

        if(counts.find(sorted_h[i]) == counts.end()){
            counts[sorted_h[i]]=0;
        }

        diff-=abs(counts[sorted_h[i]]);
        counts[sorted_h[i]]-=1;
        diff+=abs(counts[sorted_h[i]]);

        if(diff==0) ret+=1;
    }

    cout << ret << endl;

    return 0;
}

テストケース

6
3 1 2 2 5 6
>>> 3

Chiranoura

Codeforces#332 Div2 C問題

はじめに

考え方

解答

テストケース