E - 宝箱の選択 / Choosing Treasure Chests 解説 by admin
Claude 4.5 Opus概要
0-1ナップサック問題において、各アイテムが最適解に含まれる可能性があるかどうかを判定する問題です。
考察
問題の本質
通常のナップサック問題では「最大価値」を求めれば終わりですが、この問題では「各アイテムが最適解の一部になり得るか」を判定する必要があります。
素朴なアプローチとその問題点
各アイテム \(k\) について、「アイテム \(k\) を必ず選んだ場合の最大価値」を求め、それが全体の最大価値と一致するか確認すれば良いです。
しかし、愚直に毎回DPを計算し直すと \(O(N^2 M)\) となり、制約（\(N \leq 1000, M \leq 3000\)）では TLE になる可能性があります。
解決策：prefix と suffix を使った分割
アイテム \(k\) を必ず選ぶ場合を考えると、残りのアイテムは「\(k\) より前のアイテム（\(0\) ～ \(k-1\)）」と「\(k\) より後のアイテム（\(k+1\) ～ \(N-1\)）」に分けられます。
そこで： - prefix[i][w]: アイテム \(0\) ～ \(i-1\) から選んで、重さがちょうど \(w\) のときの最大価値 - suffix[i][w]: アイテム \(i\) ～ \(N-1\) から選んで、重さがちょうど \(w\) のときの最大価値
を事前計算しておきます。
すると、アイテム \(k\)（重さ \(a\)、価値 \(b\)）を必ず選んだ場合の最大価値は： $\(\max_{w_1 + a + w_2 \leq M} \left( \text{prefix}[k][w_1] + b + \text{suffix}[k+1][w_2] \right)\)$ で求められます。
さらなる高速化
上記の計算で \(w_1\) と \(w_2\) の二重ループを回すと \(O(M^2)\) かかってしまいます。
そこで suffix_max[i][w] = \(\max_{0 \leq j \leq w} \text{suffix}[i][j]\)（累積最大値）を事前計算しておきます。
すると、\(w_1\) を固定したとき、\(w_2 \leq M - a - w_1\) を満たす最大の suffix 値は \(O(1)\) で取得できます。
アルゴリズム
- prefix DP の計算: アイテムを前から順に処理し、各重さでの最大価値を記録
- suffix DP の計算: アイテムを後ろから順に処理し、各重さでの最大価値を記録
- suffix_max の計算: suffix の累積最大値を計算
- 全体の最大価値を求める: prefix[N] の最大値
- 各アイテムについて判定:
- アイテム \(k\) を必ず選んだ場合の最大価値を計算
- それが全体の最大価値と一致すれば
Yes、そうでなければNo
計算量
- 時間計算量: \(O(NM)\)
- prefix, suffix の計算: 各 \(O(NM)\)
- suffix_max の計算: \(O(NM)\)
- 各アイテムの判定: \(O(M)\) × \(N\) 個 = \(O(NM)\)
- 空間計算量: \(O(NM)\)
- prefix, suffix, suffix_max の配列
実装のポイント
-INF の扱い: 「その重さでは達成不可能」を表すために負の無限大を使用。初期状態は prefix[0][0] = suffix[N][0] = 0 のみ達成可能。
「ちょうど w」のDP: 通常のナップサックでは「w 以下」で最大化しますが、この問題では前後を組み合わせるため「ちょうど w」で計算する必要があります。
累積最大値の活用: suffix_max を使うことで、\(w_2\) のループを省略し、各アイテムの判定を \(O(M)\) に抑えています。
重さの上限に注意: アイテム \(k\) を選ぶので、prefix 側で使える重さは最大 \(M - a\) までです（\(w_1 + a + w_2 \leq M\) の制約）。
ソースコード
def solve():
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
items = []
for _ in range(N):
a, b = map(int, input().split())
items.append((a, b))
INF = float('inf')
# prefix[i][w] = items[0..i-1]から重さちょうどwで得られる最大価値（不可能なら-INF）
# suffix[i][w] = items[i..N-1]から重さちょうどwで得られる最大価値（不可能なら-INF）
# prefixの計算
prefix = [[-INF] * (M + 1) for _ in range(N + 1)]
prefix[0][0] = 0
for i in range(N):
a, b = items[i]
for w in range(M + 1):
if prefix[i][w] == -INF:
continue
# 選ばない
if prefix[i + 1][w] < prefix[i][w]:
prefix[i + 1][w] = prefix[i][w]
# 選ぶ
if w + a <= M:
if prefix[i + 1][w + a] < prefix[i][w] + b:
prefix[i + 1][w + a] = prefix[i][w] + b
# suffixの計算
suffix = [[-INF] * (M + 1) for _ in range(N + 1)]
suffix[N][0] = 0
for i in range(N - 1, -1, -1):
a, b = items[i]
for w in range(M + 1):
if suffix[i + 1][w] == -INF:
continue
# 選ばない
if suffix[i][w] < suffix[i + 1][w]:
suffix[i][w] = suffix[i + 1][w]
# 選ぶ
if w + a <= M:
if suffix[i][w + a] < suffix[i + 1][w] + b:
suffix[i][w + a] = suffix[i + 1][w] + b
# 全体の最大価値
max_value = max(prefix[N][w] for w in range(M + 1))
# 各アイテムについて判定
results = []
for k in range(N):
a, b = items[k]
# items[k]を必ず選ぶ場合の最大価値
# prefix[k][w1] + b + suffix[k+1][w2] where w1 + a + w2 <= M
can_include = False
for w1 in range(M + 1 - a):
if prefix[k][w1] == -INF:
continue
# w1 + a + w2 <= M => w2 <= M - a - w1
max_w2 = M - a - w1
# suffix[k+1][0..max_w2]の最大値が必要
# これを高速化するために、suffix_maxを事前計算
for w2 in range(max_w2 + 1):
if suffix[k + 1][w2] == -INF:
continue
total = prefix[k][w1] + b + suffix[k + 1][w2]
if total == max_value:
can_include = True
break
if can_include:
break
results.append("Yes" if can_include else "No")
print('\n'.join(results))
# 高速化版
def solve_optimized():
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
items = []
for _ in range(N):
a, b = map(int, input().split())
items.append((a, b))
INF = float('inf')
# prefixの計算
prefix = [[-INF] * (M + 1) for _ in range(N + 1)]
prefix[0][0] = 0
for i in range(N):
a, b = items[i]
for w in range(M + 1):
if prefix[i][w] == -INF:
continue
if prefix[i + 1][w] < prefix[i][w]:
prefix[i + 1][w] = prefix[i][w]
if w + a <= M:
if prefix[i + 1][w + a] < prefix[i][w] + b:
prefix[i + 1][w + a] = prefix[i][w] + b
# suffixの計算
suffix = [[-INF] * (M + 1) for _ in range(N + 1)]
suffix[N][0] = 0
for i in range(N - 1, -1, -1):
a, b = items[i]
for w in range(M + 1):
if suffix[i + 1][w] == -INF:
continue
if suffix[i][w] < suffix[i + 1][w]:
suffix[i][w] = suffix[i + 1][w]
if w + a <= M:
if suffix[i][w + a] < suffix[i + 1][w] + b:
suffix[i][w + a] = suffix[i + 1][w] + b
# suffix_max[i][w] = max(suffix[i][0], suffix[i][1], ..., suffix[i][w])
suffix_max = [[-INF] * (M + 1) for _ in range(N + 1)]
for i in range(N + 1):
curr_max = -INF
for w in range(M + 1):
if suffix[i][w] > curr_max:
curr_max = suffix[i][w]
suffix_max[i][w] = curr_max
# 全体の最大価値
max_value = max(prefix[N][w] for w in range(M + 1))
# 各アイテムについて判定
results = []
for k in range(N):
a, b = items[k]
can_include = False
for w1 in range(M + 1 - a):
if prefix[k][w1] == -INF:
continue
max_w2 = M - a - w1
best_suffix = suffix_max[k + 1][max_w2]
if best_suffix == -INF:
continue
total = prefix[k][w1] + b + best_suffix
if total == max_value:
can_include = True
break
results.append("Yes" if can_include else "No")
print('\n'.join(results))
solve_optimized()
この解説は claude4.5opus によって生成されました。
投稿日時:
最終更新: