C++で奇数をちょうどm個含む部分配列の数を求める方法

C++を使ったことがある方なら、「部分配列（サブアレイ）」という概念と、それがいかに便利であるかをご存じでしょう。C++では多くの数学的問題を効率的に解くことができます。本記事では、C++を用いて「奇数をちょうどm個含む部分配列」の数を求める方法について、基礎から詳しく解説します。

問題の定義

この問題では、与えられた配列と整数mに対して、「奇数をちょうどm個含む」部分配列が全部でいくつ作れるかを求めます。以下に具体的な例を示します。

入力 : array = { 6, 3, 5, 8, 9 }, m = 2
出力 : 5
説明 : 奇数をちょうど2個含む部分配列は
{ 3, 5 }、{ 6, 3, 5 }、{ 3, 5, 8 }、{ 6, 3, 5, 8 }、{ 5, 8, 9 } の5つ

入力 : array = { 1, 6, 3, 2, 5, 4 }, m = 2
出力 : 6
説明 : 奇数をちょうど2個含む部分配列は
{ 1, 6, 3 }、{ 1, 6, 3, 2 }、{ 6, 3, 2, 5 }、{ 6, 3, 2, 5, 4 }、{ 3, 2, 5 }、{ 3, 2, 5, 4 } の6つ

方法1：すべての部分配列を生成して調べる（総当たり法）

最初の方法は、与えられた配列から考えられるすべての部分配列を生成し、それぞれの部分配列に奇数がちょうどm個含まれているかを確認するというものです。「生成して見つける」というシンプルなアプローチで、計算量は O(n²) となります。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0; // nは配列のサイズ、mは部分配列に含めたい奇数の個数、
                                 // countは奇数がm個含まれる部分配列の数
    for (int i = 0; i < n; i++){ // 外側のループで各要素を処理
        int odd = 0;
        for (int j = i; j < n; j++) { // 内側のループで奇数m個を含む部分配列を探索
            if (a[j] % 2)
                odd++;
            if (odd == m) // 奇数の個数がmと等しくなったら
                count++;
        }
    }
    cout << "奇数がm個含まれる部分配列の数: " << count;
    return 0;
}

実行結果

奇数がm個含まれる部分配列の数: 6

コードの解説

このコードでは、二重ループ（ネストしたループ）を使って、奇数をm個含む部分配列を探索しています。外側のループは変数iを増やしながら配列の各要素を処理する役割を担います。

内側のループは部分配列を構築しながら要素を順に処理し、奇数カウンタoddがmに達するたびに結果カウンタcountを増やします。最後に、count変数に格納された結果を出力します。

方法2：プレフィックス配列を使った効率的な方法

もう一つの方法は、「奇数がi個含まれる状態の箇所数」を記録するプレフィックス配列を作成し、配列の各要素を処理しながら、奇数を見つけるたびに奇数カウンタを増やしていくやり方です。

そして、奇数の個数がm以上になった時点で、プレフィックス配列の (odd − m) 番目の位置にある値を結果に加算します。

oddがm以上になると、そのインデックスまでに形成できる部分配列の数を計算し、「odd − m」番目の値をcount変数に加算します。すべての要素の処理が完了した時点で、count変数に最終結果が格納されます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int main (){
    int array[ ] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0, odd = 0, i;
    int prefix_array[n + 1] = { 0 };
    // 配列の各要素を処理する外側のループ
    for (i = 0; i < n; i++){
        prefix_array[odd] = prefix_array[odd] + 1; // 現在の奇数の個数をprefix_array[]に記録
        // 配列の要素が奇数なら odd 変数をインクリメント
        if (array[i] % 2 == 1)
            odd++;
        // 奇数の個数がm以上になったら、
        // そのインデックスまでに形成可能な部分配列の数を求める
        if (odd >= m)
            count += prefix_array[odd - m];
    }
    cout << "奇数がm個含まれる部分配列の数: " << count;
    return 0;
}

実行結果

奇数がm個含まれる部分配列の数: 6

コードの解説

まず、配列と各変数を初期値で初期化します。

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };

ここでは、変数nに配列のサイズを、mに探す奇数の個数を、countには部分配列の個数を数えるための初期値0を、oddには0を設定し、さらにサイズ n+1 のprefix_arrayをすべて0で初期化しています。

ループの動作

for (i = 0; i < n; i++){
    prefix_array[odd] = prefix_array[odd] + 1;
    if (array[i] % 2 == 1)
        odd++;
    if (odd >= m)
        count += prefix_array[odd - m];
}

このループでは、まず現在までに数えた奇数の個数（odd）をインデックスとしてprefix_array[ ]の該当箇所を+1し、次に奇数の要素が見つかった場合にodd変数をインクリメントします。そしてodd変数がm以上になった時点で、そのインデックスまでに形成できる部分配列の数を算出してcountに加算します。

最後に、count変数に格納された「奇数m個を含む部分配列の数」を出力して結果を得ます。

まとめ

本記事では、奇数をちょうどm個含む部分配列の数を求めるための2つのアプローチについて解説しました。

• すべての部分配列を生成し、それぞれに奇数がm個含まれているかを確認して、条件を満たすたびにカウントを増やす方法。計算量は O(n²) です。

• 効率的な方法として、配列の各要素を走査しながらプレフィックス配列を作成し、それを活用して結果を求める方法。計算量は O(n) です。

本記事が、問題の理解と解決の一助となれば幸いです。