Pythonでn個のボールからk個を選んだときの最大値と最小値の差の合計を求めるプログラム

この記事では、n個のボールからk個を選ぶすべての組み合わせについて「最大値 − 最小値」の差を求め、その合計を計算するPythonプログラムを紹介します。

問題の概要

n個のボールがあり、それぞれのボールには配列 nums の要素が番号として書かれています（nums[i] は i 番目のボールの番号）。これとは別に整数 k が与えられます。

各ターンでは、n個の異なるボールの中からk個を選び、そのk個の最大値と最小値の差を表に記録します。その後、選んだk個を元に戻し、考えられるすべての組み合わせに対して同じ操作を繰り返します。最後に、表に記録されたすべての差の合計を求めます。答えが非常に大きくなる場合は、10⁹ + 7 で割った余りを返します。

入力例と出力例

たとえば、入力が n = 4、k = 3、nums = [5, 7, 9, 11] の場合、出力は 20 になります。これは、各組み合わせの差が次のようになるためです。

• [5, 7, 9] → 差は 9 − 5 = 4
• [5, 7, 11] → 差は 11 − 5 = 6
• [5, 9, 11] → 差は 11 − 5 = 6
• [7, 9, 11] → 差は 11 − 7 = 4

したがって、4 + 6 + 6 + 4 = 20 となります。

解き方のアプローチ

すべての組み合わせを実際に列挙すると計算量が爆発してしまうため、次の手順で効率的に求めます。なお、配列 nums は昇順にソートされているものとします。

• m := 10⁹ + 7（剰余を取るための定数）
• inv := 要素 [0, 1] を持つ新しいリスト（モジュラ逆数を格納）
• i が 2 から n までの範囲で、以下を繰り返す：
  • (m − (m // i) × inv[m mod i] mod m) を inv の末尾に追加する
• comb_count := 1（現在の組み合わせ数）
• res := 0（答えとなる合計値）
• pick が k − 1 から n − 1 までの範囲で、以下を繰り返す：
  • res := res + (nums[pick] − nums[n − 1 − pick]) × comb_count mod m
  • res := res mod m
  • comb_count := comb_count × (pick + 1) mod m × inv[pick + 2 − k] mod m
• res を返す

アルゴリズムのポイント

この手法の鍵は、「各要素が最大値・最小値として現れる回数」に着目することです。ソート済みの配列において、インデックス i の要素は C(i, k−1) 回だけ最大値となり、C(n−1−i, k−1) 回だけ最小値となります。つまり、各要素の寄与分（出現回数 × 値）を合計すれば、全組み合わせの差の総和を一度のループで求められます。二項係数は前の値から漸化的に更新し、除算の代わりにモジュラ逆数を使用することで、非常に大きな数でも高速かつ正確に計算できます。

実装例

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

def solve(n, k, nums):
    m = 10**9 + 7

    inv = [0, 1]
    for i in range(2, n + 1):
        inv.append(m - m // i * inv[m % i] % m)

    comb_count = 1
    res = 0
    for pick in range(k - 1, n):
        res += (nums[pick] - nums[n - 1 - pick]) * comb_count % m
        res %= m
        comb_count = comb_count * (pick + 1) % m * inv[pick + 2 - k] % m

    return res

n = 4
k = 3
nums = [5, 7, 9, 11]
print(solve(n, k, nums))

入力

4, 3, [5, 7, 9, 11]

出力

20