C++で条件 i*arr[i] > j*arr[j] を満たす配列内のペアの個数を数える方法

数値からなる配列が与えられたとき、次の条件を満たす要素のペアを見つけるのが目標です。

条件： (i × arr[i]) > (j × arr[j]) が成り立つ場合、(arr[i], arr[j]) は有効なペアとみなされます。

例えば、配列が [5, 4, 3, 2, 1] の場合、有効なペアは [3, 1] と [2, 1] の2つになります。

例で理解する

入力： arr[] = [1, 5, 4, 1, 2, 8, 3]

出力： 条件 i*arr[i] > j*arr[j] を満たすペアの個数 ― 3

説明： 有効なペアは (5, 1)、(4, 1)、(8, 3) の3つです。

入力： arr[] = [-1, -2, 3, 4, 5, 6]

出力： 条件 i*arr[i] > j*arr[j] を満たすペアの個数 ― 1

説明： 有効なペアは (-1, -2) の1つです。

アルゴリズムのアプローチ

この問題は、二重の for ループを使って配列を走査することで解決できます。各インデックス i と arr[i] に対して、条件 i*arr[i] > j*arr[j](ただし i ≠ j)を満たす j と arr[j] を探し、条件が成立するたびにカウントを増やしていきます。

• 整数型の配列を受け取ります。
• 関数 condition_pair(int arr[], int size) は、配列とそのサイズを引数に取り、条件を満たすペアの個数を返します。
• カウント用の変数 count を 0 で初期化します。
• 外側のループで i を 0 から size - 2 まで走査します。
• 内側のループで j を i + 1 から size - 1 まで走査します。
• (i * arr[i]) > (j * arr[j]) が真であれば、count を 1 増やします。
• すべてのループが完了すると、count には条件を満たすペアの総数が格納されています。
• count を結果として返します。

C++での実装例

#include <iostream>
using namespace std;

int condition_pair(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size - 1; i++){
        for (int j = i + 1; j < size; j++){
            if(i*arr[i] > j*arr[j]){
                count++;
            }
        }
    }
    return count;
}

int main(){
    int arr[] = { 2, 4, 1, 9, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "条件 i*arr[i] > j*arr[j] を満たすペアの個数: " << condition_pair(arr, size);
    return 0;
}

出力結果

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

条件 i*arr[i] > j*arr[j] を満たすペアの個数: 2

計算量について

このアプローチでは二重ループを使用するため、時間計算量は O(N²)(N は配列のサイズ)となります。一方、追加のメモリをほとんど使用しないため、空間計算量は O(1) です。より大きな配列を扱う場合は、マージソートの考え方を応用した O(N log N) の効率的な手法も検討するとよいでしょう。