公式

E - 調合と目標量 / Mixing and Target Amount 解説 by admin

GPT 5.4 High

概要

各薬品について「使わない・通常モード・加熱モード」の \(3\) 通りの選択があります。
全探索は \(3^N\) 通りで間に合わないため、薬品を半分ずつに分けて全列挙する 半分全列挙（Meet-in-the-Middle） で解きます。

考察

この問題では、各薬品ごとに次の \(3\) 通りの選択があります。

  • 使わない
  • 通常モードで使う（\(A_i\) mL）
  • 加熱モードで使う（\(B_i\) mL）

したがって、全体の組み合わせ数は \(3^N\) 通りです。
しかし \(N \leq 26\) なので、

\[ 3^{26} \approx 2.5 \times 10^{12} \]

となり、素直に全部試すのは不可能です。

また、よくある「和がちょうど \(K\) になるか」を判定する問題なので DP を考えたくなりますが、この問題では

\[ K \leq 10^{15} \]

と非常に大きいため、和を添字にした DP は使えません。

そこで有効なのが 半分全列挙 です。

薬品を前半と後半に分けます。
それぞれの半分について「作れる合計量」をすべて列挙すれば、

  • 前半で作れる量を \(x\)
  • 後半で作れる量を \(y\)

として、

\[ x + y = K \]

となる組があるかを調べればよいです。

例えば \(N=26\) を \(13\) 個と \(13\) 個に分けると、それぞれの組み合わせ数は最大でも

\[ 3^{13} = 1594323 \]

程度です。
これは現実的な大きさなので、片方を列挙して集合に入れ、もう片方を列挙しながら補数 \(K-y\) があるか確認すれば判定できます。

さらに、この問題では \(A_i, B_i \geq 1\) なので、途中の合計がすでに \(K\) を超えたなら、その先でちょうど \(K\) に戻ることはありません。
そのため、列挙中に

  • \(s + A_i \leq K\)
  • \(s + B_i \leq K\)

のときだけ次へ進めばよく、不要な探索を減らせます。

アルゴリズム

  1. 薬品列を前半 left と後半 right に分ける。
  2. 前半について、各薬品に対して
    • 使わない
    • \(A_i\) を足す
    • \(B_i\) を足す の \(3\) 通りを全列挙し、作れる合計量を left_sums という集合に入れる。
  3. 後半についても同様に全列挙する。
  4. 後半で合計量 \(s\) を作れたとき、前半で \(K-s\) を作れるなら合計でちょうど \(K\) になる。
    つまり

$\( K - s \in \text{left\_sums} \)$

なら答えは Yes。 5. 最後まで見つからなければ No。

このコードでは再帰ではなく、スタックを使った DFS で全列挙しています。
状態は

  • 今どの薬品まで見たか
  • 現在の合計量

の 2 つです。

各状態からの遷移は次の 3 通りです。

  • その薬品を使わない
  • 通常モードで使う
  • 加熱モードで使う

イメージ

例えば前半で作れる量が

\[ \{0, 3, 5, 8\} \]

だったとします。
後半を列挙していて \(s=7\) が作れたなら、

\[ K-s \]

が前半に存在するかを見ます。
もし \(K=15\) なら \(15-7=8\) なので、前半の \(8\) と後半の \(7\) を合わせてちょうど \(15\) が作れます。

計算量

  • 時間計算量: \(O\left(3^{\lfloor N/2 \rfloor} + 3^{\lceil N/2 \rceil}\right)\)
  • 空間計算量: \(O\left(3^{\lfloor N/2 \rfloor}\right)\)

\(N \leq 26\) なので、最大でもおおよそ \(3^{13}\) 程度の全列挙を 2 回行うだけで済みます。

実装のポイント

  • 各薬品には「使わない」選択肢もあるので、初期状態の合計 \(0\) を必ず含めます。
    そのため \(K=0\) の場合も正しく判定できます。

  • 合計が \(K\) を超えた状態は、それ以降すべて正の量しか足されないので探索不要です。

  • 前半の合計量は set に入れることで、重複を自動で除けます。

  • 再帰でも書けますが、コードではスタックを使って反復的に DFS をしています。これにより再帰の深さを気にせず実装できます。

    ソースコード

import sys

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

    m = N // 2
    left = AB[:m]
    right = AB[m:]

    left_sums = set()

    stack_i = [0]
    stack_s = [0]
    llen = len(left)

    while stack_i:
        i = stack_i.pop()
        s = stack_s.pop()

        if i == llen:
            left_sums.add(s)
            continue

        a, b = left[i]
        ni = i + 1

        stack_i.append(ni)
        stack_s.append(s)

        x = s + a
        if x <= K:
            stack_i.append(ni)
            stack_s.append(x)

        y = s + b
        if y <= K:
            stack_i.append(ni)
            stack_s.append(y)

    stack_i = [0]
    stack_s = [0]
    rlen = len(right)

    while stack_i:
        i = stack_i.pop()
        s = stack_s.pop()

        if i == rlen:
            if K - s in left_sums:
                print("Yes")
                return
            continue

        a, b = right[i]
        ni = i + 1

        stack_i.append(ni)
        stack_s.append(s)

        x = s + a
        if x <= K:
            stack_i.append(ni)
            stack_s.append(x)

        y = s + b
        if y <= K:
            stack_i.append(ni)
            stack_s.append(y)

    print("No")

if __name__ == "__main__":
    main()

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