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に繋げられなかったので悔しい。