https://atcoder.jp/contests/agc040/tasks/agc040_b
1から$10^9$までの番号がついた$10^9$人が参加する大会があり、この大会では2回のコンテストが行われる。
$N$個の問題があり、$i$番目の問題は番号が[$L_i, R_i$]の参加者に解かれる。これらの問題を2つのコンテストに振り分けて、それぞれのコンテストで全問正解できる人の人数の和(楽しさと呼ぶ)を最大化せよ。
すべての問題について正解者は区間になっており、同じコンテストに出題される問題の区間の共通部分の長さを最大化する。前提として、(すでに1つ以上の問題がある)コンテストに問題を追加することで楽しさが減ることはあっても増えることはない。
以下、すべての問題のなかで最も$L$が大きい問題を$p$、すべての問題の中で最も$R$が小さい問題を$q$と呼ぶ。$p$と$q$を同じコンテストで出題するかどうかで場合分けをする。
$p$と$q$を同じコンテストに出題する場合($p=q$である場合も含む)にはそのコンテストの楽しさは$\max(0, R_q-L_p)$となり、ほかにどれだけ問題を加えようと変わることはない。よって、もう一つのコンテストの楽しさを最大化するためには$p, q$以外で最も区間の長い問題だけのコンテストを作るべきである。
$p$と$q$を別のコンテストに出題する場合を考える。$q$が出題されるコンテストでは、$L$が$L_q$より小さい問題はすべて出題してよい($R_q$より小さい$R$をもつ問題は存在しないので、$L_i\lt L_q$であるような問題$i$はすべて問題$q$を区間として含んでいるため)。こうすると、まだ出題するコンテストが決まっていない問題は$L_q\lt L\lt L_p$であるような$L$をもつ問題だけとなる。ここで、そのような問題$r$を$q$と同じコンテストに出題することに決めたとすると、$L_i\lt L_r$であるような問題$i$は区間として[$L_r, R_q$]を含むのですべて$q$と同じコンテストに出題してよいことになる。
以上のことから、すべての問題を$(L_i, -R_i)$が昇順となるようにソートしたあと、各問題1問だけのコンテストを作った場合と、ある問題より$L_i$が小さいかどうかでコンテストを分けた場合をすべて考えればその中に必ず最適な分け方が存在していることがいえる。
区間を2グループに分けて共通部分を最大化するという典型っぽい問題だったが解けなかった。ARC073Eに似ていることは問題を見た瞬間に気付いたが、ACに繋げられなかったので悔しい。