初解説記事です。
もう3年前の問題ですが、自分のやり方がeditorialと違う気がしたので書こうかな〜となりました。
厳密な証明とか記法はむずかしいのでごめんなさい。
問題概要
雑に考えたこと
今ある椅子と人との最大マッチングを考えてNから引けば良い。
二部グラフの最大マッチングかな〜→無理
この問題だと各人の座れる区間が2つに分かれているが、1つなら適当にソートしてpriority_queueを使うと解けることを思い出すとそんな感じなのかな〜となる。
解法
以下、座標xにある椅子を椅子xと呼ぶ。
i番目の人がL_i以下の椅子に座ることを左から取る、R_i以上の椅子に座ることを右から取ると表現することとする。
椅子a,b(a<b)について、aが右から取られて、bが左から取られたケースが最適解の1つだとすると、aを左から、bを右から取るに変更しても良いことがわかる。
よって、あるpを境にして、x<=pとなる椅子xは左からor取られない、p<yとなる椅子yは右からor取られないと考えて良い。
椅子a,b,c(a<b<c)について、a,cが左から取られて、bが取られてない場合、a,bを左から取る、cを取られてないに変更しても良いことがわかる。
右も同様に考えると、椅子1~xは左から、椅子x+1~y-1は取られない、椅子y~Mは右から取られるが達成できるもののうち、x+(M-y+1)の最大値を求めれば良いことがわかる。
xを固定すると、椅子xから椅子1まで順に見て、その椅子を左から取ることのできる人のうち、R_iが最大の人を選ぶということを繰り返し、その後に右から取るのは残った人でR_iについて貪欲で良い。
しかし、これだと間に合わない。
ここで、xをx+1に変化させた時のことを考える。このとき、右から取れる個数は高々1しか減らないことがわかる。
よって、x+(M-y+1)は、椅子1~xまでを左から取れるうちは、広義単調増加となるため、xが最大の場合についてのみ考えて、そのときのみ右から取るパートのシミュレーションをすれば良いことがわかる。
提出
〇〇としても解は悪化しないを大量に使うので面白いと思いました。
こんな雑でもそこそこだるかったので、多くの解説記事を書いてる人はすごいということを実感できました。
