概要

\(N\) 個のアイテムからいくつか選び、その合計をちょうど \(S\) にする組み合わせの数を求める問題です。これは「部分和問題」と呼ばれる有名な問題の一種ですが、制約に応じて適切な手法を選択する必要があります。

考察

1. 素朴な全探索（ビット全探索）

各お菓子について「買う」か「買わない」かの 2 択があるため、すべての組み合わせは \(2^N\) 通り存在します。 今回の制約は \(N \leq 40\) です。\(2^{40} \approx 1.1 \times 10^{12}\) となり、制限時間内（通常 \(10^8\) 回程度の計算が限界）にすべてを調べることは不可能です。

2. 動的計画法 (DP)

合計が \(S\) になる組み合わせを数える際、通常は dp[i][j] = (i番目まで見て合計がjになる通り数) という DP が使われます。 しかし、今回の制約では \(S \leq 10^{12}\) と非常に大きいため、配列のサイズを確保できず、計算量 \(O(NS)\) も間に合いません。

3. 半分全列挙 (Meet-in-the-middle)

\(N=40\) では間に合いませんが、もし \(N=20\) であれば \(2^{20} \approx 10^6\) であり、十分に計算可能です。 そこで、お菓子を前後の 2 グループ（\(N/2\) 個ずつ）に分けて別々に全列挙する「半分全列挙」という手法をとります。

1. 前半 \(N/2\) 個のお菓子で作れる合計金額をすべて列挙し、それぞれの出現回数を記録する。
2. 後半の残りのお菓子で作れる合計金額をすべて列挙する。
3. 後半のある組み合わせの合計が \(s_2\) 円だったとき、合計を \(S\) 円にするには前半で \(S - s_2\) 円を作る必要があります。前半の結果から \(S - s_2\) 円になる通り数を取得し、合計に加算します。

アルゴリズム

具体的には以下の手順で実装します。

1. 分割: \(N\) 個の要素を持つ配列 \(A\) を、長さ \(n_1 = N/2\) と \(n_2 = N - n_1\) の 2 つの配列 \(A_1, A_2\) に分割します。
2. 前半の全列挙: \(A_1\) の部分和をすべて計算し、ハッシュマップ（Python では collections.Counter）に「合計値：その合計になる組み合わせ数」の形式で保存します。
3. 後半の全列挙と照合: \(A_2\) の部分和 \(s_2\) を 1 つずつ生成します。
   • ターゲットとなる値 \(target = S - s_2\) を計算します。
   • 前半で作ったハッシュマップに \(target\) が存在すれば、その出現回数を答えに加えます。
4. 結果の出力: 最終的な合計値を回答とします。

計算量

• 時間計算量: \(O(2^{N/2})\)
  • 前半の列挙に \(O(2^{N/2})\)、後半の列挙と照合に \(O(2^{N/2})\) かかります。\(N=40\) のとき \(2^{20} \approx 10^6\) なので、制限時間内に余裕を持って動作します。
• 空間計算量: \(O(2^{N/2})\)
  • 前半で作った部分和の出現回数を記録するためのメモリが必要です。

実装のポイント

• 枝刈り: 部分和を計算する途中で、すでに合計が \(S\) を超えている場合はそれ以上お菓子を追加する必要がないため、探索を打ち切ることで高速化・省メモリ化が図れます。

• メモリ管理: Python でリストを拡張していく際、非常に大きなリストになるとメモリを消費します。前半の結果を Counter で集計した後は、元の巨大なリストを del で解放するなどの工夫をすると、メモリ制限が厳しい問題でも安心です。

• 辞書の利用: target in counts1 のようにハッシュマップ（辞書）の検索を使うことで、前半の値を \(O(1)\) で見つけることができます。”`

  ソースコード

import sys
from collections import Counter

def solve():
    # Read all input at once and split into tokens
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of items, S is the target sum
    N = int(input_data[0])
    S = int(input_data[1])
    # A is a list of the prices of the N items
    A = [int(x) for x in input_data[2:]]
    
    # Meet-in-the-middle: split the items into two halves
    # This reduces the complexity from O(2^N) to O(2^(N/2))
    n1 = N // 2
    A1 = A[:n1]
    A2 = A[n1:]
    
    # Function to generate all possible subset sums that do not exceed S
    def get_sums(arr, limit):
        subset_sums = [0]
        for x in arr:
            # Create new sums by adding the current item x to all existing subset sums
            # Filter out any sums that already exceed the target S
            new_vals = [s + x for s in subset_sums if s + x <= limit]
            subset_sums.extend(new_vals)
        return subset_sums
    
    # Generate all possible sums for the first half
    sums1 = get_sums(A1, S)
    # Use Counter to store the frequency of each possible sum in the first half
    counts1 = Counter(sums1)
    
    # Free the memory used by the list of sums for the first half
    del sums1
    
    # Generate all possible sums for the second half
    sums2 = get_sums(A2, S)
    
    # For each sum in the second half, find how many matching sums 
    # from the first half result in a total sum equal to exactly S.
    total_ways = 0
    for s2 in sums2:
        target = S - s2
        if target in counts1:
            total_ways += counts1[target]
            
    # Output the final count of ways to achieve the target sum S
    sys.stdout.write(str(total_ways) + '\n')

if __name__ == '__main__':
    solve()

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