要素の合計が偶数になる空でない部分集合の長さを求めるC++プログラム

n個の要素を持つ配列Aがあるとします。この中から要素の合計が偶数になるような空でない部分集合を見つけ、その長さを求める必要があります。条件を満たす部分集合が存在しない場合は、-1を返します。

例えば、入力が A = [1, 3, 7] の場合、[1, 3] の合計は4（偶数）となるため、出力は2になります。

解法の考え方

この問題は、配列内の要素の偶奇に着目することで非常にシンプルに解くことができます。

• 配列内に偶数が1つでも存在すれば、その要素単独で合計が偶数になるため、答えは 1
• すべての要素が奇数で、要素数が2以上であれば、任意の2つの奇数の合計は必ず偶数になるため、答えは 2
• 要素が1つだけで、かつそれが奇数の場合は、条件を満たす部分集合が存在しないため -1 を返す

アルゴリズムの手順

上記の考え方に基づき、以下の手順で処理を行います。

n := Aのサイズ
i := 0 で初期化し、i < n の間、i を1ずつ増やしながら繰り返す:
    もし A[i] を 2 で割った余りが 0 の場合:
        k := i + 1
もし n が 1 かつ k が 0 の場合:
    -1 を返す
そうでなく、k が 0 以外の場合:
    1 を返す
それ以外の場合:
    2 を返す

実装例

理解を深めるために、以下のC++での実装例を見てみましょう。

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

int solve(vector<int> A) {
    long n = A.size(), k = 0;
    for (long i = 0; i < n; i++) {
        if (A[i] % 2 == 0) {
            k = i + 1;
        }
    }
    if (n == 1 & k == 0) {
        return -1;
    }
    else if (k != 0) {
        return 1;
    }
    else {
        return 2;
    }
}
int main() {
    vector<int> A = { 1, 3, 7 };
    cout << solve(A) << endl;
}

コードの解説

solve関数では、まずループを使って配列内に偶数が存在するかどうかを確認しています。変数kには、見つかった偶数の位置+1が記録され、kが0以外であれば「配列内に偶数が存在する」ことを意味します。

その後の条件分岐では、要素数が1かつ奇数のみの場合に-1を返し、偶数が存在する場合は1、すべて奇数で要素数が複数の場合は2を返します。

入力

{ 1, 3, 7 }

出力

2

この入力例では、配列内に偶数が存在しないため k は 0 のままです。しかし要素数が3（複数）なので、2つの奇数を選ぶことで合計を偶数にできるため、正しく2が出力されます。