C++でX以下の要素のみを含む部分配列の個数を求める方法

整数型の配列 arr[] と変数 X が与えられたとき、「各部分配列(サブ配列)が X 以下の要素のみで構成されている」という条件を満たす部分配列をすべて数えるのが本記事の目的です。例えば、配列が [1,2,3] で X=2 の場合、条件を満たす部分配列は [1]、[2]、[1,2] の3つになります。

具体例で理解する

入力 − arr[] = { 4,3,2,1,6 }; X=3

出力 − X 以下の要素を持つ部分配列の個数 − 6

説明 − 条件を満たす部分配列は以下の通りです。

[3], [2], [1], [3,2], [2,1], [3,2,1]

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

出力 − X 以下の要素を持つ部分配列の個数 − 4

説明 − 条件を満たす部分配列は以下の通りです。

[3], [2], [1], [5]

プログラムで使用するアプローチ

まず、元の配列 arr[] と同じサイズのバイナリ配列 temp_arr[] を作成します。対応する arr[i] が X 以下であれば 1、そうでなければ 0 を格納します。次に temp_arr[] を走査し、連続する 1 の区間(つまり arr[] 内で X 以下の要素が連続している区間)を検出します。各区間の長さを temp として記録すると、長さ temp の区間から作れる部分配列の総数は temp × (temp + 1) / 2 で求められます。これを合計 count に加算し、temp_arr[] の末尾まで処理を続けます。

• 配列 arr[] と変数 X を用意します。

• 関数 sub_X(int arr[], int size, int x) は配列と x を受け取り、x 以下の要素のみを含む部分配列の個数を返します。

• 一時変数 temp と、最終的な合計を格納する count を用意します。

• arr[] と同じ長さのバイナリ配列 temp_arr[] を用意します。

• for ループを使い、i=0 から i<size まで arr[] を走査します。

• 各要素について、arr[i]<=x なら temp_arr[i]=1、それ以外は 0 を設定します。

• for ループで temp_arr[] を走査します。

• temp_arr[i]==1 の要素が見つかったら、現在のインデックス i からサブループ(temp_2=i+1; temp_2<size)で走査を続け、temp_arr[temp_2] が 1 である限り進み、0 になったらサブループを抜けます。

• すべて 1 が続く区間の長さは temp = temp_2 − i となります。

• この区間はすべての要素が arr[i] <= x を満たすことを意味するため、そこから作れる部分配列の総数は temp_3 = temp × (temp + 1) / 2 です。

• 両方の走査が完了した時点で、count には arr 内の X 以下の数値だけで構成されるすべての部分配列の総数が格納されています。

コード例

#include <iostream>
using namespace std;
int sub_X(int arr[], int size, int x){
   int count = 0, temp = 0;
   int temp_arr[size];
   for (int i = 0; i < size; i++){
      if (arr[i] <= x){
         temp_arr[i] = 1;
      }
      else{
         temp_arr[i] = 0;
      }
   }
   for (int i = 0; i < size; i++){
      if (temp_arr[i] == 1){
         int temp_2;
         for(temp_2 = i + 1; temp_2 < size; temp_2++){
            if(temp_arr[temp_2] != 1){
               break;
            }
         }
         temp = temp_2 - i;
         int temp_3 = (temp) * (temp + 1)/2;
         count = count + temp_3;
         i = temp_2;
      }
   }
   return count;
}
int main(){
   int arr[] = { 2, 6, 1, 10, 5, 3 };
   int x = 4;
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"X以下の要素を持つ部分配列の個数: "<<sub_X(arr, size, x);
   return 0;
}

出力

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

X以下の要素を持つ部分配列の個数: 3