AtCoder が提供しているABC（AtCoder Beginner Contest）304 のD問題をC++とPythonで解いてみました。ABC304は、2023年6月3日21:00に実施されました。
この回は、サーバ攻撃を受けてジャッジ遅れが大きく発生したため、unrated となりました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 A Piece of Cake（Difficulty : 1015）
問題はリンク先をご覧ください。
イチゴがどのピースにあるかを二分探索を使って求めます。AtCoder Problems による Difficulty は 1015 でした。
解答案
問題文にあるように $(A + 1) \times (B + 1)$ 個のピースにケーキを分割します。$1 \leqq A, B \leqq 2 \times 10^5$ です。このため、それぞれのピースに載っているイチゴの数を求めることは、計算量的に間に合いません。参考までに、計算量（演算回数）の目途は、$10^8$ です。
二分探索を行う関数 lower_bound を使います。この関数により、$a_0, a_1, \cdots, a_{n-1}, W$ のどこに $p_i$ があるかを求めることができます。これはピースの右座標となります。
同じように $b_0, b_1, \cdots, b_{n-1}, H$ のどこに $q_i$ があるかを求めることができます。これはピースの上座標となります。
補足：$x$ 座標の値は右に、$y$ 座標の値は上に向かって増えていくとします。
それぞれのイチゴがどこのピースに載っているかを $\log(A) + \log(B)$ で求めることができます。あとは、map を使って、解答を求めることができます。
C++ プログラム例（ABC304D）
上記の考察に従い、実装します。
最小値については注意が必要です。map のサイズが、$(A + 1) \times (B + 1)$ より少なければ、最小値は 0 となります（44行目）。$(A + 1) \times (B + 1)$ は、32ビット整数の範囲より大きくなる可能性があることに注意します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int w, h;
cin >> w >> h;
int n;
cin >> n;
vector<int> p(n), q(n);
for (int i = 0; i < n; ++i) {
cin >> p[i] >> q[i];
}
int na;
cin >> na;
vector<int> a(na + 1);
a[na] = w;
for (int i = 0; i < na; ++i) {
cin >> a[i];
}
int nb;
cin >> nb;
vector<int> b(nb + 1);
b[nb] = h;
for (int i = 0; i < nb; ++i) {
cin >> b[i];
}
map<pair<int, int>, int> m;
for (int i = 0; i < n; ++i) {
auto itx = lower_bound(a.begin(), a.end(), p[i]);
auto ity = lower_bound(b.begin(), b.end(), q[i]);
++m[make_pair(*itx, *ity)];
}
int result_min = n + 1;
int result_max = -1;
for (auto e : m) {
result_min = min(result_min, e.second);
result_max = max(result_max, e.second);
}
if (((long long)na + 1) * ((long long)nb + 1) > m.size()) {
result_min = 0;
}
cout << result_min << " " << result_max << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC304D）
C++ の map の替わりに collections モジュールの defaultdict を、lower_bound の替わりに bisect モジュールの bisect_left を使います。
"""AtCoder Beginner Contest 304 D"""
from collections import defaultdict
import bisect
w, h = map(int, input().split())
n = int(input())
p = []
q = []
for i in range(n):
tp, tq = map(int, input().split())
p.append(tp)
q.append(tq)
na = int(input())
a = list(map(int, input().split()))
a.append(w)
nb = int(input())
b = list(map(int, input().split()))
b.append(h)
m = defaultdict(int)
for i in range(n):
x = bisect.bisect_left(a, p[i])
y = bisect.bisect_left(b, q[i])
m[(x, y)] += 1
result_min = n + 1
result_max = -1
for v in m.values():
result_min = min(result_min, v)
result_max = max(result_max, v)
if (na + 1) * (nb + 1) > len(m):
result_min = 0
print(result_min, result_max)こちらも「AC」と判定されました。
最後に
素朴な方法は計算量が $O(N^2)$ となり、時間的に間に合いません。コンテストでは解くことができず公式解説をみて、二分探索を使うことに気づきました。二分探索は応用範囲が広いと感じました。
引き続き ABC の問題を紹介していきます。
