7K12 blog

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

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

AOJ GRL_2_A Minimum Spanning Tree

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4213849 クラスカル法による最小全域木の計算量は 最小全域木は全ての頂点を通るグラフの最短距離となる。最小全域木のアルゴリズムにはプリム法とクラスカル法がある。実装方法は蟻本p100に載ってい…

ABC141 D - Powerful Discount Tickets

https://atcoder.jp/contests/abc141/submissions/15353189 priority_queueのtop、pop、pushを多用しリアルタイムに最大値を取得、更新する この類の問題は買う値段などを決め打ちして二分探索するような定跡もあるが、今回はokとなる値が不明となるため二分…

ABC142 D - Disjoint Set of Common Divisors

https://atcoder.jp/contests/abc142/submissions/15352890 https://atcoder.jp/contests/abc142/submissions/15351653 因数分解した因数の組み合わせが約数になる 素因数分解した因数の個数 ⇔ 約数のうち素数の個数 「互いに素でなければならない」という条…