ABC368 B問題（Decrease 2 max elements）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）368 B問題をC++とPythonで解いてみました。ABC368は、2024年8月24日21:00に実施されました。

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

B問題 Decrease 2 max elements（Difficulty : 56）

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

ABC368 B問題 Decrease 2 max elements

与えられた操作をそのままシミュレーションします。AtCoder Problems による Difficulty は 56 でした。

解答案

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

$N \leqq 100$ と制約が小さいため、毎回ソートしても間に合います。降順にソートして、a[1] の値が 0 であれば、$A$ に含まれる正の要素の個数が 1 つ以下となります。

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

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

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

	int result = 0;
	while (1) {
		sort(a.begin(), a.end(), greater<int>());
		if (a[1] == 0) {
			break;
		}
		--a[0];
		--a[1];
		++result;
	}

	cout << result << endl;

	return 0;
}

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

Python プログラム例（ABC368B）

Python版も基本的な考え方は同じです。以下がプログラムです。

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

result = 0
while True:
    a.sort(reverse=True)
    if a[1] == 0:
        break
    a[0] -= 1
    a[1] -= 1
    result += 1

print(result)

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

最後に

ユーザ解説で、ソートを使わない $O(N)$ の解法が紹介されています。わたしの実力では、制約を満たす場合、簡素なプログラムを実装する方がよさそうです。

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