7K12 blog

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

2020-06-17から1日間の記事一覧

AOJ ALDS1_11_C 幅優先探索

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4587473 幅優先探索はキューを使う キューはFIFO 幅優先探索の基本。注意点として、他の頂点から遠回りして更新済み頂点に辿り着いたとき再び更新しないように if (res[to] != -1) continue; が必要。…

ABC157 E - Simple String Queries

https://atcoder.jp/contests/abc157/submissions/13434967 BITで点加算と範囲取得が BITを複数本もつデータ構造に慣れる 文字列の長さがでクエリ数があることから、合計を求めるクエリ1個につきまたはで処理したいという気持ちになる。そこで、Binary Index…

ABC156 E - Roaming

https://atcoder.jp/contests/abc156/submissions/13470562 人の移動パターンは関係ないので意識してしまうと一生答えが出ない 移動すると空部屋が増える傾向にある→移動した人を部屋の外に集めて空部屋以外に再分配する重複組み合わせ どの部屋を空部屋にす…