競技プログラミング 知識集積所

EDPC X - Tower

塔

問題ページ解答例

考え方

ABCでいうと、F問題級。
ただし、考察が重いという意味ではARC寄りかもしれない。

まず、使うブロックを決めたときに、それで塔を作れるかを高速に判定したい。
そこで、$(w_1,s_1)$ のブロックと $(w_2,s_2)$ のブロックの、どちらを上にするべきかを考えてみる。
この上には重さ合計 $w_0$ のものが乗っていて、下に丈夫さ $s_3$ のものがあるとする。

$w_1,s_1$ のを上に使う場合、壊れないためには以下の $3$ つが全て成り立つ必要がある。

逆に $w_2,s_2$ のを上に使う場合、壊れないためには以下の $3$ つが全て成り立つ必要がある。

これらの一方だけが満たされる状況がどんなときに発生しうるかを考える。

第 $3$ 式は共通なので、どちらを上に使うのがいいかに影響しない。
また、第 $1$ 式が満たされない場合、相手側の第 $2$ 式が成り立たなくなるので、これも影響しない。
すなわち、第 $2$ 式が片方だけ満たされる状況が、一方だけが満たされる状況となりうる。

それぞれの第 $2$ 式を以下のように変形すると、話が分かりやすくなる。

片方だけ壊れる可能性があるとすれば、それは $s+w$ の値が小さい方を下にしたときだけ。
つまり、$s+w$ の値が小さいものほど優先的に上に置く順で壊れるなら、どんな順でも壊れるのである。
ということで、ブロックを積む順は、$s+w$ が小さい順に上から並べる貪欲法でよい。

以上より、最初から全部 $s+w$ を小さい順に並べた上で、条件付きナップサック問題を解けばよい。

$s_i+w_i$ の最大値を $M$ とすると、計算量は $O(N\log N+NM)$。

入力例1での動作

入力を受け取る。

n: 3
(w, s, v):
  (2, 2, 20)
  (2, 1, 30)
  (3, 1, 40)

各ブロックの $w+s$ を求め、小さい順に上から使う順序へ並べる。

順番 $w+s$ $w$ $s$ $v$
$1$ $3$ $2$ $1$ $30$
$2$ $4$ $2$ $2$ $20$
$3$ $4$ $3$ $1$ $40$

この順番を崩さずに、使うブロックだけを選ぶ。

状態として、現在の塔の総重量ごとに最大価値を持つ。
総重量がちょうど $j$ の状態から、次のブロックを塔の下へ追加すると考える。

重さ $w$、丈夫さ $s$ のブロックを追加できるのは、現在の塔の総重量が $s$ 以下の場合だけである。

最初は空の塔だけなので、総重量 $0$、価値 $0$ の状態だけがある。

重さ 0: 価値 0

最初のブロックは $(w,s,v)=(2,1,30)$ である。

空の塔の重さは $0\leq1$ なので、このブロックを下に追加できる。
総重量 $2$、価値 $30$ の状態ができる。

重さ 0: 価値 0
重さ 2: 価値 30

次のブロックは $(2,2,20)$ である。

総重量 $2$ の塔の下には置ける。
追加すると、総重量 $4$、価値 $50$ になる。

空の塔の下に置く場合は、総重量 $2$、価値 $20$ になる。
しかし同じ総重量 $2$ には価値 $30$ の状態が既にあるので、こちらは採用しない。

重さ 0: 価値 0
重さ 2: 価値 30
重さ 4: 価値 50

最後のブロックは $(3,1,40)$ である。

このブロックの上に載せられる重さは $1$ 以下である。
現在ある状態では、空の塔だけが条件を満たす。

したがって、総重量 $3$、価値 $40$ の状態が増える。

重さ 0: 価値 0
重さ 2: 価値 30
重さ 3: 価値 40
重さ 4: 価値 50

最も大きい価値は $50$ なので、答えは $50$。

注意点

答えは int 型からはみ出る

答えは、int 型からはみ出る。
long long 型を用いること。

重さ上限は、$s+w$ の最大値まででよい

全ブロックの $w$ の合計を上限に取ると、DPテーブルが大きくなりすぎる。
塔の重さの合計は最下段の $s+w$ を超えないことに注目し、テーブルの大きさを制限すること。

「重さ $W$ ぴったり」でDPテーブルをつくる。

通常のナップサックは「重さ $W$ 以下」でDPテーブルを作る方が楽だが、今回は制約上それが難しい。
「重さ $W$ ぴったり」で表を作り、最後に最大値探索をする。

別解

特になし。