Pythonで配列内のnCr値が最大となるペアを検索する方法

問題概要

n個の整数を含む配列arrが与えられたとき、配列からarr[i]とarr[j]を選び、二項係数arr[i]Carr[j](組み合わせの数)が最大になるようなペアを見つける必要があります。条件を満たすペアが複数存在する場合は、そのうちのどれか1つを返せば構いません。

例えば、入力が[4, 1, 2]の場合、出力は「4 2」になります。これは、4C1 = 4、4C2 = 6、2C1 = 2と計算でき、(4, 2)のペアが最大値6を与える唯一の組み合わせだからです。

解法の考え方

この問題を効率的に解くには、二項係数の重要な性質を利用します。nCrは、rがn/2に最も近いときに最大値を取ることが数学的に知られています。そこで、配列の最大値をnとし、残りの要素からn/2に最も近い値をrとして選ぶ方針で解きます。

具体的な手順は以下の通りです。

• 配列vをソートする
• N := v[n - 1](配列の最大値)とする
• Nが奇数の場合:
  • first := N / 2(整数除算)、second := first + 1 とする
  • left := -1、right := -1、temp := -1 で初期化する
  • iを0からnまで繰り返す:
    • v[i] > first の場合、temp := i としてループを抜ける
    • それ以外の場合、difference := first - v[i] を計算し、difference < res1 なら res1 := difference、left := v[i] と更新する
  • right := v[temp] とする
  • difference1 := first - left、difference2 := right - second を計算する
  • difference1 < difference2 なら (N, left) を出力し、そうでなければ (N, right) を出力する
• Nが偶数の場合:
  • max := N / 2(整数除算)、res := 3×10^18、R := -1 で初期化する
  • iを0からn-1まで繰り返す:
    • difference := |v[i] - max| を計算し、difference < res なら res := difference、R := v[i] と更新する
  • (N, R) を出力する

実装例

理解を深めるために、以下のPython実装例を見てみましょう。

def findMatrixPair(v, n):
    v.sort()
    N = v[n - 1]
    if N % 2 == 1:
        first = N // 2
        second = first + 1
        res1, res2 = 3 * (10 ** 18), 3 * (10 ** 18)
        left, right = -1, -1
        temp = -1
        for i in range(0, n):
            if v[i] > first:
                temp = i
                break
            else:
                difference = first - v[i]
                if difference < res1:
                    res1 = difference
                    left = v[i]
        right = v[temp]
        difference1 = first - left
        difference2 = right - second
        if difference1 < difference2:
            print(N, left)
        else:
            print(N, right)
    else:
        max = N // 2
        res = 3 * (10 ** 18)
        R = -1
        for i in range(0, n - 1):
            difference = abs(v[i] - max)
            if difference < res:
                res = difference
                R = v[i]
        print(N, R)

v = [4, 1, 2]
n = len(v)
findMatrixPair(v, n)

入力

[4, 1, 2], 3

出力

4 2

計算量とポイント

このアルゴリズムの計算量はO(n log n)です。ソートにO(n log n)かかりますが、その後の探索処理は線形時間O(n)で完了するため、大きな配列に対しても効率的に動作します。

また、Nが奇数の場合は候補が2つ(firstとsecond)に分かれるため、それぞれに最も近い要素を比較して差が小さい方を選ぶ点がポイントです。一方、Nが偶数の場合は中央値が一意に定まるため、単純にN/2との絶対差が最小の要素を選べばよいことになります。