Problem H ねこ鍋改造計画（仮） 秋葉 拓哉.

Presentation on theme: "Problem H ねこ鍋改造計画（仮） 秋葉 拓哉."— Presentation transcript:

1 Problem H ねこ鍋改造計画（仮） 秋葉 拓哉

2 猫 (性別， Cute, 重さ) Cute でソートしよう 性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19
15

3 デュアルねこ鍋 選んで鍋を作る 重さの和はそれぞれ W 以下 オス鍋 メス鍋 性別 Cute 重さ メス 1 10 オス 4 2 8 5 6
3 9 7 19 15 メス鍋 選んで鍋を作る 重さの和はそれぞれ W 以下

4 デュアルねこ鍋の評価 Cute の最大 - 最小 鍋同士の重量の差 この 2 つの大きい方 6 - 4 = 2 6 - 5 = 1
max(1, 2) = 2 Cute: 4, 6 重さの和: 5 Cute: 5 重さの和: 6 これを最小化したい！

5 つまり ① Cute が差 d 以下の範囲で ② 重さの差が d 以下になるような鍋 が作れる最小の d を求めたい 重さ 5 ① ②
性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19 15 ① ② 重さ 6 ① Cute が差 d 以下の範囲で ② 重さの差が d 以下になるような鍋 が作れる最小の d を求めたい

6 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 オス × ○ メス

7 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 × ○

8 「その重量を作るために使う Cute の最小値」
O(NW log W) の解法 (TLE?) DP の値を，Yes/No から： 「その重量を作るために使う Cute の最小値」 区間を縮めることもできるようになる ある値以下を × 扱い 重さ 1 2 3 4 5 6 7 8 9 10 11 12 オス × メス

9 O(NW log W) の解法 (TLE?) 答えについて二分探索できるようになる 一度の判定に O(NW)
性別 Cute 重さ メス 1 10 オス 4 2 8 5 6 3 9 7 19 15 範囲の大きさ d が決まっていれば しゃくとり法のように 範囲を動かせばよい

10 O(NW) の解法 (想定解法) 答え＝max 区間を広げる → ①が増え，②が減る 区間を縮める → ②が増え，①が減る
① Cute の最大 - 最小 ② 鍋同士の重量の差 答え＝max 区間を広げる → ①が増え，②が減る 区間を縮める → ②が増え，①が減る 小さい方をさらに小さくしても意味がない 二分探索は必要なく，しゃくとり法を一度で十分

11 結果 First Submit: 98 min (USAGI Code)
First Accept: 256 min (USAGI Code) Total Submit: 4 Total Accept: 1