概要

\(N\) 個のお菓子から \(K\) 個を選び、その満足度の合計が \(X\) 以上になる選び方の総数を求める問題です。

考察

まず素朴な方法を考えてみましょう。\(N\) 個の中から \(K\) 個を選ぶすべての組み合わせを列挙して、合計が \(X\) 以上かを判定すれば答えが求まります。しかし \(N \leq 36\) の場合、\(K = N/2\) 付近では組み合わせの数が \(\binom{36}{18} \approx 9 \times 10^9\) にもなり、とても間に合いません。

また、全部分集合を列挙する方法（\(2^{36} \approx 6.9 \times 10^{10}\) 通り）も同様に間に合いません。

ここで重要な観察があります。「\(2^{36}\) は大きすぎるが、\(2^{18}\) なら約 \(26\) 万で十分小さい」 という点です。そこで登場するのが 半分全列挙（Meet in the Middle） というテクニックです。

\(N\) 個のお菓子を前半 \(n_1\) 個と後半 \(n_2\) 個の \(2\) グループに分けます。それぞれのグループについて全部分集合を列挙すれば、それぞれ最大でも \(2^{18}\) 通り程度で済みます。あとは前半の選び方と後半の選び方を上手く組み合わせて数え上げればよいのです。

アルゴリズム

お菓子を前半 L（\(n_1 = N/2\) 個）と後半 R（\(n_2 = N - n_1\) 個）に分けます。

後半の前計算

後半 R のすべての部分集合を列挙し、「選んだ個数 \(c\)」ごとに「満足度の合計 \(s\)」を記録します。つまり right[c] に、後半から \(c\) 個選んだときの合計値のリストを格納します。後で二分探索を使うため、各リストはソートしておきます。

前半の全列挙と組み合わせ

前半 L のすべての部分集合を列挙します。ある部分集合で個数 \(c_1\)、合計 \(s_1\) が得られたとき、全体で \(K\) 個選ぶには後半から \(c_2 = K - c_1\) 個を選ぶ必要があります。

合計を \(X\) 以上にするには、後半の合計が

\[ s_2 \geq X - s_1 \]

を満たせばよいです。right[c2] はソート済みなので、\(X - s_1\) 以上の要素の個数を 二分探索 で高速に求められます。これを前半のすべての部分集合について足し合わせれば答えになります。

具体例として、\(K = 3\) で前半から \(c_1 = 1\) 個（合計 \(s_1\)）選んだなら、後半からは \(c_2 = 2\) 個選ぶ必要があります。right[2] の中で合計が \(X - s_1\) 以上のものを数えれば、その組み合わせがすべて条件を満たします。

なお、\(c_2 = K - c_1\) が \(0\) 未満や \(n_2\) より大きい場合は該当なしなのでスキップします。

計算量

\(n_1, n_2 \approx N/2 = 18\) です。

• 時間計算量: 後半の列挙が \(O(2^{n_2} \cdot n_2)\)、ソートが \(O(2^{n_2} \cdot n_2)\)、前半の列挙と二分探索が \(O(2^{n_1} \cdot (n_1 + \log(2^{n_2})))\) となり、全体で \(O(2^{N/2} \cdot N)\) 程度です。\(N = 36\) でも約 \(2.6 \times 10^5 \times 36\) 程度で十分高速です。
• 空間計算量: 後半の全部分集合の合計値を保持するため \(O(2^{N/2})\) です。

実装のポイント

• 後半の合計値リストを個数 \(c\) ごとに分けて管理することがポイントです。「全体で \(K\) 個」という制約を満たすために、前半で選んだ個数から後半で選ぶべき個数を一意に決められるようにしています。

• ソート済みリストに対して「ある値以上の要素数」を数えるには、Python の bisect_left が便利です。need = X - s1 として len(arr) - bisect_left(arr, need) で \(X - s_1\) 以上の要素数が得られます。

• 満足度の合計は最大で \(36 \times 10^9\) に達しますが、Python では多倍長整数が扱えるためオーバーフローの心配はありません。

  ソースコード

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0]); K = int(data[1]); X = int(data[2])
    A = [int(data[3+i]) for i in range(N)]

    n1 = N // 2
    n2 = N - n1
    L = A[:n1]
    R = A[n1:]

    # 右側: count -> ソート済み sum リスト
    right = [[] for _ in range(n2 + 1)]
    for mask in range(1 << n2):
        c = 0
        s = 0
        m = mask
        idx = 0
        while m:
            if m & 1:
                c += 1
                s += R[idx]
            m >>= 1
            idx += 1
        right[c].append(s)
    for c in range(n2 + 1):
        right[c].sort()

    ans = 0
    for mask in range(1 << n1):
        c1 = 0
        s1 = 0
        m = mask
        idx = 0
        while m:
            if m & 1:
                c1 += 1
                s1 += L[idx]
            m >>= 1
            idx += 1
        c2 = K - c1
        if c2 < 0 or c2 > n2:
            continue
        need = X - s1
        arr = right[c2]
        # sum >= need の個数
        pos = bisect_left(arr, need)
        ans += len(arr) - pos

    print(ans)

main()

---

この解説は claude4.8opus-high によって生成されました。