7K12 blog

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

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

ABC128 C - Switches

https://atcoder.jp/contests/abc128/submissions/15677953 制約が10しかないのでbit全探索する ループの最後まで行けたらans++と書くと実装が楽。 任意の電球1個について「配線を辿ってスイッチの個数のmod2がpかどうか」はで判定できる。電球が10個しかな…

AOJ ALDS1_5_A Exhaustive Search

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4610462 bit全探索した通りの答えをメモ化 制約を見ると20しかないのでbit全探索できそうと予想する。全ての組み合わせを調べても最大通りしかないので、全探索しても処理できる。ただし、各質問毎に…

ABC160 D - Line++

https://atcoder.jp/contests/abc160/submissions/11321133 ダイクストラ法は単一始点から全ての終点までの最短経路を求める ダイクストラ法は 基本的にとにしか辺が存在せず、それとは別に追加される辺が1本しかない。そのため、辺の本数が頂点数と殆ど同じ…