ランダムに選んだペアがC++における最大加重ペアになる確率

2つの異なる配列が与えられたとき、そこからランダムに選んだペアが「最大加重ペア」となる確率を求めるのが本記事のテーマです。

ここでの「ペア」とは、片方の配列(仮にarray1と呼びます)から1つの要素を取り出し、もう片方の配列(array2)からもう1つの要素を取り出して組み合わせたものを指します。プログラムは、第1要素がarray1の最大値であり、かつ第2要素がarray2の最大値であるペア――すなわち最大加重ペア――が選ばれる確率を計算する必要があります。

入出力の例

例1

入力:

arr1[] = { 2, 23 }
arr2[] = { 10, 3, 8 }

出力:

probability of maximum pair : 0.166667

説明:

両配列から構成できるペアの集合は次の6通りです。

{(2, 10), (2, 3), (2, 8), (23, 10), (23, 3), (23, 8)}

このうち最大加重ペアは (23, 8) の1つだけです。したがって確率は 1 ÷ 6 = 0.166667 となります。

例2

入力:

arr1[] = { 4, 5, 6 }
arr2[] = { 6, 2, 6 }

出力:

probability of maximum pair : 0.222222

説明:

両配列から構成できるペアは合計9通りです。そのうち最大加重ペア (6, 6) は2回出現します(arr2に最大値6が2つ含まれているため)。よって確率は 2 ÷ 9 = 0.222222 です。

解き方のアプローチ

• 両配列の要素を受け取る

• 各配列の最大値を求めるとともに、その最大値が出現する回数を数える。これにより最大加重ペアの総数が分かる

• 最大加重ペアの総数を、全ペア数(size_1 × size_2)で割って確率を計算する

• 計算結果の確率を出力する

アルゴリズム

開始
Step1→ 最大加重ペアの確率を返す関数を宣言する
    double max_pair(int arr1[], int arr2[], int size_1, int size_2)
        int max_pair1 = INT_MIN、count_1 = 0 を宣言
        ループ:int i = 0 として i < size_1 の間 i++ を繰り返す
            IF arr1[i] > max_pair1 ならば
                max_pair1 = arr1[i] を設定
                count_1 = 1 を設定
            End
            ELSE IF arr1[i] == max_pair1 ならば
                count_1++
            End
        End
        int max_pair2 = INT_MIN、count_2 = 0 を宣言
        ループ:int i = 0 として i < size_2 の間 i++ を繰り返す
            IF arr2[i] > max_pair2 ならば
                max_pair2 = arr2[i] を設定
                count_2 = 1 を設定
            End
            ELSE IF arr2[i] == max_pair2 ならば
                count_2++
            End
        End
        return (double)(count_1 * count_2) / (size_1 * size_2)
Step 2→ main() 内で
    int arr1[] = { 2, 23 } を宣言
    int arr2[] = { 10, 3, 8 } を宣言
    int size_1 = sizeof(arr1) / sizeof(arr1[0]) を計算
    int size_2 = sizeof(arr2) / sizeof(arr2[0]) を計算
    max_pair(arr1, arr2, size_1, size_2) を呼び出す
停止

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// 確率を返す関数
double max_pair(int arr1[], int arr2[], int size_1, int size_2){
   // 配列1の最大値とその出現回数を調べる
   int max_pair1 = INT_MIN, count_1 = 0;
   for (int i = 0; i < size_1; i++){
      if (arr1[i] > max_pair1){
         max_pair1 = arr1[i];
         count_1 = 1;
      }
      else if (arr1[i] == max_pair1){
         count_1++;
      }
   }
   // 配列2の最大値とその出現回数を調べる
   int max_pair2 = INT_MIN, count_2 = 0;
   for (int i = 0; i < size_2; i++){
      if (arr2[i] > max_pair2){
         max_pair2 = arr2[i];
         count_2 = 1;
      }
      else if (arr2[i] == max_pair2){
         count_2++;
      }
   }
   return (double)(count_1 * count_2) / (size_1 * size_2);
}
int main(){
   int arr1[] = { 2, 23 };
   int arr2[] = { 10, 3, 8 };
   int size_1 = sizeof(arr1) / sizeof(arr1[0]);
   int size_2 = sizeof(arr2) / sizeof(arr2[0]);
   cout <<"probability of maximum pair in both the arrays are "<<max_pair(arr1, arr2, size_1, size_2);
   return 0;
}

出力結果

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

probability of maximum pair in both the arrays are 0.166667

計算量について

各配列をそれぞれ一度ずつ走査すればよいため、時間計算量は O(n + m)(n、mは各配列のサイズ)、追加で必要なメモリは O(1) で済みます。全ペアを実際に列挙して数える方法(O(n × m))と比べて大幅に効率的であり、配列サイズが大きい場合でも高速に動作します。