C++で部分配列の合計が偶数になる個数を求める方法

要素数 N の配列 arr[] が与えられたとき、合計が偶数となる部分配列（連続部分配列）の個数を求める問題について解説します。

問題の例

入力

arr[] = {2, 1, 3, 4, 2, 5}

出力

28

この配列において、合計が偶数となる連続部分配列は全部で 28 個存在します。（元記事の列挙には非連続の部分配列（部分列）が混在していましたが、ここでは標準的な定義である「連続部分配列」としてカウントしています。）

解法 1：ブルートフォース法（全探索）

最も直感的な方法は、すべての部分配列の合計を計算し、偶数かどうかを判定することです。計算量は O(N^2) となります。

アルゴリズム

1. 開始インデックス i を 0 から N-1 まで動かす
2. 終了インデックス j を i から N-1 まで動かし、部分配列 arr[i...j] の合計を順次加算する
3. 合計が偶数（sum % 2 == 0）ならカウントを増やす

C++ 実装例

#include <iostream>
using namespace std;

// 部分配列の偶数合計カウント（O(N^2)）
int countEvenSumSubArrayBruteForce(int arr[], int n) {
    int evenSumCount = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if (sum % 2 == 0) {
                evenSumCount++;
            }
        }
    }
    return evenSumCount;
}

int main() {
    int arr[] = {2, 1, 3, 4, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "偶数合計の部分配列の数: " << countEvenSumSubArrayBruteForce(arr, n) << endl;
    // 出力: 28
    return 0;
}

解法 2：累積和の偶奇を利用した最適解（O(N)）

部分配列 arr[i...j] の合計は、累積和を用いて prefix[j+1] - prefix[i] と表せます。この差が偶数になる条件は、prefix[j+1] と prefix[i] の偶奇（パリティ）が**同じ**場合です。

したがって、累積和の値が「偶数」になるインデックスの数を evenCount、「奇数」になるインデックスの数を oddCount とすると、答えは以下の組み合わせの和になります。 \[ \binom{evenCount}{2} + \binom{oddCount}{2} = \frac{evenCount \times (evenCount - 1)}{2} + \frac{oddCount \times (oddCount - 1)}{2} \]

初期状態（要素なし）の累積和 0 は偶数なので、evenCount は 1 から始めます。

C++ 実装例

#include <iostream>
#include <vector>
using namespace std;

// 部分配列の偶数合計カウント（O(N)）
long long countEvenSumSubArrayOptimized(const vector<int>& arr) {
    long long evenCount = 1; // 累積和 0（空部分配列）は偶数
    long long oddCount = 0;
    int prefixParity = 0;    // 0: 偶数, 1: 奇数

    for (int x : arr) {
        prefixParity = (prefixParity + (x & 1)) & 1; // 偶奇のみ更新
        if (prefixParity == 0) {
            evenCount++;
        } else {
            oddCount++;
        }
    }
    // nC2 = n * (n - 1) / 2
    return (evenCount * (evenCount - 1) / 2) + (oddCount * (oddCount - 1) / 2);
}

int main() {
    vector<int> arr = {2, 1, 3, 4, 2, 5};
    cout << "偶数合計の部分配列の数: " << countEvenSumSubArrayOptimized(arr) << endl;
    // 出力: 28
    return 0;
}

計算量の比較

まとめ

• 部分配列の合計が偶数 ⇔ 区間の両端の累積和の偶奇が一致
• 累積和の偶奇の出現回数を数えるだけで、全区間を列挙せずに答えを導出できる
• 競プロや実務では O(N) 解法 が標準的です