人権なし

競プロで解いた問題や開発の進捗などの記録です

九州大学プログラミングコンテスト2018:D - Novelist

問題

beta.atcoder.jp

解法

王都から各都市に行ったならばすぐに王都に戻るのが最適であるので,M 個の依頼からすぐにまた王都に戻ってくる時刻を1つに定められる.なので,2種類の依頼を1つにまとめてしまうことで,最大スケジューリング問題にすることが出来る.あとは,時間の区間を終わりが早い順にソートし,終わりと始まりが重なってはいけないことに注意して貪欲に選んでいけばよい.問題文より,最後はどこにいてもよいので,王都から各都市に行けるならば最後に行く.O(N + LlogL).

解答

beta.atcoder.jp

upper_bound() を使う際,事前に配列を sort() していなくて 1 WA してしまった.

f:id:babcs2035:20181101180007p:plain