AtCoder が提供しているABC（AtCoder Beginner Contest）290 のC問題をC++とPythonで解いてみました。ABC290は、2023年2月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Max MEX（Difficulty : 225）
問題はリンク先をご覧ください。
与えられた数列から重複する要素を抜いて、ソートすることによって解答を求めます。AtCoder Problems による Difficulty は 225 でした。
問題名にある “MEX” は、Minimum EXclude だと思われます。
解答案
問題文を読んだ時点では、問題が理解できませんでした。このような場合は、入力例と出力例、その解説を読むことにします。
例の解説から、以下の手順で解答が求められることが分かりました。問題文にある「順序を保ったまま抜き出した列」は、MEX(B) を求めるには、関係ない情報でした。
- 入力例の数列
2 0 2 3 2 1 9 - 重複する要素を除く。
2 0 3 1 9 - ソートする。
0 1 2 3 9 - 0 からカウントアップして連続となる数の個数（4個）と K（3）を比較して小さい数である 3 を出力する。（K 要素しか選ばないため）
C++ プログラム例（ABC290C）
C++ の set コンテナはソートした順に取り出せるため、set を使います。0 から連続してカウントアップする上限を求めて、K と比較して小さい数を解答として出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
set<int> a;
for (int i = 0; i < n; ++i) {
int temp;
cin >> temp;
a.insert(temp);
}
int result = 0;
for (auto e : a) {
if (e == result) {
++result;
} else {
break;
}
}
result = min(result, k);
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC290C）
Python では、リストから set で重複を除いて、ソートしました（3-5行目）。プログラムの構造は、C++ で紹介したプログラムと同じです。
"""AtCoder Beginner Contest 290 C"""
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = list(set(a))
a.sort()
result = 0
for i in range(len(a)):
if a[i] == result:
result += 1
else:
break
result = min(result, k)
print(result)C++とPythonでは、C++の方が速く動くことが多いです。この問題で紹介したプログラムは、Python版の方が速く動きました。C++は、setコンテナで処理をしていますが、Python版は、setを経由していますがリストで処理していることが関係しているかもしれません。
こちらも「AC」と判定されました。
最後に
例を調べることで問題の構造が理解できました。
引き続き ABC の問題を紹介していきます。
