素因数分解のアルゴリズム
素因数分解とは「ある自然数を素数の積の形に分解すること」です。
\(12 = 2^2 × 3\)\(1024 = 2^{10}\)
1つの自然数 n を \(O(\sqrt{n})\) で素因数分解する方法と ...
2つの自然数の最小公倍数(LCM)を求めるアルゴリズム
最小公倍数(LCM: least common multiple) とは、「0でない複数の自然数の公倍数のうち最小の自然数」のことを言います。
最小公倍数は、最大公約数を利用することで簡単に求めることができます。
2 ...素数かどうかを判定するアルゴリズム
素数とは 「1 より大きい自然数で、正の約数が 1 と自分自身のみであるような数」です。
ある数 \(n\) が素数かどうかを判定するためには、単純に考えると \(O(n)\) の計算量になりますが、後述する通り実は \( ...
トポロジカルソートのアルゴリズム（閉路のない有向グラフDAGのソート）
トポロジカルソートとは、閉路の無い有向グラフ DAG について行うソートです。
左図のDAGを右図のように頂点を一列に並べて、全ての辺の向きが左から右になるようにすることを言います。
閉路のないDAG繰り返し二乗法によるべき乗(pow(x,n))の計算のアルゴリズム
多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数のアルゴリズムです。
Input : pow(2,4) (x=2, n=4)
Output : 16
べき乗は非常に大きな数値に ...
ビットDP(bit DP)の考え方 ~集合に対する動的計画法~
競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。
ビットDPとはビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 ...
グラフにおける橋(bridge)を検出するアルゴリズム
無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います。
※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があることを言います。（くわしくはグラフ ...
グラフにおける関節点(Articulation Points)を検出するアルゴリズム
連結グラフにおける関節点(切断点)とは、「グラフから取り除くと、グラフが非連結になってしまうような頂点」のことを言います。
※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があること ...
桁DP(Digit DP) を考え方から問題例まで徹底解説！
競技プログラミングで良く用いられる動的計画法の1つ「桁DP」について解説します。
桁DPとは桁ごとに分けて考える動的計画法です。
「1からNまでの整数について、条件を満たす数はいくつあるか？」「1からNまでの ...
動的計画法（Dynamic Programming）入門
動的計画法（Dynamic Programming）とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。
以下のような特徴がありますが、抽象的なのでここではざっと眺 ...