7K12 blog

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

2020-05-07から1日間の記事一覧

EDPC Q - Flowers

https://atcoder.jp/contests/dp/submissions/12909348 in-place DPというやつらしい。 メイン条件 + index条件 → セグメントツリーにバラバラに入れる + RMQ (Range Max Query) 逆の逆の操作は同値「背が高い∧indexが減少」を抜く⇔「背が低い∧indexが増加」…

ABC128 E - Roadwork

https://atcoder.jp/contests/abc128/submissions/12875865 std::setのinsertと二分探索、removeが便利。 工事座標Xに到達するのにX秒かかることから逆算する。工事範囲[S-X, T-X)で二分探索してスタート時間Dの人が工事に引っかかる範囲を対応させる。ただ…