概要

お菓子を前半と後半に分け、それぞれの部分集合について「選んだ個数」と「満足度の合計」を列挙する半分全列挙を用います。後半の合計値をソートしておくことで、条件を満たす組み合わせ数を二分探索で数えます。

考察

すべての選び方をそのまま調べると、部分集合は最大で \(2^{36}\) 個あります。これは約 \(687\) 億個であり、全列挙では実行時間に間に合いません。

また、満足度の合計を状態とする動的計画法も、\(A_i\) が最大 \(10^9\) であるため、必要な配列が大きくなりすぎます。

そこで、\(N\) 個のお菓子を次のように前半と後半に分けます。

• 前半の個数を \(n_1\)
• 後半の個数を \(n_2\)

それぞれおよそ \(N/2\) 個なので、各側の部分集合数は最大でも \(2^{18}\) 程度です。これは十分に列挙できます。

各部分集合について、次の2つを記録します。

• 何個のお菓子を選んだか
• 満足度の合計はいくつか

前半から \(l\) 個、後半から \(r\) 個選ぶとき、ちょうど \(K\) 個選ぶためには

\( l+r=K \)

である必要があります。

さらに、前半の満足度の合計を \(s_L\)、後半の合計を \(s_R\) とすると、求める条件は

\( s_L+s_R \geq X \)

です。これは

\( s_R \geq X-s_L \)

と言い換えられます。

そこで、後半から \(r\) 個選んだときの合計値をあらかじめソートしておけば、\(X-s_L\) 以上の合計値が何個あるかを lower_bound によって高速に求められます。

例えば、後半の合計値が

\([1,3,4,8]\)

で、前半の合計が \(7\)、\(X=10\) の場合、後半には

\(10-7=3\)

以上が必要です。最初の \(3\) の位置を二分探索で求めると、条件を満たす値は \(3,4,8\) の3個だと分かります。

アルゴリズム

1. お菓子を前半 \(n_1=N/2\) 個と、後半 \(n_2=N-n_1\) 個に分ける。
2. 前半のすべての部分集合を列挙する。
   • 選んだ個数を \(c\)
   • 満足度の合計を \(s\)
   • left[c] に \(s\) を追加する。
3. 後半についても同様にすべての部分集合を列挙し、合計を right[c] に追加する。
4. right[c] をそれぞれ昇順にソートする。
5. 前半から選ぶ個数 leftCount をすべて試す。
   • 後半から選ぶ個数を rightCount = K - leftCount とする。
   • rightCount が範囲外なら無視する。
6. left[leftCount] の各合計 leftSum について、後半には \(X-\mathrm{leftSum}\) 以上の合計が必要となる。
7. right[rightCount] で lower_bound を行い、その位置以降の要素数を答えに加算する。
8. 最終的な合計を出力する。

各 \(K\) 個の選び方は「前半で選んだ集合」と「後半で選んだ集合」に一意に分かれるため、重複して数えることはありません。

計算量

\(m=\lceil N/2\rceil\) とします。

• 時間計算量: \(O(N2^m)\)
• 空間計算量: \(O(2^m)\)

部分集合の列挙、後半の合計値のソート、前半の各部分集合に対する二分探索をすべて含めても、\(N\leq 36\) なら十分高速です。

実装のポイント

• 満足度の合計は最大で \(36\times 10^9\) になるため、long long を使用します。

• 答えも最大で \(2^{36}\) に近い値になる可能性があるため、int ではなく long long が必要です。

• 合計値を選んだ個数ごとに分けて保存することが重要です。これにより、前半と後半を合わせてちょうど \(K\) 個になる組み合わせだけを数えられます。

• lower_bound が返した位置から末尾までの要素数が、条件を満たす後半部分集合の個数です。

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    long long X;
    cin >> N >> K >> X;

    vector<long long> A(N);
    for (auto& a : A) cin >> a;

    int n1 = N / 2;
    int n2 = N - n1;

    vector<vector<long long>> left(n1 + 1), right(n2 + 1);

    for (int mask = 0; mask < (1 << n1); ++mask) {
        long long sum = 0;
        int count = 0;
        for (int i = 0; i < n1; ++i) {
            if (mask >> i & 1) {
                sum += A[i];
                ++count;
            }
        }
        left[count].push_back(sum);
    }

    for (int mask = 0; mask < (1 << n2); ++mask) {
        long long sum = 0;
        int count = 0;
        for (int i = 0; i < n2; ++i) {
            if (mask >> i & 1) {
                sum += A[n1 + i];
                ++count;
            }
        }
        right[count].push_back(sum);
    }

    for (auto& sums : right) {
        sort(sums.begin(), sums.end());
    }

    long long answer = 0;

    for (int leftCount = 0; leftCount <= n1; ++leftCount) {
        int rightCount = K - leftCount;
        if (rightCount < 0 || rightCount > n2) continue;

        const auto& rightSums = right[rightCount];
        for (long long leftSum : left[leftCount]) {
            auto it = lower_bound(
                rightSums.begin(), rightSums.end(), X - leftSum
            );
            answer += rightSums.end() - it;
        }
    }

    cout << answer << '\n';
    return 0;
}

---

この解説は gpt-5.6-sol-high によって生成されました。