B. Uniqueness

1500
  • Quiz
  • AC
  • 解説
    • editorialの方が賢いですが、別解法で解いたので書いておきます
    • 削る長さが大きいほど条件を満たしやすくなり、条件を満たす・満たさないの単調性があるので「長さl削る場合に条件は達成できるか？」の判定関数で二分探索します
    • 制約nが小さいのでナイーブに実装してみるとTLE。除去する範囲を1つずつずらしながら、直前の結果を利用して効率化するとACです
int main(){
    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];

    {
      set<ll> se;
      for(ll a : A) se.insert(a);
      if(se.size()==N){
        p(0);
        return 0;
      }
    }

    auto check = [&](ll center){
      map<ll,ll> mp;
      FOR(i,center,N) mp[A[i]]++;
      if(mp.size()==N-center) return true;

      rep(i,N-center){
        mp[A[i]]++;
        ll remove = A[i+center];
        mp[remove]--;
        if(mp[remove]==0) mp.erase(remove);
        if(mp.size()==N-center) return true;
      }
      return false;
    };

    ll left = 0; // ng
    ll right = N-1; // ok

    while(left+1!=right){
      ll center = (left+right)/2;
      if(check(center)){
        right = center;
      }else{
        left = center;
      }
    }
    p(right);
    
    return 0;
}