競技プログラミング用 知識集積所
X - Tower
最終更新：
sport_programming
-
view
問題
必要知識
ABCのB以下レベルの内容は省略
考え方
まず、使うブロックを決めたときに、それで塔を作れるかを高速に判定したい。
そこで、重さw1で丈夫さs1のブロックと、重さw2で丈夫さs2のブロックのどちらを上に使うべきか考えてみる。
この上には重さw0のものが乗っていて、下に丈夫さs3のものがあるとする。
そこで、重さw1で丈夫さs1のブロックと、重さw2で丈夫さs2のブロックのどちらを上に使うべきか考えてみる。
この上には重さw0のものが乗っていて、下に丈夫さs3のものがあるとする。
w1,s1のを上に使う場合、
w0 < s1 w0+w1 < s2 w0+w1+w2 < s3
を満たす必要がある。
逆にw2,s2のを上に使う場合、
逆にw2,s2のを上に使う場合、
w0 < s2 w0+w2 < s1 w0+w1+w2 < s3
を満たす必要がある。
これらの一方だけが満たされる状況がどんなときに発生しうるかを考える。
これらの一方だけが満たされる状況がどんなときに発生しうるかを考える。
第3式は共通なので、どちらを上に使うのがいいかに影響しない。
また、第1式が満たされない場合、相手側の第2式が成り立たなくなるので、これも影響しない。
すなわち、第2式が片方だけ満たされる状況が、一方だけが満たされる状況となりうる。
また、第1式が満たされない場合、相手側の第2式が成り立たなくなるので、これも影響しない。
すなわち、第2式が片方だけ満たされる状況が、一方だけが満たされる状況となりうる。
式を
w0 < s2-w1 w0 < s1-w2
と変形すると、s2-w1<s1-w2なら2の方を上に、s2-w1>s1-w2なら1の方を上にするのがよく、s2-w1==s1-w2ならどちらでもよいことがわかる。
つまり、各ブロックについてs+wの値を求め、それが小さいものほど優先的に上に置く貪欲法（未作成）が成立する。
つまり、各ブロックについてs+wの値を求め、それが小さいものほど優先的に上に置く貪欲法（未作成）が成立する。
つまり、最初から全部s+wを小さい順に並べた上で、追加分は必ず一番下に置くというルールのもとで条件付きナップサック問題を解けばよい。
解答例
注意点
重さ上限は、s+wの最大値まででよい
全ブロックのwの合計を上限に取ると、DPテーブルが大きくなりすぎる。
塔の重さの合計は最下段のs+wを超えないことに注目し、テーブルの大きさを制限すること。
塔の重さの合計は最下段のs+wを超えないことに注目し、テーブルの大きさを制限すること。
「重さWぴったり」でDPテーブルをつくる。
通常のナップサックは「重さW以下」でDPテーブルを作る方が楽だが、今回は制約上それが難しい。
「重さWぴったり」で表を作り、最後に最大値探索をする。
「重さWぴったり」で表を作り、最後に最大値探索をする。
