C++で配列からnCr値が最大となるペアを検索する方法

概要

正の整数 n 個からなる配列 arr[] が与えられたとき、二項係数 arr[i]Carr[j] が最大となるような要素のペア arr[i] と arr[j] を配列から見つけるのが課題です。条件を満たすペアが複数存在する場合は、そのうちのいずれか1つを出力すれば構いません。

入力例

arr[] = {4, 1, 2}

出力例

4 2
4C1 = 4
4C2 = 4
2C1 = 2
(4, 2) が nCr を最大化する唯一のペアです。

解法の考え方

nCr は n に関して単調増加する関数とみなせます。つまり ⁿ⁺¹C_r > ⁿC_r が成り立ちます。この性質を利用することで答えに近づくことができます。まず、配列内のすべての整数の中から最大値を n として選びます。これにより n の値が確定します。

次に r に注目します。ⁿC_r = ⁿC_n-r という対称性があるため、nCr は最初に最大値に達し、その後減少していくことが分かります。

• n が奇数の場合： 最大値は n / 2 と n / 2 + 1 の位置で現れます。
  例：n = 11 の場合、¹¹C₅ と ¹¹C₆ で最大値となります。
• n が偶数の場合： 最大値は n / 2 の位置で現れます。
  例：n = 4 の場合、⁴C₂ で最大値となります。

したがって、配列をソートした後、最大値 N を固定し、残りの要素の中から N / 2（奇数なら N / 2 または N / 2 + 1）に最も近い値を r として選べばよいことになります。

C++実装例

// この手法のC++実装
#include <bits/stdc++.h>
using namespace std;

// 最大の nCr を与えるペアを出力する関数
void printMaxValPair1(vector<long long>& v1, int n1){
    sort(v1.begin(), v1.end());
    // nCr における N の値
    long long N1 = v1[n1 - 1];
    // ケース1 : N1 が奇数の場合
    if (N1 % 2 == 1) {
        long long first_maxima1 = N1 / 2;
        long long second_maxima1 = first_maxima1 + 1;
        long long ans1 = 3e18, ans2 = 3e18;
        long long from_left1 = -1, from_right1 = -1;
        long long from = -1;
        for (long long i = 0; i < n1; ++i) {
            if (v1[i] > first_maxima1) {
                from = i;
                break;
            }
            else {
                long long diff = first_maxima1 - v1[i];
                if (diff < ans1) {
                    ans1 = diff;
                    from_left1 = v1[i];
                }
            }
        }
        from_right1 = v1[from];
        long long diff1 = first_maxima1 - from_left1;
        long long diff2 = from_right1 - second_maxima1;
        if (diff1 < diff2)
            cout << N1 << " " << from_left1;
        else
            cout << N1 << " " << from_right1;
    }
    // ケース2 : N1 が偶数の場合
    else {
        long long maxima = N1 / 2;
        long long ans1 = 3e18;
        long long R = -1;
        for (long long i = 0; i < n1 - 1; ++i) {
            long long diff = abs(v1[i] - maxima);
            if (diff < ans1) {
                ans1 = diff;
                R = v1[i];
            }
        }
        cout << N1 << " " << R;
    }
}

// ドライバーコード
int main(){
    vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
    int n1 = v1.size();
    printMaxValPair1(v1, n1);
    return 0;
}

実行結果

6 3

まとめ

このアルゴリズムでは、配列を一度ソートするだけでよく、その後は線形探索によって最適な r を求めます。計算量は O(n log n) であり、実際に巨大な二項係数を計算することなく最大の nCr を持つペアを効率的に特定できる点が大きな特徴です。