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

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$ $w$ $s$ $v$
1 3 2 1 30
2 4 2 2 20
3 4 3 1 40

dp[j] を、総重量 $j$ での最大価値とする。
重さ上限は $w+s$ の最大値でよいので、今回は dp[0] から dp[4] までを用意する。
重量 $0$ の場合を $0$ で初期化しておく。

dp: {0, -INF, -INF, -INF, -INF}

$1$ 個目のブロック $(w,s,v)=(2,1,30)$ を見る。
このブロックの上に載る総重量 $j$ は、$0$ 以上 $1$ 以下でなければならない。

$j=1$ の場合、dp[1] が -INF なので更新されない。
$j=0$ の場合、dp[0] が $0$ なので、dp[2] を $0+30=30$ に更新する。

dp: {0, -INF, 30, -INF, -INF}

$2$ 個目のブロック $(w,s,v)=(2,2,20)$ を見る。
このブロックの上に載る総重量 $j$ は、$0$ 以上 $2$ 以下でなければならない。

$j=2$ の場合、dp[2] が $30$ なので、dp[4] を $30+20=50$ に更新する。
$j=1$ の場合、dp[1] が -INF なので更新されない。
$j=0$ の場合、dp[0] が $0$ なので、dp[2] は $\max(30,0+20)=30$ のまま。

dp: {0, -INF, 30, -INF, 50}

$3$ 個目のブロック $(w,s,v)=(3,1,40)$ を見る。
このブロックの上に載る総重量 $j$ は、$0$ 以上 $1$ 以下でなければならない。

$j=1$ の場合、dp[1] が -INF なので更新されない。
$j=0$ の場合、dp[0] が $0$ なので、dp[3] を $0+40=40$ に更新する。

dp: {0, -INF, 30, 40, 50}

テーブル内の最大値 $50$ が答え。

注意点

答えは int 型からはみ出る

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

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

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

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

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

別解

特になし。