QUPC2018-D:Novelist
きれいに解けるので好き。
問題
考察過程
王都から都市へ移動する依頼をタイプM，都市から王都へ移動する依頼をタイプLとする。
最初は各依頼を頂点として，ある依頼を終えた後，実行可能な依頼について有向辺を張って，最長パスを調べるということを考えていたのだが，これでは辺が本あるためTLEする。考え直し。
よく考える。タイプMの依頼を終えた後，Treeone君はある都市にいる。次には(可能なものが存在すれば)タイプLの依頼を選ぶことになるが，都市
から出発する依頼のうち，現在時刻より後で，最も出発日が早いものを選ぶのが最適になる。できるだけ早く王都に戻った方が，多くの依頼を達成できるかもしれないからである。つまり，あるタイプMの依頼をやると決めた後，タイプLの依頼を終えて王都に戻ってくる日が一意に定まる。
それならば，以下のようにすればよい。
- タイプMの各依頼に対して，その依頼の開始日と，王都に帰ってくる日を両端とした区間を作る(ただし，王都に帰ってこれない場合は作らないでおく)。
- これらの区間について，区間スケジューリング問題を解く。その解
を答えに加算する。
- 区間スケジューリング問題の最適解の終了日を記録しておく。このとき王都にいるので，タイプMの依頼のうち，まだ達成できるものがあれば答えに1を加算する。もう王都には戻ってこれないので，これでTreeone君の仕事は終わりである。
区間スケジューリング問題を知らない方は調べてください(すいません)。
提出
https://beta.atcoder.jp/contests/qupc2018/submissions/3438077
- タイプLの依頼は，出発する都市ごとにvectorで管理した。
- あるタイプMの依頼に対する最適なタイプLの依頼を探すのに二部探索をしている。
- もうちょっときれいに書けそう。
今思えば，「できるだけ早く王都に戻った方が，多くの依頼を達成できるかもしれない」という考え方はまさに区間スケジューリング問題を示唆するものであった。良問だと思う。
