AtCoder

ABC304 D問題(A Piece of Cake)を解く

AtCoder_ABC304_D

AtCoder が提供しているABC(AtCoder Beginner Contest)304 のD問題をC++とPythonで解いてみました。ABC304は、2023年6月3日21:00に実施されました。

この回は、サーバ攻撃を受けてジャッジ遅れが大きく発生したため、unrated となりました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 A Piece of Cake(Difficulty : 1015)

問題はリンク先をご覧ください。

ABC304 D問題 A Piece of Cake

イチゴがどのピースにあるかを二分探索を使って求めます。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)$ となり、時間的に間に合いません。コンテストでは解くことができず公式解説をみて、二分探索を使うことに気づきました。二分探索は応用範囲が広いと感じました。

ABC304 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA