概要

\(N\) 個のお菓子から \(K\) 個を選び、その満足度の合計が \(X\) 以上になる選び方の総数を求める問題です。\(N \leq 36\) という制約から、半分全列挙（Meet in the Middle）を用います。

考察

まず素朴なアプローチを考えます。\(N\) 個から \(K\) 個を選ぶ全ての組み合わせを列挙して、合計が \(X\) 以上かを判定する方法です。しかし、組み合わせの数は最大で \(\binom{36}{18} \approx 9 \times 10^9\) 通りにもなり、全列挙は現実的な時間では終わりません。

一方で「全ての部分集合」を列挙する場合、\(2^{36} \approx 6.8 \times 10^{10}\) 通りとなり、こちらもそのままでは間に合いません。

ここで重要な気づきは、\(N\) を半分に分割すれば、各半分の部分集合は \(2^{18} \approx 2.6 \times 10^5\) 通りに抑えられるという点です。この「半分全列挙（Meet in the Middle）」により、それぞれを列挙してから賢く組み合わせることで、計算量を大幅に削減できます。

具体的には、お菓子を前半 \(n_1\) 個と後半 \(n_2\) 個に分け、 - 前半から選ぶ個数と合計 \(s_1\) - 後半から選ぶ個数と合計 \(s_2\)

の組み合わせを考えます。選ぶ個数の合計が \(K\) で、\(s_1 + s_2 \geq X\) となる組を数えればよいわけです。

アルゴリズム

Meet in the Middle（半分全列挙） を使います。

手順1: 前半・後半それぞれの列挙

お菓子を前半 \(n_1 = \lfloor N/2 \rfloor\) 個、後半 \(n_2 = N - n_1\) 個に分割します。

前半について、\(2^{n_1}\) 通りの全ての部分集合を列挙し、「選んだ個数 \(c_1\)」ごとに合計値をリスト left[c1] に格納します。後半についても同様に right[c2] を作ります。

手順2: 後半のソート

後半の各リスト right[c2] を昇順にソートしておきます。これは後で二分探索を行うためです。

手順3: 組み合わせのカウント

前半で選ぶ個数 \(c_1\) を \(0\) から \(n_1\) まで動かし、後半で選ぶべき個数を \(c_2 = K - c_1\) とします（範囲外ならスキップ）。

前半の合計 \(s_1\) に対して、条件 \(s_1 + s_2 \geq X\) すなわち \(s_2 \geq X - s_1\) を満たす後半の合計 \(s_2\) の個数を数えます。

right[c2] はソート済みなので、lower_bound で \(X - s_1\) 以上となる最初の位置を求めれば、その位置以降の要素数が条件を満たす個数になります。これを全ての \(s_1\) について足し合わせれば答えが得られます。

具体例: \(N=4, K=2, X=10\), \(A = [3, 6, 4, 8]\) の場合。前半 \(\{3, 6\}\)、後半 \(\{4, 8\}\) に分けます。 - \(c_1=0, c_2=2\): 前半合計 \(0\)、後半で2個選ぶ合計は \(\{12\}\)。\(12 \geq 10\) なので 1 通り。 - \(c_1=1, c_2=1\): 前半合計 \(\{3, 6\}\)、後半1個は \(\{4, 8\}\)。\(3+8=11\geq10\)、\(6+4=10\geq10\)、\(6+8=14\geq10\) で 3 通り。 - \(c_1=2, c_2=0\): 前半合計 \(\{9\}\)、後半0個は \(\{0\}\)。\(9 < 10\) なので 0 通り。

合計 \(4\) 通りとなります。

計算量

半分のサイズを \(M = N/2\) とします。

• 時間計算量: 列挙に \(O(2^M \cdot M)\)、ソートに \(O(2^M \cdot M)\)、二分探索によるカウントに \(O(2^M \cdot M)\) なので、全体で \(O(2^{N/2} \cdot N)\) です。\(N=36\) でも \(2^{18} \times 36 \approx 10^7\) 程度で高速に動作します。
• 空間計算量: 全部分集合の合計値を保存するので \(O(2^{N/2})\) です。

実装のポイント

• オーバーフローに注意: \(A_i \leq 10^9\) で最大 \(36\) 個の合計を扱うため、合計値は最大 \(3.6 \times 10^{10}\) になります。int ではオーバーフローするので、合計値・\(X\)・答えは必ず 64bit 整数（long long）で扱います。

• 個数ごとに分類する: 単に合計値だけでなく「選んだ個数」ごとにリストを分けておくことで、\(c_1 + c_2 = K\) という個数制約を簡単に扱えます。

• 二分探索の活用: 後半をソートしておき lower_bound で「ある値以上の個数」を \(O(\log)\) で求めるのがこの解法の肝です。全ペアを直接調べると \(O(2^{N/2} \times 2^{N/2})\) となり間に合いません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;
    long long X;
    scanf("%d %d %lld", &N, &K, &X);
    vector<long long> A(N);
    for(int i=0;i<N;i++) scanf("%lld", &A[i]);
    
    int n1 = N/2;
    int n2 = N - n1;
    
    // left: for each count, list of sums
    vector<vector<long long>> left(n1+1), right(n2+1);
    
    for(int mask=0; mask<(1<<n1); mask++){
        int cnt = __builtin_popcount(mask);
        long long sum = 0;
        for(int i=0;i<n1;i++) if(mask&(1<<i)) sum += A[i];
        left[cnt].push_back(sum);
    }
    for(int mask=0; mask<(1<<n2); mask++){
        int cnt = __builtin_popcount(mask);
        long long sum = 0;
        for(int i=0;i<n2;i++) if(mask&(1<<i)) sum += A[n1+i];
        right[cnt].push_back(sum);
    }
    
    for(int c=0;c<=n2;c++) sort(right[c].begin(), right[c].end());
    
    long long ans = 0;
    for(int c1=0;c1<=n1;c1++){
        int c2 = K - c1;
        if(c2 < 0 || c2 > n2) continue;
        auto& R = right[c2];
        for(long long s1 : left[c1]){
            long long need = X - s1;
            // count of R >= need
            int idx = lower_bound(R.begin(), R.end(), need) - R.begin();
            ans += (long long)(R.size() - idx);
        }
    }
    
    printf("%lld\n", ans);
    return 0;
}

---

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