7K12 blog

猫でも分かるアルゴリズム解説

ABC128 E - Roadwork

f:id:tkr987:20200506194528p:plain

https://atcoder.jp/contests/abc128/submissions/12875865

  • std::setのinsertと二分探索、removeが便利。

工事座標Xに到達するのにX秒かかることから逆算する。工事範囲[S-X, T-X)で二分探索してスタート時間Dの人が工事に引っかかる範囲を対応させる。ただし、引っかかる工事が確定した人を積極的に排除していかないと最悪 O(N^2 \log N)になってしまうため、人のスタート時間Dをsetに格納して削除を O(\log N)で出来るようにしておく。 スタートに近い工事座標で止まるべき人がスタートから離れた工事座標になってしまうと困るので、工事座標昇順にソートして上記処理をする必要がある。

f:id:tkr987:20200507052234p:plain

なお、全ての人が1秒で距離1しか歩かないので、予めスタート地点をマイナス方向に調整する方法もあるが、今回はそのまま実装したほうが簡潔になると思われる。