フローネットワークの基礎と用語の定義
関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローは、以下の特徴を持つ重み付き有向グラフ（フローネットワーク） \(G=(V,E)\) 上で定義されます。
ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム
最近木においてある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。
頂点 u と v の最近共通祖先(LCA: Lowest Common Ancesto ...
半分全列挙による全探索の高速化
N 個の要素の組み合わせを計算する際、N/2 ずつの2グループに分けてそれぞれを全列挙し、組み合わせ方を高速に求めるという工夫を「半分全列挙」と言います。
選択した数列の合計値を半分全列挙で探索する場合（\(2^4\)ずつに分け ...木の直径を求めるアルゴリズム
木に存在する2つノード間の最大距離を木の直径と言います。
重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。
重み無しの木の例：
以下は直径が5となる木の例で
組み合わせゲーム理論の基礎とGrundy数での勝敗判定アルゴリズム
競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。
前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題については後半にあります。
組み合わせゲーム ...区間DP の考え方と使える状況まとめ
競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。
区間DPとは区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。
基本的には、以下のような DP ...
ダイクストラ法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては
計算量が \(O(|E| \l ...ベルマンフォード法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、
負の辺が含まれているような場合でも適用 ...競プロでよく出る区間和問題の解き方まとめ
区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。
一次元の区間和累積和を用いることで、
前処理：\(O(N)\)クエリ：\(O(1)\)
で処理がで ...
N の約数を全列挙するアルゴリズム
整数 N の約数とは「整数 N を割り切ることができる整数またはその集合」のことです。
単純なアルゴリズムでは約数の全列挙に \(O(N)\) だけかかりますが、約数の性質を活かすと \(O(\sqrt{N})\) で全列 ...