DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 B - ディスコ社内ツアー

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選に参加しました。

なんとなく早解きコンテストになるんじゃないかと思っていましたが面白かったです。非競プロ勢には厳しかったような気がしますが。

問題

discovery2016-qual.contest.atcoder.jp

解法

広義単調増加列になるということは, まず面白さ 1 の部屋をすべて回って, 次に面白さ 2 の部屋をすべて回って, ..., 面白さ 10^5 の部屋をすべて回って, 終わりです。

今いる位置が cur で, 次に回りたい数が num であるとします。

num が登場する場所の集合を p[0], p[1], ..., p[m-1] とすると,

• cur > p[0] の時は, ぐるっと一周して p[i] < cur を満たす最大の i を見つける
• cur < p[0] の時は, p[m-1] まで移動する

これらは lower_bound 使えば各数 num について, O(log N) で実行できるので, 実行時間内に間に合います。

const int MAXN = 100010;
int A[MAXN];
vector<int> pos[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];
        pos[A[i]].push_back(i);
    }
    int cur = 0, ans = 0;
    for (int i = 1; i <= 100000; i++) {
        if (pos[i].empty()) continue;
        int size = pos[i].size();
        int index = lower_bound(pos[i].begin(), pos[i].end(), cur) - pos[i].begin();
        if (cur > pos[i][0]) {
            ans++;
            cur = pos[i][index-1];
        } else {
            cur = pos[i][size-1];
        }
    }
    if (cur != 0) ans++;
    cout << ans << endl;
    return 0;
}