AtCoder が提供しているABC（AtCoder Beginner Contest）322 のC問題をC++とPythonで解いてみました。ABC322は、2023年9月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Festival（Difficulty : 128）
問題はリンク先をご覧ください。
二分探索を使って解きました。AtCoder Problems による Difficulty は 128 でした。
解答案
C++ プログラム例（ABC322C）
C問題としては、取り組みやすい難易度です。
花火が上がる日は、すでにソートされているため、$i = 1, 2, \dots, N$ に対して、upper_bound で、$i$ 以上の直近の花火が上がる日を求めて、$i$ を引くことによって、解答を求めることができます（14行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
auto it = lower_bound(a.begin(), a.end(), i);
cout << *it - i << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC322C）
二分探索は、bisect モジュールを使うと楽です。
- bisect.bisect_left は、C++の lower_bound に該当します。
- bisect.bisect_right は、C++の upper_bound に該当します。
この問題では、bisect.bisect_left を使います（8行目）。考え方はC++版と同じです。
"""AtCoder Beginner Contest 322 C"""
import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(1, n + 1):
j = bisect.bisect_left(a, i)
print(a[j] - i)こちらも「AC」と判定されました。
最後に
ABC322は、C問題までは取り組みやすい難易度でした。結果的にC問題までの3問までしか、解けませんでした。
C問題は、14:22 でAC判定をもらえました。このような問題間で難易度の差があるコンテストでは、わたしのレートでは、解きやすい問題を速く解くことが重要だと感じました。最終的にパフォーマンス 872 で、それほどレートが落ちませんでした。
引き続き ABC の問題を紹介していきます。
