問題概要

どの 2 つの値も互いに相異なるような、長さ $N$ の数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

この数列 $A$ の異なる 2 要素の和として表せる値の中に偶数が存在するか判定し、存在する場合その最大値を求めよ。

制約

$2 \le N \le 2 \times 10^{5}$
$0 \le A_{i} \le 10^{9}$

考えたこと

競プロを始めて、「全探索」に慣れ親しみ始めた頃合いの方は、次のような解法が思い浮かぶかもしれないですね。

つまり、数列 $A$ から相異なる 2 つの要素を選ぶ場合をすべて調べる全探索解法です。

long long res = -1;
for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
        // A[i] + A[j] が偶数かどうかを調べる
        if ( (A[i] + A[j]) % 2 == 0 ) {
            res = max(res, A[i] + A[j]);
        }
    }
}

しかし、この解法は、for 文を二重に用いており、 $O(N^{2})$ の計算量となります。実は、この解法を実装して提出しても、実行制限時間内に間に合わず、TLE (時間切れ) となります。計算量については、次の記事を読んでもらえたらと思います。

qiita.com

偶数グループと奇数グループに分離する

そこで代わりの解法を考えます。まず、2 つの値の和が偶数になるパターンは、次の 2 パターンしかないことに注目しましょう。

(偶数) + (偶数) = (偶数) である
(奇数) + (奇数) = (偶数) である

偶数と奇数を足しても偶数にはならないことがポイントです。つまり、数列 $A$ の要素を「偶数のグループ」と「奇数のグループ」に分けて考えてよいということが言えます。

たとえば、 $A = (1, 3, 4, 5, 6, 9, 12)$ としましょう。これを偶数グループと奇数グループに分けると、次のようになります。

偶数グループ： $4, 6, 12$
奇数グループ： $1, 3, 5, 9$

ここで、グループを跨ぐように選んでも和は奇数になってしまうため、必ず同じグループから選ぶ必要があります。

偶数グループから 2 つの要素を選んだ和を大きくしたいなら、 $6 + 12 = 18$ が最適です。奇数グループから 2 つの要素を選んだ和を大きくしたいなら、 $5 + 9 = 14$ が最適です。これらのうちの大きい方である $18$ が答えとなります。

ここでポイントとなるのは、同じグループ内で 2 つの要素を選んだとき、その和は必ず偶数になることです。つまり、単純に同じグループ内で大きい順に 2 つの要素を取って和をとればよいのです。

解法まとめ

整理すると、次のように考えればよいことがわかります。

偶数グループから大きい順に 2 つ取って足す
- ただし、偶数グループのメンバーが 1 個以下の場合はスキップ
奇数グループから大きい順に 2 つ取って足す
- ただし、奇数グループのメンバーが 1 個以下の場合はスキップ

このうちの大きい方が答えである

とても単純な結末を迎えました。大きい順に 2 つ選ぶのは、ソートして大きい順にとればよいでしょう。

計算量は $O(N \log N)$ となります。 $O(N^{2})$ から改善しました。この解法なら AC となります。

コード

#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>());
    
    // 各グループから大きい順に 2 つ足す
    int res = -1;
    if (even.size() >= 2) res = max(res, even[0] + even[1]);
    if (odd.size() >= 2) res = max(res, odd[0] + odd[1]);
    cout << res << endl;
}