AtCoder

ABC272 C問題(Max Even)を解く

AtCoder_ABC272_C

AtCoder が提供しているABC(AtCoder Beginner Contest)272 のC問題をC++とPythonで解いてみました。ABC272は、2022年10月8日21:00に実施されました。

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

C問題 Max Even(Difficulty : 167)

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

ABC272 C問題 Max Even

問題の条件のもとで最大値を求める問題です。AtCoder Problems による Difficulty は、167 でした。ABC C問題としては、やや簡単な難易度です。

最初の考察

最初に考えた問題を解く方針です。

  • N と数列 An を読み込む。
  • N = 2 の場合を判断する。
    • A0 + A1 が偶数なら、それが解
    • 上記でない場合は、-1 を出力する。
  • N = 3 以上の場合
    • An を降順にソートする。
    • A0 + A1 が偶数なら、それが解
    • A0 + A2 が偶数なら、それが解
    • ここまでくれば、A1 + A2 は必ず偶数になるため、それが解
      ※ A0、A1、A2 のうち、どれか二つは偶奇が一致するため

この方針で、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];
	}

	if (n == 2) {
		if ((a[0] + a[1])% 2 == 0) {
			cout << a[0] + a[1] << endl;
		} else {
			cout << -1 << endl;
		}
		return 0;
	}

	sort(a.begin(), a.end(), greater<int>());

	int result = 0;
	if ((a[0] + a[1])% 2 == 0) {
		result = a[0] + a[1];
	} else if ((a[0] + a[2])% 2 == 0) {
		result = a[0] + a[2];
	} else {
		result = a[1] + a[2];
	}

	cout << result << endl;

	return 0;
}

これを採点させたところ、WA(Wrong Answer)と判断されました。

WA が出力されて気が付きましたが、以下の推論は正しいのですが、最大値を出すわけではありませんでした。

  • N = 3 以上の場合
    • An を降順にソートする。
    • A0 + A1 が偶数なら、それが解
    • A0 + A2 が偶数なら、それが解
    • ここまでくれば、A1 + A2 は必ず偶数になるため、それが解

例えば、降順のソート結果を以下とします。

100, 9, 7, 2

この場合、100 + 9 は奇数、100 + 7 は奇数ですから、9 + 7 = 16 は必ず偶数になります。一方、A0 + A3 = 100 + 2 = 102 が最大値になります。

ここは、偶数、奇数に分けて数字を分けたほうがよさそうです。

解答案

前の考察を考慮して、新たに問題を解く方針を書きだします。

  • N と数列 An を読み込む。
  • An を偶数と奇数に分ける。
  • 偶数と奇数それぞれを降順にソートする。
  • 偶数の大きい数2つを加える。別に奇数の大きい数2つを加える。その大きい数を解答とする。

解答が -1 となるのは、偶数が1つ、奇数が1つの場合だけとなります。

C++ プログラム例(ABC272C)

偶数と奇数を格納するために vector コンテナを使います。格納した後に降順にソートして、コンテナにある数を確認して、解答を求めています。

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

int main()
{
	int n;
	cin >> n;
	vector<int> even, odd;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		if (a % 2 == 0) {
			even.push_back(a);
		} else {
			odd.push_back(a);
		}
	}

	sort(even.begin(), even.end(), greater<int>());
	sort(odd.begin(), odd.end(), greater<int>());

	int result = -1;
	if (even.size() >= 2) {
		result = max(result, even[0] + even[1]);
	}
	if (odd.size() >= 2) {
		result = max(result, odd[0] + odd[1]);
	}

	cout << result << endl;

	return 0;
}

このプログラムは、AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC272C)

C++ 版をベースに Python 版をプログラムしました。Vector コンテナの代わりにリストを使っています。もっと Python らしい書き方ができるかもしれません。

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

even = []
odd = []
for i in range(n):
    if a[i] % 2 == 0:
        even.append(a[i])
    else:
        odd.append(a[i])

even.sort(reverse=True)
odd.sort(reverse=True)

result = -1
if len(even) >= 2:
    result = max(result, even[0] + even[1])
if len(odd) >= 2:
    result = max(result, odd[0] + odd[1])
print(result)

Python 版も「AC」と判定されました。

最後に

ABC C問題としては、やや簡単な難易度でしたが、最初の方針を間違えることもあるという例になりました。一方、偶数、奇数で分けることに気づけば、解きやすい問題でした。

D問題は、グラフの最短距離を求める問題に帰着します。今のわたしには難易度が高く、今回は、C問題までの解説としました。

引き続き ABC を解いていきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA