ABC330 B問題（Minimize Abs 1）を解く

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

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

B問題 Minimize Abs 1（Difficulty : 118）

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

ABC330 B問題 Minimize Abs 1

意図が読み取りにくい問題でした。AtCoder Problems による Difficulty は 118 でした。

解答案

問題を読むだけでは内容が把握できませんでした。このような場合は、入力例の確認です。入力例1について出力を確認します。

N=5、L=4、R=7、a[0]=3、a[1]=1、a[2]=4、a[3]=9、a[4]=7 です。

L以上、R以下の値で、|Y-a[i]| の最小値となるように |x[i]-a[i]| の x[i] を定めます。

• |Y-a[0]| の最小値 1 = |x[0]-3| となる x[0] は 4 となります。
• |Y-a[1]| の最小値 3 = |x[1]-1| となる x[1] は 4 となります。
• |Y-a[2]| の最小値 0 = |x[2]-4| となる x[2] は 4 となります。
• |Y-a[3]| の最小値 2 = |x[3]-9| となる x[3] は 7 となります。
• |Y-a[4]| の最小値 0 = |x[4]-7| となる x[4] は 7 となります。

a[i] が L と R の間にある場合を考える。

もうひとつ例を追加します。a[5] = 6 とすると、x[5] = 6 となります。

結果的に以下となることが分かります。

• a[i] が L 以上、R 以下の場合は、|x[i]-a[i]|=0となり、結果的に x[i] = a[i] となる。
• a[i] が L 未満の場合は、x[i] は L となる。
• a[i] が R を超える場合は、x[i] は R となる。

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

上記の考察に従い、以下の処理をします。

• a[i] が L 以上、R 以下の場合は、a[i] を出力する。
• a[i] が L 未満の場合は、L を出力する。
• a[i] が R を超える場合は、R を出力する。

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

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

int main()
{
	int n, L, R;
	cin >> n >> L >> R;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	for (int i = 0; i < n; ++i) {
		int result;
		if ((L <= a[i])&&(a[i] <= R)) {
			result = a[i];
		} else if (a[i] < L) {
			result = L;
		} else {
			result = R;
		}
		cout << result << " \n"[i == n - 1];
	}

	return 0;
}

C++17からは、clampという関数が導入されました。これを使うと全体がすっきりと書けます（14行目）。また、AtCoder 環境は、C++20を選択できます。

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

int main()
{
	int n, L, R;
	cin >> n >> L >> R;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	for (int i = 0; i < n; ++i) {
		cout << clamp(a[i], L, R) << " \n"[i == n - 1];
	}

	return 0;
}

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

Python プログラム例（ABC330B）

Python 版も基本的な考え方は同じです。以下となります。

"""AtCoder Beginner Contest 330 B"""
n, L, R = map(int, input().split())
a = list(map(int, input().split()))

result = []
for i in range(n):
    if L <= a[i] <= R:
        result.append(a[i])
    elif a[i] < L:
        result.append(L)
    else:
        result.append(R)

print(*result)

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

最後に

コンテスト中は、問題の意味が読み取れず後回しにしました。C問題とD問題を解いた後に、入力例1について紙に書いて意図が理解できました。問題の意図が読み取れない場合は、入力例の理解が有効だと再認識しました。

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