概要

\(N\) 種類の薬品それぞれについて「使わない」「通常モード」「加熱モード」の3択を行い、得られる溶液の合計がちょうど \(K\) mL になるかを判定する問題です。半分全列挙（Meet in the Middle） で効率的に解きます。

考察

素朴なアプローチとその限界

各薬品には「使わない」「通常モード（\(A_i\) mL）」「加熱モード（\(B_i\) mL）」の3つの選択肢があります。\(N\) 個の薬品すべてについて全探索すると、組み合わせ数は \(3^N\) 通りです。

• \(N = 26\) のとき、\(3^{26} \approx 2.5 \times 10^{12}\) 通りとなり、到底間に合いません。

重要な気づき：半分に分ける

\(N\) 個の薬品を前半と後半の2グループに分けると、それぞれ約 \(N/2 = 13\) 個になります。

• \(3^{13} = 1{,}594{,}323\) 通り

これなら各グループの全列挙は十分高速です。前半グループで作れる合計値の集合と、後半グループで作れる合計値の集合をそれぞれ求め、「前半の値 + 後半の値 = \(K\)」となるペアが存在するかを確認すればよいのです。

具体例

\(N=4\), \(K=10\), 薬品が \((3,5), (2,4), (1,6), (7,3)\) のとき：

• 前半 \(\{(3,5), (2,4)\}\) → 合計の候補: \(\{0, 2, 3, 4, 5, 7, 8, 9\}\)
• 後半 \(\{(1,6), (7,3)\}\) → 合計の候補: \(\{0, 1, 3, 4, 6, 7, 8, 9, 10, 13\}\)

前半から \(7\) を取り、後半から \(3\) を取れば \(7 + 3 = 10 = K\) なので Yes です。

アルゴリズム

1. \(N\) 個の薬品を前半（\(\lfloor N/2 \rfloor\) 個）と後半（残り）に分割する。
2. 前半のすべての薬品について3択を全列挙し、可能な合計値の集合 left_sums を作る。
3. 後半も同様に全列挙し、可能な合計値の集合 right_sums を作る（Pythonの set に格納）。
4. left_sums の各要素 \(l\) について、\(K - l\) が right_sums に含まれるかを \(O(1)\) で判定する。
5. 一つでも見つかれば Yes、見つからなければ No を出力する。

列挙の際は、現在の集合に対して各薬品ごとに「そのまま（使わない）」「\(+A_i\)（通常モード）」「\(+B_i\)（加熱モード）」の3パターンを加えていくことで、逐次的に候補を生成します。

計算量

• 時間計算量: \(O(3^{N/2})\)
  • 前半・後半それぞれ \(3^{N/2}\) 個の候補を列挙し、マッチングは set のルックアップにより各 \(O(1)\) で行えます。\(N = 26\) のとき約 \(3^{13} \approx 1.6 \times 10^6\) で十分高速です。
• 空間計算量: \(O(3^{N/2})\)
  • 各グループの合計値候補を set に保持するため。

実装のポイント

• 列挙の実装: set を使い、薬品を1つずつ処理して候補を拡張していくのが簡潔です。

• \(K\) の値が最大 \(10^{15}\): Python は多倍長整数を標準でサポートしているため、オーバーフローの心配はありません。

• \(0\) 個選ぶ場合: 初期値として合計 \(0\) を含めておくことで自然に対応できます（\(K = 0\) のときは何も選ばない場合が該当）。

• 前半・後半の分割: なるべく均等に分けることで、列挙数の最大値を最小化できます。

  ソースコード

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    
    items = []
    for i in range(N):
        a = int(input_data[2 + 2*i])
        b = int(input_data[3 + 2*i])
        items.append((a, b))
    
    # Meet in the middle approach
    # Each item has 3 choices: not used (0), normal mode (A_i), heated mode (B_i)
    # Split into two halves
    
    half1 = N // 2
    half2 = N - half1
    
    def enumerate_sums(item_list):
        """Enumerate all possible sums from a list of items."""
        sums = {0}
        for a, b in item_list:
            new_sums = set()
            for s in sums:
                new_sums.add(s)       # don't use this item
                new_sums.add(s + a)   # normal mode
                new_sums.add(s + b)   # heated mode
            sums = new_sums
        return sums
    
    left_items = items[:half1]
    right_items = items[half1:]
    
    left_sums = enumerate_sums(left_items)
    right_sums = enumerate_sums(right_items)
    
    # Check if any left_sum + right_sum == K
    # Store right_sums in a set, then for each left_sum check if K - left_sum is in right_sums
    right_set = right_sums
    
    for ls in left_sums:
        if K - ls in right_set:
            print("Yes")
            return
    
    print("No")

solve()

---

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