概要

お菓子を前半と後半に分け、それぞれの部分集合について「選んだ個数」と「満足度の合計」を列挙する半分全列挙を用います。前半から \(l\) 個選んだ場合、後半から \(K-l\) 個選ぶ組み合わせを二分探索で数えます。

考察

すべての選び方を直接調べると、最大で

\[{N \choose K}\]

通りを確認する必要があります。特に \(N=36,\ K=18\) 付近では組み合わせ数が非常に多いため、全探索では間に合いません。また、すべての部分集合を列挙する方法も \(O(2^N)\) であり、\(2^{36}\) は大きすぎます。

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

• 前半：およそ \(N/2\) 個
• 後半：残りのおよそ \(N/2\) 個

各半分の部分集合数は最大でも \(2^{18}\) 程度なので、すべて列挙できます。

ただし、今回は合計値だけでなく、ちょうど \(K\) 個のお菓子を選ぶ必要があります。そのため、部分集合の満足度の合計を、選んだ個数ごとに分類します。

前半から \(l\) 個選び、その満足度の合計が \(s\) だったとします。このとき、後半からは \(K-l\) 個選ぶ必要があり、後半の合計を \(t\) とすると条件は

\[s+t \geq X\]

です。したがって、

\[t \geq X-s\]

を満たす後半の部分集合の個数を求めればよいことになります。

後半の合計値を選んだ個数ごとにソートしておけば、\(X-s\) 以上となる最初の位置を二分探索で見つけられます。

例えば、後半から指定個数を選んだときの合計が

\[[3,5,8,11]\]

で、前半の合計が \(s=6\)、目標が \(X=14\) なら、後半には

\[t \geq 14-6=8\]

が必要です。\(8\) 以上なのは \(8,11\) の \(2\) 通りです。

アルゴリズム

1. お菓子の列を前半と後半に分割する。
2. それぞれについて、すべての部分集合を列挙し、満足度の合計を選んだ個数ごとに保存する。
   • groups[c] に、ちょうど \(c\) 個選んだ部分集合の合計を格納する。
3. 後半の各リストを昇順にソートする。
4. 前半から選ぶ個数を left_count とする。
   • 後半から選ぶ個数は right_count = K - left_count。
   • right_count が後半から選べる範囲外なら無視する。
5. 前半の各合計 left_sum に対して、後半に必要な合計は X - left_sum。
6. bisect_left を使い、後半の合計リストから X - left_sum 以上となる最初の位置を求める。
7. その位置以降の要素数を答えに加算する。

部分和の列挙では、各お菓子を順番に処理し、選ぶ個数を大きい方から更新します。降順に更新することで、同じお菓子を1回の処理中に複数回使ってしまうことを防げます。

計算量

• 時間計算量: \(O\left(N2^{\lceil N/2\rceil}\right)\)
• 空間計算量: \(O\left(2^{\lceil N/2\rceil}\right)\)

前半・後半の部分集合数はそれぞれ最大で \(2^{\lceil N/2\rceil}\) 個です。後半のソートと、前半の各部分集合に対する二分探索を含めると、時間計算量は上記になります。

実装のポイント

• 部分和を選択個数ごとに分けて保存する必要があります。合計値だけを保存すると「ちょうど \(K\) 個」という条件を判定できません。

• bisect_left(right_sums, X - left_sum) は、X - left_sum 以上となる最初の位置を返します。したがって、条件を満たす個数は len(right_sums) - pos です。

• 部分和を更新するとき、選択個数を大きい方から小さい方へ走査します。昇順に更新すると、現在処理中のお菓子を複数回選んだ状態が作られてしまいます。

• 答えは最大で \({36 \choose 18}\) となり、32 bit整数には収まりません。Pythonの整数は任意精度なので、そのまま扱えます。

  ソースコード

import sys
from bisect import bisect_left

def subset_sums_by_count(values):
    n = len(values)
    groups = [[] for _ in range(n + 1)]
    groups[0] = [0]
    used = 0

    for value in values:
        used += 1
        for count in range(used, 0, -1):
            groups[count].extend([s + value for s in groups[count - 1]])

    return groups

def main():
    input = sys.stdin.readline
    N, K, X = map(int, input().split())
    A = list(map(int, input().split()))

    mid = N // 2
    left = subset_sums_by_count(A[:mid])
    right = subset_sums_by_count(A[mid:])

    for sums in right:
        sums.sort()

    answer = 0
    for left_count, left_sums in enumerate(left):
        right_count = K - left_count
        if not (0 <= right_count < len(right)):
            continue

        right_sums = right[right_count]
        right_size = len(right_sums)

        for left_sum in left_sums:
            pos = bisect_left(right_sums, X - left_sum)
            answer += right_size - pos

    print(answer)

if __name__ == "__main__":
    main()

---

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