概要

\(N\) 個の薬品に対し、「使わない」「通常モード（\(A_i\) mL）」「加熱モード（\(B_i\) mL）」の 3 通りの選択肢がある中で、合計量をちょうど \(K\) mL にできるかを判定する問題です。

考察

各薬品について 3 通りの選び方があるため、単純にすべての組み合わせを調べようとすると、その計算量は \(3^N\) となります。 本問題の制約は \(N \le 26\) であり、\(3^{26} \approx 2.5 \times 10^{12}\) となるため、制限時間内に全探索を終えることは不可能です。

一方で、もう一つの典型的な手法である動的計画法（DP）を検討すると、目標量 \(K\) が最大 \(10^{15}\) と非常に大きいため、和をインデックスに持つ DP も使えません。

そこで、「半分全列挙（Meet-in-the-middle）」という手法を活用します。 \(N\) 個の要素を半分（\(N/2\) 個ずつ）に分けて別々に全列挙を行うと、各グループの組み合わせ数は \(3^{N/2}\) となります。\(N=26\) の場合、\(3^{13} = 1,594,323\) であり、これは十分に計算可能な範囲に収まります。

アルゴリズム

半分全列挙の手順は以下の通りです。

1. グループの分割: \(N\) 個の薬品を、前半の \(N/2\) 個と後半の残りの個数に分けます。
2. 全列挙（前半）: 前半の薬品について、あり得るすべての合計量を列挙し、集合（Setなど）に格納します。
   • このとき、合計が \(K\) を超えるものは除外して構いません（薬品の量はすべて正であるため）。
3. 全列挙（後半）: 後半の薬品についても、あり得るすべての合計量を列挙します。
4. 照合: 後半のグループで得られたある合計量を \(s_2\) としたとき、前半のグループの集合の中に \(s_1 = K - s_2\) となる値が存在するかを確認します。
   • もし存在すれば、全体で合計 \(K\) を作ることが可能（Yes）です。
   • すべての \(s_2\) を確認しても見つからなければ、不可能（No）です。

計算量

• 時間計算量: \(O(3^{N/2})\)
  • 前半と後半の全列挙にそれぞれ \(3^{N/2}\)、照合に \(3^{N/2}\) の定数倍程度の時間がかかります。\(N=26\) のとき \(3^{13} \approx 1.6 \times 10^6\) なので、Pythonでも高速に動作します。
• 空間計算量: \(O(3^{N/2})\)
  • 前半のグループで作れる合計量を保持するために、最大で \(3^{N/2}\) 個の要素を格納するメモリが必要です。

実装のポイント

• 集合（set）の利用: 前半の合計量を set に格納することで、後半の探索時に「値が存在するか」の判定を平均 \(O(1)\) で行うことができます。

• 枝刈り: 合計が \(K\) を超えた時点でその組み合わせを捨てることで、メモリ消費量と計算時間を抑えることができます。

• 効率的な列挙: 薬品を 1 つずつ見ていき、現在の「あり得る和の集合」に対して、新しい薬品の \(0, A_i, B_i\) を加えた新しい集合を作る、という手順を繰り返すと実装がスムーズです。

  ソースコード

import sys

def solve():
    # Fast input reading from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of drugs, K is the target volume
    N = int(input_data[0])
    K = int(input_data[1])
    
    A = []
    B = []
    for i in range(N):
        A.append(int(input_data[2 + 2*i]))
        B.append(int(input_data[3 + 2*i]))
        
    # Using the meet-in-the-middle technique to reduce complexity from 3^N to 3^(N/2)
    # N <= 26, so 3^26 is too large (~2.5 * 10^12), but 3^13 is manageable (~1.6 * 10^6)
    mid = N // 2
    
    def get_possible_sums(a_part, b_part, target):
        """
        Calculates all possible sums of solution volumes for a given set of drugs.
        Each drug can be used in mode A, mode B, or not at all.
        """
        ps = {0}
        for a, b in zip(a_part, b_part):
            # For each drug, there are three choices for its contribution to the sum:
            # 1. Not used: The sum remains s (already present in ps).
            # 2. Mode A: The sum becomes s + a.
            # 3. Mode B: The sum becomes s + b.
            # Pruning sums that already exceed the target volume K.
            new_a = {s + a for s in ps if s + a <= target}
            new_b = {s + b for s in ps if s + b <= target}
            
            # Update the set of possible sums with the new options
            ps |= new_a
            ps |= new_b
        return ps

    # Generate all possible sums for the two halves of the drugs
    sums1 = get_possible_sums(A[:mid], B[:mid], K)
    sums2 = get_possible_sums(A[mid:], B[mid:], K)
    
    # Meet-in-the-middle check:
    # We need to find if there exists s1 in sums1 and s2 in sums2 such that s1 + s2 = K.
    # This is equivalent to checking if (K - s1) exists in sums2.
    
    # Optimization: Iterate over the smaller set to minimize the number of lookups
    if len(sums1) > len(sums2):
        sums1, sums2 = sums2, sums1
        
    found = False
    for s in sums1:
        if (K - s) in sums2:
            found = True
            break
    
    # Output the result
    if found:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

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