概要

0/1ナップサックの最適価値をDPで求めたうえで、「最適解（複数あり得る）のどれかに含まれる宝箱」を、最適解全体をまとめて逆向きにたどることで判定します。

考察

この問題は典型的な0/1ナップサックですが、求めたいのは最大価値そのものではなく、

• 各宝箱 \(i\) について「宝箱 \(i\) を含む最適解が存在するか」

です。最適解が複数あるのがポイントで、単に1つの最適解を復元して含まれるかを見るだけでは不十分です。

素朴案が厳しい理由

• 各宝箱を「必ず入れる」と固定してナップサックを解き直す、あるいは「除外して」解き直す、などを宝箱ごとに行うと、DPを \(N\) 回回すことになり \(O(N^2M)\) で重いです（\(1000^2 \cdot 3000\) は現実的でない）。
• 最適解を全列挙するのは当然指数時間で不可能です。

解決の方向性

まず通常のDPで「最適価値」をすべての \(i,w\) について計算します（表DP）。 そのあと、DP表上で「最適解に対応する遷移だけ」を逆向きにたどり、最適解になり得る状態を全部まとめて管理します。

DP表は有向非巡回グラフ（DAG）のように見なせます： - 状態 \((i,w)\) から \((i-1,w)\)（宝箱 \(i\) を入れない） - 状態 \((i,w)\) から \((i-1,w-A_i)\)（宝箱 \(i\) を入れる） のどちらか（または両方）が、最適値を保つなら「最適解に沿った遷移」です。

この「最適遷移」を逆にたどっていき、どこかの最適解の経路に 一度でも「入れる遷移」が現れた宝箱は Yes になります。

アルゴリズム

1. DPで最大価値を計算

\(dp[i][w]\) を - 「先頭から \(i\) 個の宝箱だけを使って、容量 \(w\) 以下で得られる最大価値」 とします。

遷移は0/1ナップサックそのものです：

• 入れない：\(dp[i][w] = dp[i-1][w]\)
• 入れる（\(w \ge A_i\)）：\(dp[i][w] = \max(dp[i][w],\ dp[i-1][w-A_i] + B_i)\)

これで最適価値は \(dp[N][M]\) です。

2. 「最適解になり得る状態」を逆向きに同時追跡

最適解が複数あるので、1本の復元ではなく、到達可能な状態集合を持ちます。

• reach[w] = 1 を「現在の段階の状態 \((i,w)\) が、(N,M) から最適遷移だけを辿って到達可能」を表すとします。
• 初期は \((N,M)\) だけなので reach[M]=1。

\(i=N,N-1,\dots,1\) の順に、各到達状態 \((i,w)\) から「最適遷移」だけを \((i-1,*)\) へ伸ばします：

• 入れない遷移が最適なら：
  • 条件：\(dp[i][w] = dp[i-1][w]\)
  • 次も到達可能：\((i-1,w)\)
• 入れる遷移が最適なら：
  • 条件：\(w\ge A_i\) かつ \(dp[i][w] = dp[i-1][w-A_i] + B_i\)
  • 次も到達可能：\((i-1,w-A_i)\)
  • さらに「宝箱 \(i\) を含む最適解が存在」するので included[i]=True

このようにすると、「(N,M) から始まる最適解の経路」を全てまとめて辿れるため、各宝箱について「含む最適解があるか」を漏れなく判定できます。

計算量

• 時間計算量: \(O(NM)\)
  
  • DP作成が \(O(NM)\)、逆向き到達判定も \(O(NM)\)
• 空間計算量: \(O(NM)\)
  
  • \(dp\) 表を全段保持するため \(O(NM)\)（復元に必要）

実装のポイント

• 価値の合計は最大で \(1000 \cdot 10^9 = 10^{12}\) なので 64bit 整数が必要です（Pythonでは通常intでOKですが、高速化のため array('q') を使用）。

• 逆向き探索の到達集合 reach は、長さ \(M+1\) の bytearray にすると高速かつ省メモリです。

• 逆向きでは「等号チェック」で最適遷移かどうかを判断します：

  • \(dp[i][w] == dp[i-1][w]\)（入れないでも最適）

  • \(dp[i][w] == dp[i-1][w-A_i] + B_i\)（入れるのが最適） 両方成り立つ場合もあり、そのときは両方の遷移を残すのが重要です（最適解が分岐するため）。

    ソースコード

import sys
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]

    A = [0] * (N + 1)
    B = [0] * (N + 1)
    p = 2
    for i in range(1, N + 1):
        A[i] = data[p]
        B[i] = data[p + 1]
        p += 2

    # dp[i][w] = max value using first i items with capacity w
    dp = [array('q', [0]) * (M + 1)]
    for i in range(1, N + 1):
        a = A[i]
        b = B[i]
        prev = dp[i - 1]
        cur = array('q', prev)  # exclude by default
        for w in range(a, M + 1):
            v = prev[w - a] + b
            if v > cur[w]:
                cur[w] = v
        dp.append(cur)

    included = [False] * (N + 1)

    # reachable capacities at step i (state (i, w)) along some optimal path from (N, M)
    reach = bytearray(M + 1)
    reach[M] = 1

    for i in range(N, 0, -1):
        a = A[i]
        b = B[i]
        cur = dp[i]
        prev = dp[i - 1]
        next_reach = bytearray(M + 1)

        r = reach
        nr = next_reach
        for w in range(M + 1):
            if not r[w]:
                continue
            v = cur[w]
            if v == prev[w]:
                nr[w] = 1
            if w >= a and v == prev[w - a] + b:
                included[i] = True
                nr[w - a] = 1

        reach = next_reach

    out = []
    for i in range(1, N + 1):
        out.append("Yes" if included[i] else "No")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

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