D: DANGEROUS TOWER 原案・解説：保坂 問題概要 • 直方体の積み木が N 個ある • 積み木 i は，以下のいずれかとして使える • 奥行き 1 横 Ai 高さ Bi • 奥行き 1 横 Bi 高さ Ai • 横の長さが厳密に小さくなっていくように積む • 積み木を使う順番は自由 • 使わない積み木があってもよい • 高さを最大にしたい • N <= 1,000 注目点 • 積み木を好きな順番に使ってよいということは，横の長 さが異なるように積み木を選んでいけばそれらをすべて 使うことができる 解法 • 積み木 i は， • 横の長さ Ai で使うと Bi 点獲得 • 横の長さ Bi で使うと Ai 点獲得 • 制約：横の長さはすべて異なる • 割り当て問題！ 解法 • 最小費用流 -40 10 -40 -30 20 -20 30 -10 -10 40 × 容量 ∞ 解法 • • • • 計算量 入力に出てくる長さは 2N 個 グラフは頂点数 O(N)，辺数 O(N) O(N2 log N) • 必要はないが，コストが負の辺を消すことも可能 • 横の長さ Ai で使うと Ai 点失う • 横の長さ Bi で使うと Bi 点失う • 使わなければ Ai + Bi 点失う 結果 • • • • • 正解 / 提出： 4 / 25 提出チーム： 10 正解チーム： 4 最初の提出： stqn (00:27) 最初の正解： HITORIx2 (02:36) • 合宿参加チーム： team WAKABA (03:24)
© Copyright 2024 ExpyDoc
