AGC040 - B - Two Contests
概要
N個の区間が与えられる。これらの区間をグループ１、グループ２に分ける。それぞれのグループ内の区間の積集合の区間を計算し、その長さの和を最大化せよ。
制約： 2 <= N <= 10^5, 1 <= L_i <= R_i <= 10^9
ACするまで
1. 一杯実験をすると、どうやら答えになる区間の境界に必ず使われる要素が存在してるとわかる。
2. ２つのグループから２つの積集合の区間が存在するけど、合計４つの境界のうち、２つは固定で、２つはなんでもよい。
3. 固定する２つの場所を考えて、場合分けして考察する。->AC!
考察
グループ①は、右端が固定されてるので、(割り当てられた区間の)左端の(最大)値が、区間の積集合の長さと直結する。
基本的に、区間をグループに追加するというのは、積集合の性質から、追加すればするほど制約が厳しくなる方向性に動くので、、できれば無用にグループに追加しないほうが良い。(確実に悪化しない場合以外)
ところで、グループ①の左端をlとすると、左端がlより左にある区間は、いくらグループに追加しても、確実に積集合の範囲は縮まらない。グループ②に追加しても悪化しないものもあるが、リスクなしで確実に悪化しないグループ①に追加しよう。
つまり、あるlまでの集合たちは①、それいがいは②に追加をする、ということになり、そのうちのどこかで最適解が存在するので、全探索をすればよい。
lと同じ始点を持つグループについては、終点が大きい順にソートしよう。グループ②に割り当てるときに、よりrが大きいものの方が②の制約を緩めないからである。
一言
実装になぜか詰まっていた。AGC精進の一環。
