問題
箱が $N$ 個ある。箱 $i$ は重さ $w_i$、丈夫さ $s_i$、価値 $v_i$ を持つ。
いくつかの箱を選び、好きな順に縦一列に積んで塔を作る。次の条件をすべて満たす塔の、箱の価値の和の最大値を求めよ（箱を 1 つも選ばない塔も認め、その価値は $0$）。
- 塔の各箱について、その箱より上にある箱の重さの和がその箱の丈夫さ $s_i$ 以下
- 塔全体の重さの和が床の耐荷重 $C$ 以下
入力形式
N C
w_1 s_1 v_1
w_2 s_2 v_2
...
w_N s_N v_N制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le1000$ |
| 2 | $1\le C\le2\times10^4$ |
| 3 | $1\le w_i\le10^4$ |
| 4 | $0\le s_i\le10^4$ |
| 5 | $1\le v_i\le10^9$ |
| 6 | 入力はすべて整数 |
入出力例
入力例1
3 10
2 2 20
1 1 30
3 1 40出力例1
70（上から 箱 2、箱 3 と積む。箱 3 の上の重さは 1 で丈夫さ 1 以下。3 つ全部は、どの順でも誰かがつぶれる）
入力例2
4 5
2 10 10
3 0 15
1 1 7
2 2 9出力例2
26入力例3
3 9
3 0 11
5 5 1
1 6 15出力例3
27（上から 箱 1（$s+w=3$）、箱 3（$7$）、箱 2（$10$）。箱 3 の上は 3 ≤ 6、箱 2 の上は 4 ≤ 5、全体 9 ≤ 9。丈夫さ $s$ の小さい順に積むと箱 2 が箱 3 より上に来て、箱 3 の上が 8 > 6 になり 26 しか取れない。3 例とも全探索で確認）
背景と出典
AtCoder の Educational DP Contest の X 問題「Tower」がこの形（床の耐荷重なし、$N\le1000$、$w,s\le10^4$）だった、と私は記憶している（原典は本セッションでは未確認）。本問は床の耐荷重 $C$ を足した自作の言い換えで、$C$ は DP 配列の長さの上限になるだけ。
交換議論: 隣り合う 2 箱 $a$（上）と $b$（下）を考える。その上の重さを $X$ とすると、条件は $X\le s_a$ かつ $X+w_a\le s_b$。入れ替えると $X\le s_b$ かつ $X+w_b\le s_a$。2 つの条件のうち厳しい方は、それぞれ $X\le\min(s_a,\ s_b-w_a)$ と $X\le\min(s_b,\ s_a-w_b)$ で、
$$s_a+w_a\le s_b+w_b \iff s_b-w_a\ge s_a-w_b$$
なので、$s+w$ が小さい方を上に置けば、上限は入れ替える前より小さくならない。だから上から $s+w$ の小さい順に積む塔だけを考えればよい。
概念図
ヒント（クリックで段階的に開示）
ヒント1（方向性）
選んだ箱の集合が決まれば、積む順は 1 通りに決めてよいのではないか。隣り合う 2 箱を入れ替えたとき、上に載せられる重さの上限がどう変わるかを書き出す。
ヒント2（アプローチ）
$s+w$ の小さい順にソートして、上から順に「一番下に足す」形で DP する。状態は「いまの塔の重さ $t$」。箱 $i$ を一番下に足せるのは $t\le s_i$ のとき。
ヒント3（誘導）
dp[t] = 重さ $t$ の塔の価値の最大。箱 $i$ について $t=\min(s_i, C-w_i)$ から $0$ まで下りながら dp[t+w_i] = max(dp[t+w_i], dp[t]+v_i)。答えは max(dp)。更新は合計で最大 $10^7$ 回程度なので、Python でも素直な for 文で間に合う。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def main():
data = sys.stdin.buffer.read().split()
n, cap = int(data[0]), int(data[1])
blocks = []
for i in range(n):
w, s, v = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
blocks.append((s + w, w, s, v))
blocks.sort() # s+w の小さい順 = 上から順に積む
NEG = -(1 << 62) # 到達不能。v を何度足しても負のまま（v の総和 ≤ 10^12）
dp = [0] + [NEG] * cap # dp[t]: 上から積んだ塔の総重量が t のときの価値の最大
for _, w, s, v in blocks:
if w > cap:
continue
hi = min(s, cap - w) # いまの重さ t ≤ s のときだけ、この箱を一番下に足せる
if hi < 0:
continue
# 右辺のスライスは代入前に複製されるので、同じ箱を 2 回使うことはない（0/1 ナップサック）
dp[w:w + hi + 1] = map(max, dp[w:w + hi + 1], map(v.__add__, dp[:hi + 1]))
print(max(dp))
main()計算量: ソート $O(N\log N)$、DP は箱ごとに $\min(s_i,C-w_i)+1$ 個の更新で $O(N\cdot\min(\max s, C))$、最大 $10^7$ 回。$N=1000$、$C=2\times10^4$（更新の合計 $5.0\times10^6$〜$7.5\times10^6$ 回）で 0.36〜0.53 s（Python 3.14.7、M1 Mac、負荷平均 5〜6 のときの実測）。
Step-by-Step 解説
背景の式の通り、$s_a+w_a\le s_b+w_b$ なら $a$ を上にしても悪くならない。隣り合う逆順の対を 1 つずつ入れ替えていけば、どんな実行可能な塔も「$s+w$ の小さい順」の塔に直せる。だから集合を決めた後の並べ方は考えなくてよい。
上から順に「いまの塔の一番下に新しい箱を足す」と考えると、足せる条件は「いまの塔の重さ $t\le s_i$」だけで、足した後の重さは $t+w_i$。状態は重さ $t$ だけで閉じる。下から積むと「上に何が来るか」がまだ分からないので、状態が閉じない。
各箱は 1 回しか使えない。dp[w:w+hi+1] = map(max, 旧の dp[w:…], v + 旧の dp[:hi+1]) は、右辺のスライスが代入前に複製されるので、同じ箱の更新が同じ箱の更新に連鎖しない。for 文で書く場合は $t$ を大きい方から回す。
塔全体の重さは最後の $t+w_i$ なので、$t\le C-w_i$ を上限に加えるだけでよい。dp の長さを $C+1$ にしておけば、答えは max(dp)。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 部分集合 × 全順列 | $O(2^N\cdot N!)$ | 検算用のみ | $N\le7$ のランダム 500 件の正解に使用 |
| bit DP（使った集合 × 重さ） | $O(2^N\cdot N)$ | 不採用 | $N=1000$ では不可能 |
| $s+w$ 順のナップサック、for 文を $t$ の大きい順に | $O(N\cdot S)$ | どれでもよい | 同じ 3 入力で 0.32〜0.50 s（実測）。読みやすさはこちらが上 |
同じ DP、内包表記で候補を作って zip で比べる | $O(N\cdot S)$ | どれでもよい | 0.33〜0.48 s（実測） |
同じ DP、スライス＋map(max)（本解） | $O(N\cdot S)$ | 採用 | 0.36〜0.53 s（実測）。3 通りの差は 1 割以内で、Python 3.14 では書き方より更新回数が効く。0/1 の取り違えが起きにくい形として採った |
| 価値を軸にした DP（価値ごとの最小重さ） | $O(N\cdot\sum v)$ | 不採用 | $v\le10^9$ では配列が作れない |
前提が変わったら:
- $s,w$ が $10^9$、$v$ が小さいなら、軸を入れ替えて「価値 $V$ を達成する塔の最小重さ」を DP する（箱を足せる条件は「最小重さ $\le s_i$」で、同じ順で成り立つ）
- 箱の個数制限つき（同じ箱が $k_i$ 個）なら、同じ箱どうしは $s+w$ が同じなので連続して積まれる。2 冪分割で $2^j$ 個の束にするとき、束の一番下の箱には束の中の $(2^j-1)w$ が載るので、束の丈夫さは $s-(2^j-1)w$、重さは $2^jw$ にする。すると束の $s'+w'=s+w$ で順は変わらない（導出。本セッションでは未実装・未検証）
- 上に載る「個数」の制限（重さでなく箱の数）なら、比較は $s_i+1$ になり、順は $s$ の小さい順でよい
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 丈夫さ $s$ の小さい順に積む | 「弱い箱を上に」で十分だと思う | $s+w$ の小さい順（500 件中 53 件誤答、実測。入力例 3 が反例） |
| 重さ $w$ の小さい順に積む | 「軽い箱を上に」で十分だと思う | 500 件中 63 件誤答（実測） |
| $s-w$ の小さい順に積む | 交換議論の式の符号を誤る | 500 件中 165 件誤答（実測） |
| 下から積む DP にする | 上に載る重さがまだ決まっていない | 上から積み、一番下に足す形にする |
| 更新を $t$ の小さい順に for 文で回す | 0/1 と個数無制限の取り違え | 大きい順に回すか、旧い配列のスライスから計算する |
次のステップ
- 発展1: $w,s\le10^9$、$v\le100$、$N\le100$ の版を、価値を軸にした DP で解き、全探索で確かめる
- 発展2: 交換議論が効く他の問題（締め切り付きの仕事の並べ替え、Johnson の 2 機械フローショップ）で、比較の式を自分で導く
- 発展3: 原典の EDPC X「Tower」の制約を確かめ、本解で通るか試す（本セッションでは未確認）
検証ログ（本セッションで実行した数値）
- 全探索との照合（実測）: $N\le7$、$w,s$ の上限を 5/10/30 に振り、$C$ を $1$ から（上限 $\times N$）まで選んだランダム 500 件で不一致 0。全探索は部分集合ごとに全順列を試す
- 誤った順（実測）: 同じ 500 件で、$s$ の順 53 件・$w$ の順 63 件・$s-w$ の順 165 件誤答
- 入力例（実測）: 例 1
70、例 226、例 327（全探索と一致。例 3 は $s$ の順だと 26、$w$ の順だと 16） - 実行時間（実測、負荷平均 5〜6）: $N=1000$、$C=2\times10^4$ で（$w$ 1〜$10^4$、$s$ 0〜$10^4$）0.37 s、（$w$ 1〜10）0.38 s、（$w$ 1〜100、$s$ 5000〜$10^4$）0.53 s。$N=500$ では 0.21〜0.36 s。同じ入力を負荷平均 36 のときに測ると 2.2〜2.9 s で、数字は機械の混み具合で 5 倍以上ぶれる
- 扱っていない範囲: 価値を軸にした DP、個数制限つきの箱、原典の確認