概要

\(N\) 個の商品から1個以上選んで合計金額がちょうど \(S\) 円になる選び方の数 \(C\) を求め、\(C=0\), \(C=1\), \(C \geq 2\) のいずれかを判定する部分集合の和の問題です。

考察

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

全ての部分集合を列挙して合計を調べる方法では、\(2^N\) 通りを調べる必要があります。\(N \leq 40\) のとき \(2^{40} \approx 10^{12}\) となり、時間制限に間に合いません。

重要な気づき

• \(N \leq 40\) という制約は、半分全列挙（Meet in the Middle） を使うサインです。
• 商品を前半・後半に分割すると、各半分は最大20個。\(2^{20} \approx 10^6\) なので十分高速に全列挙できます。
• \(C\) の正確な値は不要で、\(0\), \(1\), \(2\) 以上のどれかだけ分かればよいため、各部分集合の和の出現回数を 2で打ち切り（cap） できます。

アルゴリズム

1. 商品を2つに分割: 前半 \(A\)（\(\lfloor N/2 \rfloor\) 個）と後半 \(B\)（残り）に分ける。

2. 各半分の部分集合の和を列挙:

   • 前半の全 \(2^{|A|}\) 通りの部分集合について合計 \(s_a\) を計算し、辞書に「合計値 → 出現回数（最大2）」を記録。
   • 後半も同様に辞書を作成。

3. 組み合わせ: 前半の各合計 \(s_a\) に対して、後半で \(S - s_a\) となる部分集合があるか辞書を参照。出現回数の積を加算して合計カウントを求める。合計が2以上になった時点で打ち切り。

4. 空集合の扱い: mask=0（何も選ばない）は合計0を生成しますが、\(S \geq 1\) なので「前半も後半も空」のケースが \(S\) に一致することはありません。「前半が空で後半から選ぶ」「後半が空で前半から選ぶ」は1個以上選んでいるので有効です。

5. capの正当性:

   • capped total \(\geq 2\) → 実際の total \(\geq 2\)（capは過小評価しかしないので）
   • capped total \(= 1\) → 唯一の寄与は \(c_a = 1, c_b = 1\) の組。もし実際の個数がどちらか2以上なら、capされた値も2になり積が2以上になるはず。よって実際も1。
   • capped total \(= 0\) → 実際も0。

計算量

• 時間計算量: \(O(2^{N/2} \cdot N/2)\)（各半分の全列挙にビットごとの加算）
  • \(N=40\) のとき約 \(2^{20} \times 20 \approx 2 \times 10^7\) 程度
• 空間計算量: \(O(2^{N/2})\)（辞書に格納する部分集合の和の数）

実装のポイント

• 辞書のcap: 出現回数を2で打ち切ることで、巨大なカウントを扱う必要がなくなり、判定もシンプルになる。

• 早期終了: 組み合わせフェーズで合計が2以上になったら即座にループを抜けられる。

• \(S\) の値が \(10^{18}\) と大きい: Pythonは多倍長整数を自然に扱えるため、オーバーフローの心配は不要。C++等では注意が必要。

• \(N\) が小さい場合（例: \(N=1\)）でも正しく動作するよう、半分の分割は \(\lfloor N/2 \rfloor\) と \(N - \lfloor N/2 \rfloor\) で行う。

  ソースコード

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    S = int(input_data[1])
    P = [int(input_data[i+2]) for i in range(N)]
    
    # Meet in the middle approach
    # Split into two halves
    half1 = N // 2
    half2 = N - half1
    
    A = P[:half1]
    B = P[half1:]
    
    # Enumerate all subset sums for each half
    # We only need to know if total count is 0, 1, or >=2, so we can cap counts at 2
    
    def enum_sums(items):
        """Return a dict: sum -> count of subsets achieving that sum, capped at 2"""
        sums = defaultdict(int)
        n = len(items)
        for mask in range(1 << n):
            s = 0
            for i in range(n):
                if mask & (1 << i):
                    s += items[i]
            if sums[s] < 2:
                sums[s] += 1
            # We keep going but cap at 2
        return sums
    
    def enum_sums_capped(items):
        """Return a dict: sum -> min(count, 2)"""
        sums = defaultdict(int)
        n = len(items)
        for mask in range(1 << n):
            s = 0
            for i in range(n):
                if mask & (1 << i):
                    s += items[i]
            if sums[s] < 2:
                sums[s] += 1
        return sums
    
    sums_a = enum_sums_capped(A)
    sums_b = enum_sums_capped(B)
    
    # For each sum_a in sums_a, we need sum_b = S - sum_a in sums_b
    # But note: mask=0 means selecting nothing from that half
    # We need at least 1 item total, so we can't have both masks = 0
    # mask=0 gives sum=0 for both halves
    # So the pair (0,0) from A and B would give sum=0 selecting 0 items - invalid
    # We need to handle: total count of ways to get sum S with at least 1 item
    
    # Count C = sum over all (mask_a, mask_b) where sum_a + sum_b = S and not (mask_a=0 and mask_b=0)
    # = sum over all pairs where sum_a + sum_b = S, minus the case where both are empty (sum=0, which equals S only if S=0)
    
    # Since S >= 1 (from constraints S >= 1), the empty+empty case (sum=0) never equals S.
    # So we just compute the total.
    
    total = 0
    for sa, ca in sums_a.items():
        need = S - sa
        if need in sums_b:
            cb = sums_b[need]
            total += ca * cb
            if total >= 2:
                break
    
    # But wait, we need to be more careful. ca and cb are capped at 2.
    # If ca=2 and cb>=1, then ca*cb >= 2, so total >= 2.
    # If ca=1 and cb=2, same.
    # If ca=1 and cb=1, contribution is 1, and we need to check if there are more pairs.
    # The issue is we might miss counting if we break too early but total is already >=2.
    # Actually once total >= 2 we can break.
    
    # However, we also need to exclude the case where both halves select nothing (mask=0).
    # mask=0 contributes sum=0. If S=0 this would be a problem, but S>=1 so no issue.
    # But actually we DO include mask_a=0 (selecting nothing from A) combined with mask_b selecting items from B.
    # That's valid (at least 1 item from B). Similarly mask_b=0 with items from A. Both are fine.
    
    if total >= 2:
        # Need to recheck: could total be inflated? No, caps at 2 per side means 
        # if true count on one side is >=2, we record 2, which could undercount.
        # But we only need to know if total >= 2, and if we get >= 2 with capped counts, real is also >= 2.
        print("YES")
    elif total == 0:
        print("NO")
    else:
        # total == 1 with capped counts. Since capping can only decrease counts,
        # if capped total is 1, real total is also exactly 1.
        # Wait, no. Capping could make real total > capped total. But capped >= real? No, capped <= real.
        # If capped total = 1, real total >= 1. Could real total be > 1?
        # No: if real total were >=2, then capped total >= 2 (since each ca*cb with cap is <= real ca*real cb).
        # Hmm actually that's not necessarily true. But since we cap at 2 and multiply, 
        # min(rc,2)*min(rb,2) >= min(rc*rb, 2) is not always true... but sum could be tricky.
        # Actually since total=1, there's exactly one (sa, S-sa) pair contributing, with ca=1, cb=1.
        # Real ca >= 1, real cb >= 1, so real contribution >= 1. If real ca or cb > 1, capped would be 2, giving total >=2.
        # So real total = 1.
        print("ALMOST")

solve()

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