概要

各薬品には「使わない・通常モード・加熱モード」の3通りの選択肢があるので、全探索すると \(3^N\) 通りになります。
これをそのまま調べるのは大きすぎるため、半分全列挙（Meet-in-the-Middle）で \(3^{N/2}\) 程度まで落として判定します。

考察

1つの薬品ごとに選択肢は次の3つです。

• 使わない（\(+0\)）
• 通常モード（\(+A_i\)）
• 加熱モード（\(+B_i\)）

したがって、素朴に全探索すると状態数は \(3^N\)。
最大 \(N=26\) なので、\(3^{26}\) は非常に大きく、現実的な時間では終わりません。

ここで重要な気づきは、

• 「前半の薬品で作れる量」
• 「後半の薬品で作れる量」

を別々に列挙し、最後に合成できるということです。

もし前半で作れる量を \(s\) とすると、全体で \(K\) にするには後半で \(K-s\) を作れればよいです。
つまり、

• 前半の全候補和を列挙
• 後半の全候補和を列挙して集合（set）に入れる
• 各 \(s\) について \(K-s\) が後半集合にあるか確認

で判定できます。

これが Meet-in-the-Middle の典型形です。

アルゴリズム

1. 薬品列を前半 left と後半 right に分割する（サイズは約半分ずつ）。
2. 前半について、可能な合計量を全列挙して sums_left を作る。
   初期値 [0] から始め、各薬品 \((a,b)\) に対して
   • そのまま（使わない）
   • +a（通常）
   • +b（加熱） を追加して更新する。
3. 後半についても同様に sums_right を作る。
4. sums_right を set にして高速検索可能にする。
5. sums_left の各 s について、K - s が set_right にあれば Yes。
6. 最後まで見つからなければ No。

イメージ例

例えば前半で作れる量が {0, 2, 5}、後半で作れる量が {0, 3, 7}、目標 \(K=8\) のとき：

• 前半 \(s=5\) を選ぶと、必要な後半は \(8-5=3\)
• 後半集合に \(3\) があるので達成可能 → Yes

計算量

• 時間計算量: \(O(3^{N/2})\)（厳密には前半列挙 \(O(3^{n_1})\)、後半列挙 \(O(3^{n_2})\)、照合 \(O(3^{n_1})\)）
• 空間計算量: \(O(3^{N/2})\)

\(N \le 26\) なら \(3^{13}=1,594,323\) 程度なので、Pythonでも十分現実的です。

実装のポイント

• 初期状態を sums = [0] にすることで、「何も選ばない」ケースを自然に含められます（\(K=0\) にも対応）。

• 後半は set 化して in 判定を平均 \(O(1)\) にするのが重要です。

• K や A_i,B_i は大きいですが、Python の整数は多倍長なのでオーバーフローを気にせず扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]

    n1 = N // 2
    n2 = N - n1
    left = AB[:n1]
    right = AB[n1:]

    sums_left = [0]
    for a, b in left:
        new = []
        for s in sums_left:
            new.append(s)        # not used
            new.append(s + a)    # normal mode
            new.append(s + b)    # heated mode
        sums_left = new

    sums_right = [0]
    for a, b in right:
        new = []
        for s in sums_right:
            new.append(s)
            new.append(s + a)
            new.append(s + b)
        sums_right = new

    set_right = set(sums_right)

    for s in sums_left:
        if K - s in set_right:
            print("Yes")
            return
    print("No")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。