AtCoder が提供しているABC（AtCoder Beginner Contest）312 のC問題をC++とPythonで解いてみました。ABC312は、2023年7月29日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Invisible Hand（Difficulty : 727）
問題はリンク先をご覧ください。
解の二分探索を用いて解くことができます。AtCoder Problems による Difficulty は 727 でした。
解答案
二分探索で求めることができます。めぐる式と呼ばれる二分探索の実装を参考にしました。ABC299D問題（解説）、ABC309C問題（解説）でも解説しています。
C++ プログラム例（ABC312C）
売ってもよい値段の配列 a と買ってもよい値段の配列 b を読み込んでソートしておきます。めぐる式二分探索の考え方は、29行から39行目で表現されています。このコードは共通で使えます。関数 is_OK と変数 ng と ok の初期値を変更すれば、いろいろな解の二分探索を行うことができます。
関数 is_OK の考え方は以下です。
- 「X 以下の配列 a の要素数」を seller とします。これは、X 円で売ってよい人数となります（10行目）。seller を求めるために upper_bound を使います。
- 「X 以上の配列 b の要素数」を buyer とします。これは、X 円で買ってよい人数となります（11行目）。buyer を求めるために lower_bound を使います。
- seller >= buyer の値を返します（12行目）。
変数 ok の初期値は、109 + 1 にしています（30行目）。これは、以下の入力例の場合、109 + 1 が解になるためです。解が 109 + 1 になるテストケースがコンテストにあり、この初期値を 109 にすると、1つのテストケースでWA（Wrong Answer）判定となります。
1 2
1000000000
1000000000 1000000000以下が、最終的なC＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a;
vector<int> b;
bool is_OK(int mid)
{
int seller = upper_bound(a.begin(), a.end(), mid) - a.begin();
int buyer = m - (lower_bound(b.begin(), b.end(), mid) - b.begin());
return seller >= buyer;
}
int main()
{
cin >> n >> m;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
b.resize(m);
for (int i = 0; i < m; ++i) {
cin >> b[i];
}
sort(b.begin(), b.end());
int ng = 0;
int ok = 1000000001;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC312C）
Python 版は C++ 版を移植しました。seller と buyer を求めるために bisect モジュールを使いました。
"""AtCoder Beginner Contest XXX Y"""
import bisect
def is_OK(mid):
global m
seller = bisect.bisect_right(a, mid)
buyer = m - bisect.bisect_left(b, mid)
return seller >= buyer
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = list(map(int, input().split()))
b.sort()
ng = 0
ok = 10 ** 9 + 1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_OK(mid):
ok = mid
else:
ng = mid
print(ok)どちらも「AC」と判定されました。
最後に
最初、解の二分探索の考え方を学んだときには難しく感じましたが、慣れてきて問題を解くことができるようになりました。
引き続き ABC の問題を紹介していきます。
