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