【ABC409】B問題 - Citation 考察から実装(c++)まで

AtCoderBeginnerContest409の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC409】A問題 - Conflict　考察から実装(c++)まで
• 【ABC409】B問題 - Citation　考察から実装(c++)まで <- イマココ
• 【ABC409】C問題 - Equilateral Triangle　考察から実装(c++)まで
• 【ABC409】D問題 - String Rotation　考察から実装(c++)まで
• 【ABC409】E問題 - Pair Annihilation　考察から実装(c++)まで
• 【ABC409】F問題 - Connecting Points　考察から実装(c++)まで

B問題 - Citation

問題リンク

問題概要

長さ$N$の数列$A=(A_1,A_2,...,A_N)$が与えられる。以下を満たす最大の非負整数$x$を求めよ。

• $A$に、$x$以上の数が重複を含め$x$回以上現れる。

制約

• $ 1 \le N \le 100 $
• $ 0 \le A_i \le 10^9 $

考察

問題文難しくて頭壊れるぅ〜。
「最大の非負整数を求めよ」と言われてるので、一旦上界が知りたい。$A$の長さが$N$なことを考えると、$A$に$101$回以上なにかしらの数が現れることはあり得ない。
ということは、答えは必ず$0$以上$100$以下なので、もう全部チェックしちゃえばよさそう。
チェックを愚直に$O(N)$ですることにすると、計算量は$O(N^2)$

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;

int main(void){
    //入力
    ll N;
    cin>>N;
    
    vll A(N);
    for(int i=0;i<N;i++) cin>>A[i];
    
    //答えの範囲は0以上100以下なので、でかい方から見ていって最初に見つかったのが答え
    for(int x=100;x>=0;x--){
        //Aの中に、a >= xを満たすものがいくつあるか？
        ll cnt = count_if(A.begin(), A.end(), [&](ll a){ return a >= x; });
        if(cnt >= x){
            cout<<x<<endl;
            return 0;
        }
    }
}