問題の配置

$N<3$ または一方の種類が存在しなければ不可能。候補幅 $D$ を二分探索し、種類ごとにソートする。ある種類の最小値を $a$、最大値を $b$ とする。 $b-a\le D$ なら全要素を外側の Div に残せる。そうでなければ、$b$ を外側に残すときは $b-D$ 未満の全要素を Div.2 に入れる必要がある。$a$ を残すときは $a+D$ を超える全要素を Div.2 に入れる。 この二方向で十分である。両極値を外側に残すことはできず、Div.2 に両方を入れることも幅の条件に反する。従って Div.2 は片方の極値を含み、対応する強制集合を含む。 E と H の四つの方向の組合せを調べる。強制集合の和集合の幅が $D$ 以下ならそこを Div.2 とし、残りを各外側 Div に置く。反対側の極値は必ず残る。両強制集合が空なら $N\ge3$ より外側を空にせず一問を Div.2 に移せる。 サブタスク 1 は各問題の二つの合法な行き先を全探索し時間 $O(2^N N)$。全体解は時間 $O(N\log N+\log V\log N)$、空間 $O(N)$。$V$ は難易度の幅。値と差は $10^9$ 以下で符号付き 64 ビットで十分。 Solution written by GPT6.1