【C++】指定した条件を満たすインデックスペアを数える方法

最初のN個の自然数の順列からなる配列が与えられます。この記事の目的は、次の条件を満たす要素のインデックスペアを見つけることです。

配列を Arr[]、i と j をインデックスとするとき、Arr[i] + Arr[j] = max(Arr[x])（ただし i ≦ x ≦ j）となる要素ペアを数えます。つまり、Arr[i] と A[j] の和が、この2つの区間の間に存在する最大要素と一致しているかどうかを判定します。

入力例1

Arr[]= { 2,4,1,3,6,5 }

出力例1

条件を満たすインデックスペアの数：1

解説

各ペアの和は以下のようになります。

• 2+4=6 → 6は最大値ですが、2と4の間には存在しません。
• 2+1=3 → 3は2と1の間になく、間の最大値は4です。
• 2+3=5 → 5は2と3の間になく、間の最大値は4です。
• 2+6=8 → 8は2と6の間になく、間の最大値は4です。
• 同様に他の組み合わせも確認します。
• 1+5=6 → 6は1と5の間に存在し、間の最大値も6です。条件を満たします。

すべての組み合わせの中で、条件を満たすのはこの1組だけです。

入力例2

Arr[]= { 1,2,5,4,3 }

出力例2

条件を満たすインデックスペアの数：2

解説

• 1+5=6 → 6は最大値ですが、1と5の間には存在しません。
• 1+4=5 → 5は1と4の間に存在し、間の最大値も5です。条件を満たします。
• 2+3=5 → 5は2と3の間に存在し、間の最大値も5です。条件を満たします。
• 1+3=4 → 4は1と3の間にありますが、間の最大値は5のため条件を満たしません。

すべての組み合わせの中で、条件を満たすのは2組です。

プログラムのアプローチ

• 整数配列 Arr[] に数値を格納し、size にその長さを保持します。
• 関数 countPairs(int A[], int n) は、配列とそのサイズ n を引数として受け取り、条件を満たすペアの数を返します。
• 変数 count は、該当するペアの数を格納するために初期値 0 で用意します。
• max1 を最初の要素で、maxindex を 0 で初期化し、それまでに見つかった最大値とそのインデックスを記録します。
• forループで配列を走査します。
• ネストしたforループ内で、A[j] >= max1 である場合は、max1 とそのインデックスを j の値で更新します。
• 各ペア A[i] と A[j] について、その和が max1 と等しく、かつ maxindex が i と j の間にある場合は、条件が満たされているため count を増やします。
• 両方のループが終了したら、count に格納された結果を返します。

実装例

// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// 条件を満たすインデックスペアの数を返す関数
int countPairs(int A[], int n){
    // 必要なカウントを格納する変数
    int count = 0;
    int i,j,k;
    int max1=A[0];
    int maxindex=0;
    for ( i = 0; i<n-1; i++){
        for(j=i+1;j<n;j++){
            if(A[j]>=max1){
                max1=A[j];
                maxindex=j;
            }
            if(A[i]+A[j]==max1 && maxindex>=i && maxindex<=j)
                count++;
        }
    }
    // 部分区間のカウントを返す
    return count;
}
int main(){
    int Arr[] = {3, 4, 6, 1, 5, 2};
    int size =6;
    cout <<endl<<"Count of index pairs which satisfy the given condition:"
    <<countPairs(Arr,size);
    return 0;
}

出力

Count of index pairs which satisfy the given condition: 1

このように、二重ループで全ペアを調べながら区間内の最大値を追跡することで、条件を満たすインデックスペアを効率的に数えることができます。