C++で偶数・奇数の個数が等しい部分配列を数える方法

問題の概要

正の整数からなる配列が与えられます。目的は、配列内の連続した要素からなる部分配列のうち、「偶数と奇数の要素数が等しい」ものをすべて見つけ、その個数を求めることです。

例として、配列が { 1, 2, 3, 4 } の場合、条件を満たす部分配列は {1,2}、{2,3}、{3,4}、{1,2,3,4} の4つとなり、答えは 4 になります。

入力例と出力例

入力 − arr[] = {1, 3, 5, 7, 8, 3, 2}

出力 − 偶数と奇数の個数が等しい部分配列の数 − 4

説明 − 該当する部分配列は {7, 8}、{8, 3}、{3, 2}、{7, 8, 3, 2} の4つです。

入力 − arr[] = {2, 4, 6}

出力 − 0

説明 − すべての要素が偶数のため、条件を満たす部分配列は1つも存在しません。

アルゴリズムの考え方

このアプローチでは、変数 temp を「これまでに読んだ要素における（奇数の個数 − 偶数の個数）」という差分として扱います（初期値は 0）。arr[i] が奇数なら temp を +1、偶数なら −1 していきます。

ある時点で temp の値が過去に一度でも出現していれば、その2つのインデックスの間には「偶数と奇数の個数が等しい部分配列」が必ず存在します。temp は正にも負にもなり得るため、正の差分の出現回数を記録するハッシュ配列 arr_1[size+1] と、負の差分の出現回数を記録するハッシュ配列 arr_2[size+1] の2つを用意します。

• temp が負のときは、arr_2[-temp] の頻度を count に加算します（-temp により正のインデックスに変換できます）。
• temp が 0 以上のときは、arr_1[temp] の頻度を count に加算します。
• 同じ差分値を持つ位置どうしはすべて条件を満たす部分配列の組み合わせになるため、加算後に該当する頻度を +1 して更新します。

動作例

Arr[] = { 1, 3, 5, 7, 8, 3, 2 }

先頭から順に求めた temp の値は次のようになります。

1, 2, 3, 4, 3, 4, 3
arr_1[] = { 1, 1, 1, 3, 2, 0, 0, 0 }  // 差分はすべて正
arr_2[] = { 0, 0, 0, 0, 0, 0, 0, 0 }  // 負の差分はない

各ステップで arr_1[temp] を count に加算していくと、最終的な count は 4 になります。対応する部分配列は {7, 8}、{8, 3}、{3, 2}、{7, 8, 3, 2} です。

手順のまとめ

• 入力配列を arr[] とします。
• 関数 Sub_even_odd(int arr[], int size) は配列とその長さを受け取り、偶数・奇数の個数が等しい部分配列の個数を返します。
• count を 0 で初期化し、奇数に出会ったら増加し、偶数に出会ったら減少する変数 temp を用意します。
• temp の出現頻度を記録する2つの配列 arr_1[] と arr_2[] を用意します。arr_1[] は正の差分（配列全体が偶数のみの場合など、最大 size+1 まで）、arr_2[] は負の差分を格納します。
• for ループで arr[] を走査します。
• (arr[i] & 1) == 1 なら arr[i] は奇数なので temp を +1、そうでなければ −1 します。
• temp が負の場合は arr_2[] の対応する頻度を count に加え、その頻度を +1 します。
• temp が 0 以上の場合は arr_1[] の対応する頻度を count に加え、その頻度を +1 します。
• 走査が終わった時点の count が、偶数と奇数の個数が等しい部分配列の総数になります。
• count を結果として返します。

C++での実装例

なお、元コードの arr[i] & 1 == 1 は演算子の優先順位の関係で偶然意図どおりに動作しますが、可読性と安全性のため (arr[i] & 1) == 1 と括弧を明示しています。また、可変長配列（VLA）は標準C++の機能ではないため、ここでは移植性の高い std::vector を使用しています。

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

int Sub_even_odd(int arr[], int size){
    int count = 0;
    int temp = 0;
    vector<int> arr_1(size + 1, 0);   // 正の差分の頻度
    vector<int> arr_2(size + 1, 0);   // 負の差分の頻度
    arr_1[0] = 1;                     // 先頭から始まる部分配列用（差分0を1回とみなす）

    for (int i = 0; i < size; i++){
        if ((arr[i] & 1) == 1)
            temp++;   // 奇数
        else
            temp--;   // 偶数

        if (temp < 0){
            count += arr_2[-temp];
            arr_2[-temp]++;
        }
        else{
            count += arr_1[temp];
            arr_1[temp]++;
        }
    }
    return count;
}

int main(){
    int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "偶数と奇数の個数が等しい部分配列の数: "
         << Sub_even_odd(arr, size);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

偶数と奇数の個数が等しい部分配列の数: 4

計算量

配列を一度だけ走査すればよいため、時間計算量は O(n)、補助配列の分だけ空間計算量も O(n) です。すべての部分配列を列挙して数える素朴な O(n²) の手法と比べて、大幅に効率的であることがわかります。