AtCoder が提供しているABC（AtCoder Beginner Contest）317 のB問題をC++とPythonで解いてみました。ABC317は、2023年8月26日21:00に実施されました。
ABC316は欠番になりました。AtCoderからのお知らせはこちらです。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 MissingNo.（Difficulty : 22）
問題はリンク先をご覧ください。
問題に与えられた数列から、抜けている数値を求める問題です。AtCoder Problems による Difficulty は 22 でした。
解答案
C++ プログラム例（ABC317B）
問題から、数列に途中で抜けている数字があることが分かります。与えられた数列に抜けがないと、その数列の両端よりひとつ小さい数字と大きい数字が解となり一意となりません。
与えられた数列をソートして、ループを使って調べます。$a_i + 1$ が $a_{i+1}$ になっていなければ、$a_i + 1$ が解となります（16、17行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
int result = 0;
for (int i = 0; i < n - 1; ++i) {
if (a[i] + 1 != a[i + 1]) {
result = a[i] + 1;
}
}
cout << result << endl;
return 0;
}
AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC317B）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 317 B"""
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n - 1):
if a[i] + 1 != a[i + 1]:
result = a[i] + 1
print(result)こちらも「AC」と判定されました。
最後に
ABC317A問題でも書きましたが、今回のコンテストは「各1枚限定！AtCoderコンテスト限定ポストカード（全151種類）」が特典でした。対象の条件のひとつに「1問以上正解していること」があります。この問題もB問題としては難易度が抑えられている気がします。
1問以上解けている対象者は8555人でした。上位16人には順位特典として与えられて、残りは抽選特典としてプレゼントされるようです。$(151-16)/(8555-16) = 1.58％$ となります。他の条件もあるので、もう少し抽選に当たる確率は上がると思います。楽しみにしています。
引き続き ABC の問題を紹介していきます。
