ABC148 D問題 Brick Break

昨日は、問題の考察をしながら Abema でやってた一挙放送つけてたら、一日が終わってた気がする。
○○○○が悪いんだよ… (←わかる人にはわかる)
やっぱり危機管理おもしろいなあ。(←わかる人にはわかる)
今日は、セグ木分からんって言ってたら一日が溶けてた。
セグ木が原因ではなかったが。
なんでこの貪欲法で解が求まるんだろう。

さて、昨日の D 問題、なんでこんなに早く解かれてるんだろうなあと思っていたのだが、与えられた数列なめるだけの貪欲 (計算量 : ) で済むのね、今朝気付いた。
別の方法でやってたわ…
以下のような操作が必要な問題を最近解いたので、その影響が強かったのかもしれない。
せっかくなので、雑にではあるがメモしておく。
気が向いたら説明を加えたりするかもしれない。

atcoder.jp

【問題の概要】
要素数 個の数列 が与えられる。
個以下の数字を抜き出した結果、 個残ったとすると、] について、左から 番目の数字が であるようにしたい。
このようにできるとき、削る数字の最小個数はいくらか。
不可能な場合は、 を出力。

【考察→実装】
個残したときに、 という並びができるときの の最大値を求めればよい。
問題は削る個数の最小値を聞いているので、出力は にしておく。

入力を、数列のどの位置にあるかという情報に変換する。
が存在しなければ、条件を満たす操作は不可能なので、 を出力する。

の一番左側の位置を初期値とする現在値 (now_pos) を持っておいて、 から順に現在地より右側にある位置が存在するか調べる。
存在しなければその時点でループを抜けるが、この時の (ループ変数 - 1) が求める の最大値であるので、ここで要求された値が求まる。

最悪計算量は、 (同じ数字の個数) となる。 (多分)

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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<vector<int>> pos(200005);
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        pos[a].push_back(i);    // 格納される情報は昇順に並ぶ
    }
    
    // 1 が存在しないとき
    if(pos[1].size() == 0){
        cout << -1 << endl;
        return 0;
    }
    
    // 現在地 : 1 の中で一番左側の位置
    int now_pos = pos[1][0];
    for(int i = 2; i < 200005; ++i){
        // 条件を満たす一番初めのイテレータ (満たすものがなければ end() となる)
        auto it = upper_bound(pos[i].begin(), pos[i].end(), now_pos);
        
        if(it == pos[i].end()){     // 条件を満たすものがない場合
            cout << n - (i - 1) << endl;
            return 0;
        }
        
        now_pos = *it;      // 現在地の更新
    }
}