ABC326 C問題（Peak）を解く

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

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

C問題 Peak（Difficulty : 292）

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

ABC326 C問題 Peak

ソートして二分探索します。AtCoder Problems による Difficulty は、292 でした。

解答案

数列線上の実数 $x$ は、$A_i$ のどれかと同じと考えます。これは、区間の端にプレゼントがある方がプレゼントを多くとることができるためです。

プレゼントの場所 $A_i$ を読み込みソートします。$A_i + M$ 未満の $A_j$ の要素の数は、二分探索で求めることができます。

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

配列の要素 A[i] に対して、A[i] + x 未満の要素の数を lower_bound で求めます。これから i を引けば、A[i] を左端と考えて、獲得できるプレゼントの数となります。

すべての配列の要素に対して、それを左端とする獲得できるプレゼントの数を求めて、その最大値が解答となります。

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

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	int result = 0;
	for (int i = 0; i < n; ++i) {
		int present = lower_bound(a.begin(), a.end(), a[i] + m) - a.begin() - i;
		result = max(result, present);
	}

	cout << result << endl;

	return 0;
}

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

Python プログラム例（ABC326C）

基本的な考え方は C++ と同じです。以下となります。

"""AtCoder Beginner Contest 326 C"""
import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

result = 0
for i in range(n):
    present = bisect.bisect_left(a, a[i] + m) - i
    result = max(result, present)

print(result)

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

最後に

二分探索を使う問題にも慣れてきました。

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