ABC103 Islands war

所見

想定された思考パスは前から順番に見ていって区間が閉じる直前にその区間が解決されていなければ処理すればいいよね->これをNlogNくらいでやりたい->開いてる区間を覚えておくのだとNMでつらそう->ソートしておけば貪欲に右端の橋を破壊すればよい
くらいだろうか。
「左から見ていけば」貪欲に右端を消していけばよい、というのに気づくのが難しい気がする。使う要素は難しくないのに気づきゲーなのでつらい。

問題概要

N個の整数とM個の区間が与えられる。全ての区間内に少なくとも一つの物体を置かなければならないとき、物体はいくつ必要か。(問題を言い換えています)

取った方針

区間の重なりを考えるので累積和を用いることが思いつく。重なっている数が多い順に貪欲に置いていく方法を考えるが、これが不可能なことはすぐにわかる。
必要な個数をnum個に固定したとき、O(M)もしくはO(N)でできるかできないかを判別できれば二分探索ができると思うが、判別できないのでダメ。
前から順番に見ていって区間が閉じる直前にその区間が解決されていなければ置けばいいということに気づくもO(NM)解法しか思いつかず終了。

正しい方針(解説の方針)

前から順番に見ていって区間が閉じる直前にその区間が解決されていなければ置く、という方針が正しかった。
これは区間の右端で区間をソートしておき、直前に置いた場所によってその区間が解決されていなければ区間の右端に置く、ということで実現できる。
このようにすると、区間の右端が小さい順に処理されていく。この場合、その時見ている区間の右端より左に未解決の区間の右端が残っていることはない(右端に置いたために解決できなくなる区間が存在しない)ので、右端に置いても不利になることはない。
また、右端の値が小さい順に処理される都合上、一番右に置いた物体のみを覚えておけばよい。なぜなら、右端の値が小さい順に処理されるので、見ている区間の右端に置いた物体を含まず、そうでない物体を含む未解決の区間はありえないからである。
以上より、ソートが一番遅いのでO(MlogM)。

得られた知見

・与えられた情報の順番を入れ替えても問題の意味が変わらない->ソートを視野に入れる
・貪欲法

解くのに必要な要素

・左から順番に見ていって区間が閉じる直前にその区間が解決されていなければ置くという気づき
・ソートしても良いならソートしてみる
・直前の処理だけ覚えておけばよいという気づき(区間をソートすることで得られる性質)

周辺調査によって得られた知見

なし