解法 1

\(x\) はたかだか \(N\) なので，\(x=0,1,\dots,N\) のそれぞれについて，\(A\) に現れる \(x\) の個数を数えて，それが \(x\) 以上となる最大の \(x\) を出力すればよいです．

時間計算量は \(O(N^2)\) です．

実装例 (Python)

N = int(input())
A = list(map(int, input().split()))
for x in range(N, -1, -1):
    count = 0
    for a in A:
        if a >= x:
            count += 1
    if count >= x:
        print(x)
        break

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& x : A) cin >> x;
    for (int x = N; x >= 0; --x) {
        int count = 0;
        for (auto a : A) {
            if (a >= x) ++count;
        }
        if (count >= x) {
            cout << x << endl;
            break;
        }
    }
}

解法 2

まず，\(A\) を要素の降順に並べ替えて，\(A_1 \geq A_2 \geq \dots \geq A_N\) とします．これはソートと呼ばれる操作であり，多くの言語で標準機能として実装されています（C++ では std::sort, Python では sort 関数が利用できます）．

このように並べ替えると，各 \(1 \leq i \leq N\) について，\(A_i\) 以上の要素が \(i\) 個以上現れることになります．なぜならば，\(A_1,\dots,A_i\) はすべて \(A_i\) 以上だからです．

よって，\(x\) 以上の要素が \(x\) 個以上現れる最大の \(x\) は，\(A_x \geq x\) が成り立つ最大の \(x\) であり，\(A_x\) を順番に見ていくことで求めることができます．

時間計算量はソートがボトルネックとなり \(O(N \log N)\) です．本問題の制約では解法 1 でも十分高速ですが，解法 2 は \(N\) が \(10^6\) 程度でも高速に動作します．

実装例 (Python)

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
for x in range(N, 0, -1):
    if A[x - 1] >= x:
        print(x)
        break
else:
    print(0)

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& x : A) cin >> x;
    sort(A.rbegin(), A.rend());
    for (int x = N; x > 0; --x) {
        if (A[x - 1] >= x) {
            cout << x << endl;
            return 0;
        }
    }
    cout << 0 << endl;
}