Problem H ねこ鍋改造計画（仮） 秋葉 拓哉 猫 • (性別， Cute, 重さ) • Cute でソートしよう 性別 Cute 重さ メス 1 10 オス 4 2 メス 4 8 メス 5 6 オス 6 3 オス 9 7 メス 19 15 デュアルねこ鍋 性別 Cute 重さ メス 1 10 オス 4 2 メス 4 8 メス 5 6 オス 6 3 オス 9 7 メス 19 15 • 選んで鍋を作る • 重さの和はそれぞれ W 以下 オス鍋 メス鍋 デュアルねこ鍋の評価 1. Cute の最大 - 最小 – 6-4=2 2. 鍋同士の重量の差 – 6-5=1 Cute: 4, 6 重さの和: 5 • この 2 つの大きい方 – max(1, 2) = 2 Cute: 5 重さの和: 6 これを最小化したい！ つまり ① 性別 Cute 重さ メス 1 10 オス 4 2 メス 4 8 メス 5 6 オス 6 3 オス 9 7 メス 19 15 ① Cute が差 d 以下の範囲で ② 重さの差が d 以下になるような鍋 が作れる最小の d を求めたい 重さ 5 ② 重さ 6 O(N3W) の解法 (TLE) • 全ての Cute の範囲を試す – O(N2) 通り 範 囲 • ナップサックの DP – O(NW) 性別 Cute 重さ メス 1 10 オス 4 2 メス 4 8 メス 5 6 オス 6 3 オス 9 7 メス 19 15 重さ 1 2 3 4 5 6 7 8 9 10 11 12 オス × ○ ○ × ○ × × × × × × × メス × × × × × ○ × ○ × × × × O(N2W) の解法 (TLE) • 範囲を伸ばした時，ナップサック DP は直前の 結果を再利用できる 性別 Cute 重さ メス 1 10 オス 4 2 メス 4 8 メス 5 6 オス 6 3 オス 9 7 メス 19 15 1 2 3 4 5 6 7 8 9 10 11 12 × ○ × × × × × × × × × × × × × × × ○ × ○ × × × × 1 2 3 4 5 6 7 8 9 10 11 12 × ○ ○ × ○ × × × × × × × × × × × × ○ × ○ × × × × O(NW log W) の解法 (TLE?) • DP の値を，Yes/No から： 「その重量を作るために使う Cute の最小値」 • 区間を縮めることもできるようになる – ある値以下を × 扱い 重さ 1 2 3 4 5 6 7 8 9 10 11 12 オス × 4 6 × 4 × × × × × × × メス × × × × × 5 × 4 × × × × O(NW log W) の解法 (TLE?) • 答えについて二分探索できるようになる – 一度の判定に O(NW) 性別 Cute 重さ メス 1 10 オス 4 2 メス 4 8 メス 5 6 オス 6 3 オス 9 7 メス 19 15 範囲の大きさ d が決まっていれば しゃくとり法のように 範囲を動かせばよい O(NW) の解法 (想定解法) 答え＝max ① Cute の最大 - 最小 ② 鍋同士の重量の差 • 区間を広げる → ①が増え，②が減る • 区間を縮める → ②が増え，①が減る 小さい方をさらに小さくしても意味がない 二分探索は必要なく，しゃくとり法を一度で十分 結果 • First Submit: 98 min (USAGI Code) • First Accept: 256 min (USAGI Code) • Total Submit: 4 • Total Accept: 1
© Copyright 2024 ExpyDoc
