EDPC X Tower

EDPC X Tower 考察ノート

https://atcoder.jp/contests/dp/tasks/dp_x

問題文要約

N 個のブロックはそれぞれ重さ w_i、耐荷重 s_i、価値 v_i を持っています。
価値の総和が最大になるようにブロックを積んでください。

• 1 \le N \le 10^3
• 1 \le w_i, s_i, \le 10^4
• 1 \le v_i \le 10^9

考察

• ブロックを積んでしまえば、積む順番によらず重さと価値の総和が決まる。上から積んでいくDP？
• 耐久値が小さいものほど上に積みたい。同時に、軽いものほど上に積みたい。両方のバランスをとる必要がある。

• 積む順番を決めてナップザックDP。ナイーブには計算量が O(N!\times \sum_i s_i) で話にならない。順列はダメ。
• ２つのブロックを使える場合にどちらが上にあるか決まる「積むための十分条件」があれば、ナップザックDPできる。正確には、一方が他方より常に上にあるようにできればよい。

\dag真の積み方\dagがあると思ってみる

• 局所的に考える。s_i \ge w_j \land s_j < w_i とかが成り立つときは明らか。いつも都合よく成り立つはずがない。
• 一般化して「塔の上部の重さが W のとき、ブロック i, j をどう積むのが良いか」考えてみる。
• 正順に積むとき、W\le s_i, W+w_i\le s_j が成り立つ。逆順なら W\le s_j, W+w_j\le s_i
• 整理すると、W\le \min(s_i, s_j-w_i) \lor W\le \min(s_j, s_i-w_j)

• W がでかい方が良い。

1. s_i\le s_j-w_i \land s_j \le s_i-w_j のとき、耐荷重が大きい方が上。
2. s_i\ge s_j-w_i \land s_j \le s_i-w_j のとき、j が上。
3. s_i\le s_j-w_i \land s_j \ge s_i-w_j のとき、i が上。
4. s_i\ge s_j-w_i \land s_j \ge s_i-w_j のとき、s+wが小さい方が上。同じならどっちでもよい。

• s+w が小さい方が上？

1. s_i \le s_j \Rarr s_i+w_i \le s_j \le s_j+w_j \land s_j+w_j \le s_i \le s_i+w_i より s_i=s_j, w_i=w_j=0 となり、w\ge 1 に矛盾。w=0 が許される場合、重さが変わらないのでどっちでもいい。
2. s_j+w_j \le s_i < s_i+w_i より s+w が小さい方が上。
3. s_i+w_i \le s_j < s_j+w_j より s+w が小さい方が上。
4. s+w が小さい方が上。

• \dag真の積み方\dagは実在する！

結論

s+w が小さい順に並べて、ナップザックDP
https://atcoder.jp/contests/dp/submissions/55727037