AtCoder が提供しているABC（AtCoder Beginner Contest）272 のC問題をC++とPythonで解いてみました。ABC272は、2022年10月8日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Max Even（Difficulty : 167）
問題はリンク先をご覧ください。
問題の条件のもとで最大値を求める問題です。AtCoder Problems による Difficulty は、167 でした。
最初の考察
最初に考えた問題を解く方針です。
- 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問題としては、やや簡単な難易度でしたが、最初の方針を間違えることもあるという例になりました。一方、偶数、奇数で分けることに気づけば、解きやすい問題でした。
引き続き ABC の問題を紹介していきます。
