AtCoder が提供しているABC（AtCoder Beginner Contest）382 C問題をC++とPythonで解いてみました。ABC382は、2024年11月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Kaiten Sushi（Difficulty : 476）
問題の詳細は、リンク先をご覧ください。
累積最小値を計算して、それを利用して二分探索を行います。AtCoder Problems による Difficulty は 476 でした。
解答案
美食度の条件（$B_j \geqq A_i$）を満たす番号が少ない人に寿司を割り当てます。人の美食度の累積最小値と、累積最小値を更新する人の番号を記録しておきます。累積最小値は降順にソートしておきます。
それぞれの寿司に対して、累積最小値を超える美食度を満たす人を二分探索で探します。
C++ プログラム例（ABC382C）
上の方針に従い実装しました。
- 配列
aの累積最小値min_aを求めます。累積最小値を更新する人の番号を map コンテナtに格納します（17ー26行目）。 - 累積最小値
min_aを降順にソートします（27行目）。 - 各寿司に対して、食べる人を調べます。
- 累積最小値から、寿司を食べる人を二分探索で探します（31行目）。
- 該当がなければ -1 を、該当があれば
tから食べる人の位置を求めます（32ー36行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> b(m);
for (int i = 0; i < m; ++i) {
cin >> b[i];
}
vector<int> min_a(n);
min_a[0] = a[0];
map<int, int> t;
t[min_a[0]] = 1;
for (int i = 1; i < n; ++i) {
min_a[i] = min(min_a[i - 1], a[i]);
if (t.find(min_a[i]) == t.end()) {
t[min_a[i]] = i + 1;
}
}
sort(min_a.begin(), min_a.end(), greater<int>());
vector<int> result(m);
for (int i = 0; i < m; ++i) {
auto it = lower_bound(min_a.begin(), min_a.end(), b[i], greater<int>());
if (it == min_a.end()) {
result[i] = -1;
} else {
result[i] = t[*it];
}
}
for (int i = 0; i < m; ++i) {
cout << result[i] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC382C）
Python版も基本的な考え方は同じです。二分探索は、bisect.bisect_left を使いました。昇順データを処理するため、負の値を格納しています。以下がプログラムです。
"""AtCoder Beginner Contest 382 C"""
import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
min_a = [0] * n
min_a[0] = -a[0]
t = {}
t[min_a[0]] = 1
for i in range(1, n):
min_a[i] = max(min_a[i - 1], -a[i])
if min_a[i] not in t:
t[min_a[i]] = i + 1
min_a.sort()
result = [0] * m
for i in range(m):
it = bisect.bisect_left(min_a, -b[i])
if it == n:
result[i] = -1
else:
result[i] = t[min_a[it]]
for i in range(m):
print(result[i])こちらも「AC」と判定されました。
最後に
コンテストでは、配列Bの要素数を誤って $N$ として、一度WA（Wrong Answer）となりました（正しくは $M$）。このようなミスは減らしたいです。
引き続き ABC の問題を紹介していきます。
