C++で通過する車のペアを数える方法

長さNの配列が与えられ、その中には0と1のみが含まれています。値1は西方向へ進む車を、値0は東方向へ進む車を表します。

車Aと車Bのペアが 0 <= A < B < N の条件を満たし、Aが東方向へ、Bが西方向へ進んでいる場合、そのペアを「通過する車」として1つとカウントします。つまり、0のインデックスが1のインデックスより小さい (0, 1) のペアを数えることになります。

具体例で確認しましょう。

入力 − arr[] = {1, 0, 1, 0, 1}

出力 − 通過する車のペア数： 3

説明 − 0のインデックスが1のインデックスより小さい (0, 1) のペアは、(arr[1], arr[2])、(arr[1], arr[4])、(arr[3], arr[4]) の3つです。

入力 − arr[] = {1, 0, 0, 0, 0}

出力 − 通過する車のペア数： 0

説明 − 0のインデックスが1のインデックスより小さい (0, 1) のペアは存在しません。

素朴なアプローチ（Naive Approach）

まずは2つのforループを使った素朴なアプローチです。配列を先頭から走査し、0に遭遇した時点で、その位置から配列の末尾まで再度走査を行い、1に遭遇するたびにカウントを増やしていきます。計算量はO(N²)となります。

• 0と1を含む配列arr[]を用意します。

• 関数count_cars(int arr[], int size)は、配列とその長さを引数として受け取り、通過する車のペア数を返します。

• 初期カウントを0とします。

• インデックスi=0からi<size-1まで配列を走査します。

• arr[i]が0の場合、インデックスj=i+1からj<sizeまで再度配列を走査します。

• arr[j]が1であれば、ペア(arr[i], arr[j])が(0, 1)かつi<jを満たすため、カウントを1増やします。

• 最終的に合計カウントが得られます。

• カウントを結果として返します。

効率的なアプローチ（Efficient Approach）

次に、計算量O(N)で解ける効率的なアプローチを紹介します。この方法では、配列を末尾から走査します。末尾から順に1の個数を数えていき、0に遭遇したタイミングで、それまでに数えた1の個数（変数temp）だけペアが成立することになります。

• 0と1を含む配列arr[]を用意します。

• 関数count_cars(int arr[], int size)は、配列とその長さを引数として受け取り、通過する車のペア数を返します。

• 初期カウントを0、tempも0とします。

• whileループを使い、size >= 1 の間、配列を末尾から走査します。

• arr[size-1]が1の場合、これまでに見つけた1の個数を表す変数tempを増やします。

• そうでなければ0です（temp個の1よりも小さいインデックスを持つ）。このとき成立するペア数はtempなので、count = count + temp とします。

• 次の要素へ進むためにsizeを減らします。

• 最終的に合計カウントが得られます。

• カウントを結果として返します。

実装例（素朴なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
   int count = 0;
   for (int i=0; i<size-1; i++){
      if(arr[i] == 0){
         for (int j=i+1; j<size; j++)
         if (arr[j]==1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {1, 1, 0, 0, 1};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of passing car pairs are: "<<count_cars(arr, size);
   return 0;
}

出力

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

Count of passing car pairs are: 2

実装例（効率的なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
   int count = 0;
   int temp = 0;
   while (size >= 1){
      if (arr[size-1] == 1){
         temp++;
      }
      else{
         count = count + temp;
      }
      size--;
   }
   return count;
}
int main(){
   int arr[] = {1, 1, 0, 1, 1};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of passing car pairs are: "<<count_cars(arr, size);
   return 0;
}

出力

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

Count of passing car pairs are: 2

まとめ

素朴なアプローチでは二重ループにより時間計算量がO(N²)になりますが、末尾から走査する効率的なアプローチを使えば、1回の走査で済むためO(N)まで削減できます。データサイズが大きい場合は、後者の手法を選ぶことで大幅なパフォーマンス向上が期待できます。