概要

\(N\) 個のお菓子から合計でちょうど \(K\) 個を選び、その満足度の総和を \(X\) 以上にする選び方の総数を求める問題です。\(N \le 36\) という制約に着目し、半分全列挙（Meet-in-the-middle） を用いて効率的に解きます。

考察

素朴なアプローチ（全探索）とその限界

まず、\(N\) 個のお菓子から \(K\) 個を選ぶすべての組み合わせを全探索することを考えてみます。 選ぶ組み合わせの数は最大で \(\binom{36}{18} = 9,075,135,300 \approx 9 \times 10^9\) 通りとなります。1秒間に実行できる処理回数は一般的に \(10^8\) 回程度であるため、単純な全探索では実行時間制限（TLE）になってしまいます。

半分全列挙による解決

\(N \le 36\) という制約は、競技プログラミングにおいて半分全列挙を適用する典型的なサインです。 配列を前半半分（サイズ \(N_1 = \lfloor N/2 \rfloor\)）と後半半分（サイズ \(N_2 = N - N_1\)）の2つに分割してみます。

• \(N_1, N_2\) は高々 \(18\) となります。
• 18個要素のすべての組み合わせ（選ぶ・選ばないの \(2^{18}\) 通り）は \(262,144\) 通りしかありません。

前半・後半それぞれで「選んだ個数」と「その満足度の和」をあらかじめ全列挙しておけば、あとは二分探索などを用いて効率よく条件を満たすペアを数え上げることができます。

アルゴリズム

具体的には以下の手順で解いていきます。

1. 配列の分割: お菓子を前半 \(N_1 = \lfloor N / 2 \rfloor\) 個と後半 \(N_2 = N - N_1\) 個に分けます。

2. 前半の全列挙: ビット全探索を用いて、前半 \(N_1\) 個のお菓子の選ぶ・選ばないのパターン（\(2^{N_1}\) 通り）を探索します。 このとき、「選んだお菓子の個数 \(c_1\)」ごとに、「満足度の合計値」を動的配列 S1[c1] に記録します。

3. 後半の全列挙: 同様に、後半 \(N_2\) 個についてすべてのパターン（\(2^{N_2}\) 通り）を探索し、「選んだお菓子の個数 \(c_2\)」ごとの「満足度の合計値」を S2[c2] に記録します。

4. 後半データのソート: 二分探索が行えるように、S2 の各リスト S2[c2] を昇順にソートします。

5. ペアの数え上げ: 前半で選ぶ個数 \(c_1\)（\(0 \le c_1 \le N_1\)）を固定します。すると、合計 \(K\) 個選ぶために後半で選ぶべき個数は \(c_2 = K - c_1\) に一意に決まります（\(0 \le c_2 \le N_2\) の範囲外ならスキップ）。

S1[c1] にある各満足度の和 \(s_1\) について、全体の和が \(X\) 以上になる条件は以下のように表せます： $\(s_1 + s_2 \ge X \iff s_2 \ge X - s_1\)$

したがって、ソート済みの S2[c2] の中で \(X - s_1\) 以上となる要素が何個存在するかを、二分探索（std::lower_bound）を用いて高速に求め、答えに加算していきます。

計算量

• 時間計算量: \(O(N \cdot 2^{N/2})\)

  • 前半・後半の全列挙に \(O(N_1 2^{N_1} + N_2 2^{N_2}) = O(N \cdot 2^{N/2})\)
  • 後半のソートに \(O(N \cdot 2^{N/2})\)
  • 前半の各要素に対する二分探索に \(O(N_1 \cdot 2^{N/1}) = O(N \cdot 2^{N/2})\)
  • \(N = 36\) のとき \(N/2 = 18\) となり、\(18 \times 2^{18} \approx 4.7 \times 10^6\) 回程度の操作で完了するため、十分高速です。

• 空間計算量: \(O(2^{N/2})\)

  • 前半と後半で全列挙した結果を保持するため、\(O(2^{N_1} + 2^{N_2}) = O(2^{N/2})\) のメモリを使用します。\(2^{18}\) 個の long long 型変数は数メガバイト程度であり、メモリ制限的にも余裕があります。

実装のポイント

• 型オーバーフローに注意: 満足度 \(A_i\) の値は最大で \(10^9\) であり、\(36\) 個の合計は最大で \(3.6 \times 10^{10}\) に達します。標準の32ビット整数型（int）ではオーバーフローするため、満足度の合計や入力の \(X\)、解を保持する変数には64ビット整数型（C++の long long）を使用してください。

• 「個数」ごとに分けて保持する: 単純にすべての和だけをグループ化すると、「全体でちょうど \(K\) 個選ぶ」という制約を満たせなくなります。そのため、選んだ個数（\(c_1, c_2\)）ごとに配分を分類しておくことが必須となります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    long long X;
    if (!(cin >> N >> K >> X)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    int N1 = N / 2;
    int N2 = N - N1;

    vector<vector<long long>> S1(N1 + 1);
    for (int mask = 0; mask < (1 << N1); ++mask) {
        int cnt = 0;
        long long sum = 0;
        for (int i = 0; i < N1; ++i) {
            if ((mask >> i) & 1) {
                cnt++;
                sum += A[i];
            }
        }
        S1[cnt].push_back(sum);
    }

    vector<vector<long long>> S2(N2 + 1);
    for (int mask = 0; mask < (1 << N2); ++mask) {
        int cnt = 0;
        long long sum = 0;
        for (int i = 0; i < N2; ++i) {
            if ((mask >> i) & 1) {
                cnt++;
                sum += A[N1 + i];
            }
        }
        S2[cnt].push_back(sum);
    }

    for (int i = 0; i <= N2; ++i) {
        sort(S2[i].begin(), S2[i].end());
    }

    long long ans = 0;
    for (int c1 = 0; c1 <= N1; ++c1) {
        int c2 = K - c1;
        if (c2 < 0 || c2 > N2) continue;

        for (long long s1 : S1[c1]) {
            long long target = X - s1;
            auto it = lower_bound(S2[c2].begin(), S2[c2].end(), target);
            ans += distance(it, S2[c2].end());
        }
    }

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.6-flash-high によって生成されました。