AGC040 B. Two Contests
問題
1から10^9まで番号がふられた10^9人が参加する大会があり、この大会では2回コンテストが行われる。
コンテストでは1からNまで番号がついたN問の問題が準備されており、問題iが出題された場合は、L_iからR_iまでの番号の人が正解し、それ以外の人は不正解することがわかっている。
コンテストは1問以上が出題され、問題はN問すべて2回のコンテストのいずれかで出題されなければいけない。
各コンテストで全問正解した人の数の和を最大化したいとき、その最大値を求めよ。
制約
- 2 <= N <= 10^5
- 1 <= L_i <= R_i <= 10^9
解法
まず、コンテストに1つの問題がアサインされていたとき、別の問題がアサインされると、元の問題の正解人数以下にしかなりえない。
したがって、まず、「どれか1つの問題」と「それ以外」でコンテストを開く場合を考えてみる。
一番R_iが左側にくるもの(同じ場合はL_iが一番左に来るもの)をlhs、一番L_iが右側に来るもの(同じ場合はR_iが一番右に来るもの)をrhsとする。(lhsとrhsは別の問題になるようにしておく)
すると、lhsかrhsを1問として選んだ場合は、それ以外のものからすぐに求められる。
lhsとrhs以外の問題の場合は、lhsとrhsが必ず含まれるので、lhsとrhsの共通部分が答えになる。(lhsとrhsはそのような選び方をしているので)
ここで、コンテストにrhsをアサインして、他の問題もいくつかアサインすることを考える。
lhsとrhsを除いた問題集合に対して、rhsと共通部分が多い順に問題をソートすると、rhsを含むコンテストの全問正解人数がソートしたものの順番に決めていける。
rhs側に入れなかった問題はlhsを含むコンテスト側に入るが、こちらも簡単にもとめておける。
(rhs側で共通部分の大きさが同じ問題のときは、lhs側に共通部分が大きくなるよう、lhs側の共通部分の多い順にセカンダリソートしておく)
最終的に、「どれか1つ選ぶ＆それ以外」のパターンと、「lhsとrhsをそれぞれコンテストにわけ、それぞれにいくつか問題をアサイン」のパターンを求めて、大きい方を返せば良い。
