ABC194E Mex Min

昨晩はABC194E Mex Minに取り組みました。

E - Mex Min

ある数字が数列の何番目にでてくるかを保持する配列を準備し，0から順に候補を試し，配列の要素間の距離がMを超える場合，もしくはその候補がない（配列のサイズが0）の場合，その候補を出力する，という方針でACしました。
配列の位置の数は配列の要素の数と同じなので，計算量はほぼＯ（Ｎ）。

最後にWAが取れずに少し苦労したのが終端の処理でした。
最後の要素と終端の距離がMあればansになるので要素数から現在位置を引いた値とMを比較して判定するようにしてクリアー。

    if(n-temp>=m){
      cout<<i<<endl;
      return 0;
    }   

提出コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
  int n,m;
  cin>>n>>m;
  vector<int>a(n+2);
  a[0]=0;
  a[n+1]=0;
  int maxa=0;
  rep(i,n){
    cin>>a[i+1];
    maxa=max(maxa,a[i+1]);
  }
  set<int>is[maxa+2];
  rep(i,n+2){
    is[a[i]].insert(i);
  }
  rep(i,maxa+2){
    if(is[i].size() ==0){
      cout<<i<<endl;
      return 0;
    }
    int temp=0;
    for(auto e=is[i].begin();e != is[i].end();e++){
      if(*e-temp>m){
        cout<<i<<endl;
        return 0;
      }
      else{
        temp=*e;
      }
    }
    if(n-temp>=m){
      cout<<i<<endl;
      return 0;
    }   
  }
  return 0;
}

本番で見たとき非常に難しく感じたのに緑difで驚いたのですが，一昨日あたりに取り組んだABC157E Simple String Queriesで文字列中に文字が現れる場所の集合を管理する方法を学んでいたので，今回は簡単に感じました。Simple String Queriesは水difでしたので，みんなしっかり精進しているんだなあと思いました。

Editorial - AtCoder Beginner Contest 157