Official
C - Max MEX Editorial by physics0523
全ての非負整数 \(x\) について以下が成り立ちます。
\(MEX\) を \(x+1\) 以上にするには \(x\) を \(B\) の要素として選ぶ必要があります。逆に、要素が重複しても \(MEX\) には影響しないため、 \(x\) を \(2\) つ以上選ぶメリットはありません。
このことから、次のアルゴリズムが成立する。
- \(i=0,1,\dots,K-1\) まで、以下を繰り返す。
- もし \(A\) に \(i\) が含まれる場合、それを選び出す。これにより、答えが \(i+1\) 以上となることが確定する。
- そうでない場合、 \(MEX\) の値を \(i\) より大きくすることはできないため、答えが \(i\) であると判明して終了する。
- 上記が終了しても答えが判明しなかった場合、 \(B\) を \((0,1,\dots,K-1)\) の並べ替えとすることができているので、答えは \(K\) である。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin >> n >> k;
set<int> st;
for(int i=0;i<n;i++){
int a;
cin >> a;
st.insert(a);
}
for(int i=0;i<k;i++){
if(st.find(i)==st.end()){
cout << i << "\n";
return 0;
}
}
cout << k << "\n";
return 0;
}
posted:
last update: