ABC302 D問題（Impartial Gift）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）302 のD問題をC++とPythonで解いてみました。ABC302は、2023年5月20日21:00に実施されました。

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

D問題 Impartial Gift（Difficulty : 682）

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

ABC302 D問題 Impartial Gift

二つの数列から大きい数字を選択して条件を満たすか判定する問題です。AtCoder Problems による Difficulty は 682 でした。

解答案

A の一番大きな要素 A_max と B の一番大きな要素 B_max に対して、A_max と B_max の差が D 以下であれば、この組が解となります。明らかに、A_max + B_max より大きな組み合わせは存在しないためです。

A_max と B_max の差が D より大きな場合は、以下となります。

• A_max >= B_max の場合、A_max は解の候補になりません。これは、A_max と他の B_i との差が D より大きくなるためです。A_max を候補から外して、次に大きな A を A_max とします。
• 逆に B_max >= A_max の場合、B_max は解の候補になりません。これは、B_max と他の A_i との差が D より大きくなるためです。B_max を候補から外して、次に大きな B を B_max とします。

上記の操作で A の要素か B の要素かどちらか一方は減るため、操作の最高回数は、2 × 2 × 10⁵ となり間に合います。

C++ プログラム例（ABC302D）

考察をそのままプログラムにしました。

まず、A と B をソートします（21、22行目）。

A と B の要素どちらかの要素が残っている間、以下の操作を行います。

• A の最大値（max_a）と B の最大値（max_b）を vector のメソッド back で取り出す。
• その差が D 以下であれば、その和が解となり、ループを抜ける。
• max_a が max_b より大きければ、max_a を pop_back で取り除く、そうでなければ、max_b を pop_back で取り除く。

解が見つからないときは、result の初期値 -1 を出力します。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

int main()
{
	int n, m;
	ll d;
	cin >> n >> m >> d;

	vector<ll> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<ll> b(m);
	for (int i = 0; i < m; ++i) {
		cin >> b[i];
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	ll result = -1;
	while ((a.size() != 0)&&(b.size() != 0)) {
		ll max_a = a.back();
		ll max_b = b.back();
		if (abs(max_a - max_b) <= d) {
			result = max_a + max_b;
			break;
		}
		if (max_a > max_b) {
			a.pop_back();
		} else {
			b.pop_back();
		}
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC302D）

Python の pop は、最後の値を取り出す場合は、添え字 -1 が使えます（11、12行目）。また pop が値を返して値を削除するため、max_a と max_b の大きさによって append で書き戻しています（16-19行目）。

"""AtCoder Beginner Contest 302 D"""
n, m, d = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort()

result = -1
while len(a) != 0 and len(b) != 0:
    max_a = a.pop(-1)
    max_b = b.pop(-1)
    if abs(max_a - max_b) <= d:
        result = max_a + max_b
        break
    if max_a > max_b:
        b.append(max_b)
    else:
        a.append(max_a)

print(result)

こちらも「AC」と判定されました。

最後に

この問題は、小さい方から考えていてコンテスト中は解くことができませんでした。公式解説を参考にしました。大きな方から考えればすっきりと解くことができました。しゃくとり法そのものではありませんが、考えが近いため、「しゃくとり法」にタグ付けしました。

引き続き ABC の問題を紹介していきます。