概要

\(N\) 個のお菓子から、値段の合計がちょうど \(S\) 円になるような選び方の数を求める問題です。半分全列挙（Meet in the Middle）を使って効率的に解きます。

考察

素朴なアプローチの問題点

各お菓子を「選ぶ」か「選ばない」かの \(2\) 通りがあるため、全ての選び方は \(2^N\) 通りあります。

• \(N \leq 20\) 程度なら、\(2^{20} \approx 10^6\) なので全列挙で間に合います
• しかし \(N \leq 40\) の場合、\(2^{40} \approx 10^{12}\) となり、全列挙は不可能です

重要な気づき

\(N\) 個の要素を半分に分けて考えると： - 前半 \(N/2\) 個の部分集合の和：\(2^{20} \approx 10^6\) 通り - 後半 \(N/2\) 個の部分集合の和：\(2^{20} \approx 10^6\) 通り

前半から和 \(s_1\)、後半から和 \(s_2\) を選んだとき、\(s_1 + s_2 = S\) となればよいです。 つまり、前半の各和 \(s_1\) に対して、後半で \(S - s_1\) となる和の個数を高速に数えられれば解けます。

アルゴリズム

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

手順

1. 前半の列挙: お菓子を前半 \(N/2\) 個と後半 \(N - N/2\) 個に分ける
2. 部分集合の和を計算:
   • 前半の全 \(2^{N/2}\) 個の部分集合について、値段の合計を求めてリスト first_sums に格納
   • 後半も同様に second_sums に格納
3. ソートと二分探索:
   • second_sums をソートする
   • first_sums の各要素 \(s\) について、second_sums の中で \(S - s\) と等しい要素の個数を二分探索で数える

具体例

\(N = 4\), \(S = 5\), \(A = [1, 2, 3, 4]\) の場合：

• 前半 \([1, 2]\) の部分集合の和: \(\{0, 1, 2, 3\}\)
• 後半 \([3, 4]\) の部分集合の和: \(\{0, 3, 4, 7\}\)

前半の和 \(s = 1\) のとき、後半で \(5 - 1 = 4\) を探す → \(1\) 個見つかる（お菓子 \(4\) のみ選ぶ） 前半の和 \(s = 2\) のとき、後半で \(5 - 2 = 3\) を探す → \(1\) 個見つかる（お菓子 \(3\) のみ選ぶ）

このように、\(s_1 + s_2 = S\) となる組み合わせを効率的に数えます。

計算量

• 時間計算量: \(O(2^{N/2} \cdot N/2 + 2^{N/2} \log 2^{N/2}) = O(N \cdot 2^{N/2})\)
  • 部分集合の列挙と和の計算: \(O(N \cdot 2^{N/2})\)
  • ソート: \(O(2^{N/2} \cdot N/2)\)
  • 二分探索を \(2^{N/2}\) 回: \(O(2^{N/2} \cdot N/2)\)
• 空間計算量: \(O(2^{N/2})\)
  • 前半・後半それぞれの部分集合の和を格納

\(N = 40\) のとき、\(2^{20} \appro 10^6\) なので十分高速です。

実装のポイント

• ビットマスクで部分集合を列挙: mask の \(i\) ビット目が \(1\) なら \(i\) 番目の要素を選ぶ

• 二分探索で個数を数える: bisect_left と bisect_right の差で、ある値と等しい要素の個数が求まる

• オーバーフローに注意: \(S\) や \(A_i\) が \(10^{12}\) と大きいが、Python は多倍長整数なので問題なし

• 空集合も考慮: マスクが \(0\) のとき和は \(0\) となり、これも有効な選び方（何も選ばない）として扱う

  ソースコード

import sys
from collections import defaultdict
from bisect import bisect_left, bisect_right

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    S = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # 半分全列挙 (Meet in the Middle)
    # N個の要素を半分に分けて、それぞれで全ての部分集合の和を列挙
    
    half = N // 2
    first_half = A[:half]
    second_half = A[half:]
    
    # 前半の全部分集合の和を列挙
    first_sums = []
    for mask in range(1 << len(first_half)):
        total = 0
        for i in range(len(first_half)):
            if mask & (1 << i):
                total += first_half[i]
        first_sums.append(total)
    
    # 後半の全部分集合の和を列挙
    second_sums = []
    for mask in range(1 << len(second_half)):
        total = 0
        for i in range(len(second_half)):
            if mask & (1 << i):
                total += second_half[i]
        second_sums.append(total)
    
    # 後半のリストをソート
    second_sums.sort()
    
    # 前半の各和に対して、後半から S - sum となる要素の個数を二分探索で数える
    ans = 0
    for s in first_sums:
        target = S - s
        if target < 0:
            continue
        # second_sums の中で target と等しい要素の個数を数える
        left = bisect_left(second_sums, target)
        right = bisect_right(second_sums, target)
        ans += right - left
    
    print(ans)

solve()

---

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