ABC388 E問題（Simultaneous Kagamimochi）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）388 E問題をC++とPythonで解いてみました。ABC388は、2025年1月11日21:00に実施されました。

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

E問題 Simultaneous Kagamimochi（Difficulty : 1068）

問題の詳細は、リンク先をご覧ください。

ABC388 E問題 Simultaneous Kagamimochi

餅を大きい組と小さい組に分けて貪欲法で処理します。AtCoder Problems による Difficulty は 1068 でした。

解答案

次のような貪欲法を考えます。

貪欲法1
餅を大きい方から処理する、その半分以下のもっとも大きい餅から組にしていく。

貪欲法1の反例）「2, 3, 4, 8」を考える。8 に対して半分以下で最も大きいのは4となりこれを抜いた「2, 3」は鏡餅にならない。一方、「2, 4」と「3, 8」と2つの鏡餅を作ることができる。

貪欲法2
餅を小さい方から処理する、その2倍以上のもっとも小さい餅から組にしていく。

貪欲法2の反例）「1, 2, 3, 4」を考える。1 に対して2倍以上で最も小さいのは2となりこれを抜いた「3, 4」は鏡餅にならない。一方、「1, 3」と「2, 4」と2つの鏡餅を作ることができる。

どちらの貪欲法もうまく行きませんでした。正解は以下となります。

正解の貪欲法
餅を大きい餅と小さい餅の集合に個数が半分になるように分ける。小さい餅の集合の小さい餅から処理をする。この餅の2倍以上の最小の餅を大きい餅の集合から選んで組にする。これは小さい餅の集合と大きい餅の集合が組になっていない場合、その組み合わせを変えて、小さい餅の集合と大きな餅の集合から選ぶことができるためです。

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

正解の貪欲法を実装します。

• 大きい餅の集合 big と小さい餅の集合 small に分けます。
• 小さい餅の集合から小さい順に餅を選びます。
  • その餅の2倍以上の最小の餅を big から選ることができたら解を増やします。
  • 大きな餅をどこまで選択されたかは、変数 used で管理しています（23、26行目）。

以下が、C++プログラムです。

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

int main()
{
	int n;
	cin >> n;
	vector<int> small;
	vector<int> big;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		if (i >= n / 2) {
			big.push_back(a);
		} else {
			small.push_back(a);
		}
	}

	int result = 0;
	int used = 0;
	for (int i = 0; i < (int)small.size(); ++i) {
		auto it = lower_bound(big.begin() + used, big.end(), small[i] * 2);
		if (it != big.end()) {
			++result;
			used = it - big.begin() + 1;
		} else {
			break;
		}
	}

	cout << result << endl;

	return 0;
}

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

Python プログラム例（ABC388E）

Python版も基本的な考え方は同じです。二分探索のオプション引数に lo に変数 used の値を指定します（17行目）。以下がプログラムです。

"""AtCoder Beginner Contest 388 E"""
import bisect

n = int(input())
a = list(map(int, input().split()))
small = []
big = []
for i in range(n):
    if i >= n // 2:
        big.append(a[i])
    else:
        small.append(a[i])

result = 0
used = 0
for e in small:
    t = bisect.bisect_left(big, e * 2, lo=used)
    if t != len(big):
        result += 1
        used = t + 1

print(result)

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

最後に

E問題は、冒頭に紹介した間違った貪欲法と格闘していて時間が切れました。勉強になりました。

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