https://atcoder.jp/contests/abc017/tasks/abc017_3
- 考えたこと
- スコアを最大化したいが、区間にフラグが立って、すべてのフラグが立つとNG
- Nが8で部分点。この場合2^8通りを探索することができる
- N,Mが5000で別の部分点、10万で満点
- もしも区間がカバーしない点があれば自明に「全部選択する」が最良
- 区間がすべてをカバーするケースを考えると、どこか1箇所カバーされない点ができるように穴を開ければ良い
- 穴を1箇所選べば、それに重なってる区間はすべて外すことが必要だし、それで十分、この時スコアは全部選択した時と比べて「重なってる区間」のスコアの和だけ減る
- よってスコアを区間に足し合わせて、最小値を見つける問題
- カバーしてない点がある場合は最小値が0になるので場合分けは必要ない
- いもす法で線形オーダー
- 公式解説OK