N の約数を全列挙するアルゴリズム
整数 N の約数とは「整数 N を割り切ることができる整数またはその集合」のことです。
単純なアルゴリズムでは約数の全列挙に \(O(N)\) だけかかりますが、約数の性質を活かすと \(O(\sqrt{N})\) で全列 ...
[AtCoder] ABC157 D – Friend Suggestions 解説（400点）
N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。
まだ友達関係ではないブロック関係ではない
友達関係を辿ってたどり着ける
制約\ ...
2つの自然数の最小公倍数(LCM)を求めるアルゴリズム
最小公倍数(LCM: least common multiple) とは、「0でない複数の自然数の公倍数のうち最小の自然数」のことを言います。
最小公倍数は、最大公約数を利用することで簡単に求めることができます。
2 ...繰り返し二乗法によるべき乗(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）とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。
以下のような特徴がありますが、抽象的なのでここではざっと眺 ...