C++で配列内のサブ配列平均値の平均を求めるアルゴリズム

問題の概要

この記事では、サイズnの整数型配列arr[]と整数mが与えられたときに、サブ配列平均の平均を求める方法を解説します。ここでいうサブ配列とは、元の配列から連続するm個の要素を取り出したものを指します。

つまり、まず各サブ配列の平均値を計算し、次にそれらの平均値をさらに平均した値を求めることになります。

入力例と出力例

入力

arr[] = {2, 5, 3, 6, 1}, m = 3

出力

3.78

計算の流れ

サイズm=3のサブ配列は {2, 5, 3}、{5, 3, 6}、{3, 6, 1} の3つ存在します。それぞれの平均は以下のように計算できます。

• {2, 5, 3} の平均:(2+5+3)/3 = 10/3
• {5, 3, 6} の平均:(5+3+6)/3 = 14/3
• {3, 6, 1} の平均:(3+6+1)/3 = 10/3

これらの平均値の平均は、

(10/3 + 14/3 + 10/3) ÷ 3 = (34/3) ÷ 3 = 34/9 ≈ 3.78

解法アプローチ

アプローチ1:すべてのサブ配列を調べるシンプルな解法

最も直感的な方法は、サイズmのサブ配列をすべて列挙してそれぞれの平均を求め、その合計をサブ配列の個数で割るというものです。実装は簡単ですが、各サブ配列の合計を毎回計算し直すため、時間計算量はO(n×m)となり、配列が大きい場合には非効率になります。

アプローチ2:スライディングウィンドウ法(効率的な解法)

計算量を抑えたい場合は、スライディングウィンドウ(尺取り法)を使うのが効果的です。

まずインデックス0から始まるサイズmのウィンドウの合計を求めます。その後、ウィンドウを1つずつ右へずらすたびに、「左端の要素を引き、新しく入ってくる右端の要素を足す」という操作だけで合計を更新できるため、各ステップの更新コストはO(1)で済みます。

各ウィンドウの平均を順に加算していき、最後にウィンドウの個数(n − m + 1)で割れば、求める答えが得られます。

• 時間計算量:O(n)
• 空間計算量:O(1)

C++での実装例

以下は、スライディングウィンドウ法を用いてこの問題を解くC++プログラムです。

#include <iostream>
using namespace std;

// サブ配列平均の平均を計算する関数
float calcMeanOfSubarrayMeans(int arr[], int n, int m) {
    float meanSum = 0, windowSum = 0;

    // 最初のウィンドウ(サイズm)の合計を求める
    for (int i = 0; i < m; i++)
        windowSum += arr[i];
    meanSum += windowSum / m;

    // ウィンドウを1つずつスライドさせながら平均を加算
    for (int i = m; i < n; i++) {
        windowSum = windowSum - arr[i - m] + arr[i];
        meanSum += windowSum / m;
    }

    // ウィンドウ(サブ配列)の個数で割って結果を返す
    int windowCount = n - m + 1;
    return meanSum / windowCount;
}

int main() {
    int arr[] = { 2, 5, 3, 6, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout << "サブ配列平均の平均は " << calcMeanOfSubarrayMeans(arr, n, m) << endl;
    return 0;
}

実行結果

サブ配列平均の平均は 3.77778

まとめ

サブ配列平均の平均を求める問題は、スライディングウィンドウを活用することでO(n)の時間計算量で効率的に解くことができます。「ウィンドウの合計を再利用する」というテクニックは、部分和や移動平均など、さまざまな配列操作の問題に応用できるので、ぜひ覚えておきましょう。