【C++】部分配列内の要素の平均が残りの要素の平均より大きくなる部分配列の個数を数える方法

問題の概要

正の整数からなる配列 arr[ ] が与えられます。この記事のゴールは、「部分配列に含まれる要素の平均が、部分配列に含まれない残りの要素の平均よりも大きい」という条件を満たす部分配列の個数を求めることです。

例 1

入力:

arr[ ] = { 3, 2, 4 }

出力:

部分配列内の要素の平均が、部分配列に含まれない要素の平均より大きくなる部分配列の個数: 2

説明:

考えられる部分配列は次の通りです −
[ 3 ], [ 2 ], [ 4 ], [ 3,2 ], [ 2,4 ], [ 3,2,4 ]

[ 4 ] の平均は 4 であり、残りの [ 2,3 ] の平均よりも大きい。
[ 3,2,4 ] の平均は 3 であり、空の配列 [ ] よりも大きい。

例 2

入力:

arr[ ] = { 3, 3, 3 }

出力:

部分配列内の要素の平均が、部分配列に含まれない要素の平均より大きくなる部分配列の個数: 1

説明:

考えられる部分配列は次の通りです −
[ 3 ], [ 3 ], [ 3 ], [ 3,3 ], [ 3,3 ], [ 3,3,3 ]

[ 3,3,3 ] の平均は 3 であり、空の配列 [ ] よりも大きい。

プログラムで使うアプローチ

このアプローチでは、まず累積和(接頭辞和)配列を作成し、new_arr[i] に「インデックス i までの要素の合計」を格納します。直前の要素までの合計がわかっていれば、arr[i] までの合計と要素数(j−i+1)からそれぞれの平均を簡単に計算できます。

• 配列 arr[ ] を入力として受け取ります。
• 関数 count(int arr[], int size) は、arr[ ] とそのサイズを受け取り、「部分配列内の要素の平均が部分配列外の要素の平均より大きい」部分配列の個数を返します。
• 各インデックスまでの合計を保持するための配列 new_arr[size] を用意します。
• i=0 から i<size まで走査し、new_arr[i] に new_arr[i−1]+arr[i−1] を設定します。
• 二重の for ループで new_arr[ ] を走査します。
• total_1 を現在の部分配列の合計、count_1 をその要素数として計算します。
• total_2 を残りの部分配列の合計、count_2 をその要素数として計算します。
• 平均を check_1 = total_1 / count_1、check_2 = total_2 / count_2 として求めます。
• check_1 > check_2 が成立する場合は count をインクリメントします。
• すべてのループが終わったら count を結果として返します。

サンプルコード(C++)

#include <bits/stdc++.h>
using namespace std;
int count(int arr[], int size){
    int count = 0;
    int new_size = size + 1;
    int new_arr[new_size] = { 0 };
    for (int i = 1; i < new_size; i++){
       new_arr[i] = new_arr[i - 1] + arr[i - 1];
    }
    for (int i = 1; i < new_size; i++){
       for (int j = i; j < new_size; j++){
          int total_1 = new_arr[j] - new_arr[i - 1];
          int count_1 = j - i + 1;
          int total_2 = new_arr[size] - total_1;
          int count_2 = 0;
          if((size - count_1) == 0){
             count_2 = 1;
          } else {
             count_2 = size - count_1;
          }
          int check_1 = total_1 / count_1;
          int check_2 = total_2 / count_2;
          if (check_1 > check_2){
             count++;
          }
       }
    }
    return count;
}
int main(){
    int arr[] = { 2, 6, 2, 4 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of number of sub-arrays such that the average of elements present in "
       "the sub-array is greater than that not present in the sub-array are: "<<count(arr, size);
    return 0;
}

実行結果

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

Count of number of sub-arrays such that the average of elements present in the sub-array is greater than that not present in the sub-array are: 6

まとめ

累積和を事前に計算しておくことで、任意の区間の合計を O(1) で求められるため、全部分配列の組み合わせを効率よく検証できます。計算量は二重ループにより O(n²) となり、単純に毎回合計を再計算する方法よりも高速に動作します。