重みが最小となる閉路を求めるアルゴリズム
最小コストの閉路:
任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除くv から u への最短経路 d を求める(ダイクストラ/BFS など)
d+cost(u, ...
木DPと全方位木DPを基礎から抽象化まで解説【競技プログラミング】
競技プログラミングでよく出題される木DPについての説明と、木DPで解ける一部の問題を同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。
木DP基本的な考え方とイメージ木DP とは、根を一つ固 ...
ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム
任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。
ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。
負の辺が含まれていても動作する負の閉路がある場 ...
平方数の判定をするアルゴリズム
Nが自然数の2乗で表現できるとき、平方数と言います。
平方数の例4 (= 2×2)9 (= 3×3)
16 (= 4×4)
25 (= 5×5)
アルゴリズム
以下の方法以外にも色々な求め方 ...
Nの約数の個数を求めるアルゴリズム
素因数分解を用いることで、約数の個数を簡単に求めることができます。
アルゴリズムNの約数の個数:
N を素因数分解するそれぞれの指数に1を足す
「2.」で得られたものを全てかけ合わせる
プリム法による最小全域木を求めるアルゴリズム
無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。
\(T\) は木\(T\) では\(V\) の任意の ...
クラスカル法による最小全域木を求めるアルゴリズム
無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。
\(T\) は木\(T\) では\(V\) の任意の ...
パスカルの三角形による二項係数(nCk)の計算
以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)
二項係数(nCk)の偶奇判定のアルゴリズム
Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。
アルゴリズムLucasの定理をそのまま利用したアルゴリズム:
\({}_{n_i}\mathrm ...二項係数(nCk)を素数(p)で割った余りの計算(Lucas の定理)
Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さい場合は十分高速です。
Lucas の定理任 ...