ABC321 B問題（Cutoff）を解く

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

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

B問題 Cutoff（Difficulty : 220）

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

ABC321 B問題 Cutoff

最終ラウンドに取るテストの点数について全探索を行います。AtCoder Problems による Difficulty は 220 でした。

解答案

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

最終ラウンドの点数について、$0 \leqq i \leqq 100$ の範囲で条件を満たすか調べます。

• ソートするため、配列 a を別の配列 b にコピーします（16行目）。
• 最終ラウンドの点数 i を配列に加えます（17行目）。
• ソートして、最高スコアと最低スコアを除いて、最終結果を求めます。
• 点数が小さい順に調べているため、score が x 以上になれば、ループを抜けて、解答を出力します。

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

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

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

	int result = -1;
	vector<int> b;
	for (int i = 0; i <= 100; ++i) {
		b = a;
		b.push_back(i);
		sort(b.begin(), b.end());
		int score = 0;
		for (int j = 1; j < n - 1; ++j) {
			score += b[j];
		}
		if (score >= x) {
			result = i;
			break;
		}
	}

	cout << result << endl;

	return 0;
}

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

Python プログラム例（ABC321B）

Python 版は、読み込んだリスト a を書き換えました（7、12行目）。組込み関数 sum、max、min を使うことによって、すっきりと書けています（8行目）。

"""AtCoder Beginner Contest 321 B"""
n, x = map(int, input().split())
a = list(map(int, input().split()))

result = -1
for i in range(101):
    a.append(i)
    score = sum(a) - max(a) - min(a)
    if score >= x:
        result = i
        break
    del a[-1]

print(result)

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

最後に

この問題は、少し前なら代数的に解こうとしたかもしれません。制約から時間的に間に合うことが分かり、素直に全探索しました。

難易度が低い問題に対しては、「下手な考えより全探索！」は、役立つ格言だと思います。

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