N – 木 解説（AtCoder Typical DP Contest）

問題へのリンク 問題概要 木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。 制約 \(2 \leq N \leq 1000 \) 考え方 前提：木DPの考え方 俗に言う、木DP を用います。木DPでは以下のようなDPを基本に考えます。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 それぞれの部分木から

ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム

任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。 ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。 負の辺が含まれていても動作する負の閉路がある場合は検出できる という利点があります。 アルゴリズム グラフ G = (V, E) に対するワーシャル・フロイド法は以下のようになります。 ワーシャル・フロイド法：（「dist[ i ][ j

トライ木(Trie木) の解説と実装【接頭辞(prefix) を利用したデータ構造】

Trie木は、効率的な検索(retrieval)のために使われるデータ構造です。文字列などの先頭部分(接頭辞: prefix)の共通部分を共有して保存することで、\(O(M)\) での検索を可能にします。（文字列の長さを\(M\) としました。） 以下は、「fire・firearm・firework・fireman・algo」をトライ木に保存した時の状態を表しています。 トライ木の仕組み 基本は木

平方数の判定をするアルゴリズム

Nが自然数の2乗で表現できるとき、平方数と言います。 平方数の例4 (= 2×2)9 (= 3×3)16 (= 4×4)25 (= 5×5) アルゴリズム 全探索でのアルゴリズム： \(\sqrt{N}\) 以下の自然数 \(k\) に対して以下を確かめる\(k^2 = N\) となる \(k\) が存在すれば N は平方数 ※ 平方数なら、\(k^2 = N\) となる \(\sqrt{N}\)

Nの約数の個数を求めるアルゴリズム

アルゴリズム Nの約数の個数： N を素因数分解するそれぞれの指数に1を足す「2.」で得られたものを全てかけ合わせる ※ 素因数分解のアルゴリズムに関してはこちらを参照 ※ 例と...

B – 123 Triangle 解説 (AtCoder Grand Contest 043)

問題へのリンク 問題概要 1,2,3 で構成された整数列 \(a_1 a_2 a_3 \cdots a_N\) が与えられ、\(x_{i,j}\) を以下のように再帰的に定義する...

プリム法による最小全域木を求めるアルゴリズム

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木（Spanning Tree) と言います。 \(T\)...

クラスカル法による最小全域木を求めるアルゴリズム

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木（Spanning Tree) と言います。 \(T\)...

パスカルの三角形による二項係数(nCk)の計算

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}...

パスカルの三角形による二項係数(nCk)の計算

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}...

二項係数(nCk)の偶奇判定のアルゴリズム

Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。 アルゴリズム Lucasの定理をそのまま利用したアルゴリズム： \...

二項係数(nCk)を素数(p)で割った余りの計算（Lucas の定理）

Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さ...

配列の全ての要素(N個)の最大公約数(GCD)を求めるアルゴリズム

配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。 例： Input: A = ...

拡張ユークリッドの互除法

最大公約数を求める高速なアルゴリズムとしてユークリッドの互除法が知られています。このユークリッドの互除法を拡張することにより、 $$ ax+by=gcd(a,b)$$ の形をした...

配列の全ての要素の最小公倍数(LCM)を求めるアルゴリズム

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数...

グラフの2頂点が同じ連結成分に属するか判定するアルゴリズム

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。 グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属...

グラフの連結成分の個数を求めるアルゴリズム

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。 連結成分は3つ アルゴリズム グラフ \(G=(V,E)\) の連結成分の個数...

区間の和を求めるアルゴリズム（区間の更新なし）

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 [L, R) の和を求めるアルゴリズムについてです。 区...

二次元での区間和を求めるアルゴリズム（区間の更新なし）

大きさが \(H × W\) の二次元配列 \(a\) 上において、 [h1,h2)×[w1,w2) の範囲の区間和を求めるアルゴリズムについてです。 input: a = {{...

フローネットワークの最小カットの容量を求めるアルゴリズム

アルゴリズム フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \( f^* \) を求める\( f^* \) が最小カットの容量 ※ カット \(...

二部グラフの最大マッチングを求めるアルゴリズム

アルゴリズム 二部グラフ \(G=(L \cup R, E)\) に対応する以下のようなフローネットワーク \(G'\) を作る\(G\) にソース \(s\) とシンク \(t...

Ford-Fullkerson法による最大フローの求め方

フローの基本となる用語はこちら アルゴリズム フロー \(f\) を 0 としてはじめるソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \(...

フローネットワークの基礎と用語の定義

フローネットワークとフロー フローネットワーク 関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローネットワーク \(f\) は、以下の特...

ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）

最近共通祖先（LCA）とは 木において、ある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。 頂点 u と v...

E – Roadwork 解説（AtCoder Beginner Contest 128）

問題へのリンク 問題概要  N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 \(i\) 番目の道路工事は時刻 \(S_i−0.5\) から時刻 \(T_i−...

半分全列挙による全探索の高速化

N 個の要素の組み合わせを計算する際、N/2 ずつの2グループに分けてそれぞれを全列挙し、組み合わせ方を高速に求めるという工夫を「半分全列挙」と言います。 選択した数列の合計値を...

木の直径を求めるアルゴリズム

木（連結で閉路を持たない(無向)グラフ）について、直径の概念の説明とそのアルゴリズムの解説です。 木の直径とは 木に存在する2つノード間の最大距離を木の直径と言います。 例えば、...

組み合わせゲーム理論の基礎とGrundy数でのゲーム必勝法！

競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。 前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題につい...

N – Slimes 解説 (Educational DP Contest / DP まとめコンテスト)

問題へのリンク 問題概要 N 個の数列 \({a_1, a_2, a_3, \cdots, a_N\}\) があり、以下の操作を数列の要素数が 1 になるまで繰り返す。 隣り合う...

区間DP の考え方と使える状況まとめ

競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。 区間DPとは 区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです...

L – Deque 解説 (Educational DP Contest / DP まとめコンテスト)

問題へのリンク 問題概要 数列 \(a = a_1, a_2, \ldots, a_N \) がある。二人で以下の操作を交互に行う。 a の先頭要素または末尾要素を取り...

K – Stones 解説 (Educational DP Contest / DP まとめコンテスト)

問題へのリンク 問題概要 二人で以下のゲームを行う。先手と後手のどちらが勝つか？ 以下の操作を交互に行うA = \( a_1, a_2, \ldots, a_N\) の元 x を...

A – コンテスト 解説 (Typical DP Contest)

問題へのリンク 問題概要 N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。合計得点は何通り考えられるか？ 制約...

E – Divisible Substring 解説（AtCoder Beginner Contest 158）

問題概要 長さ N の数 S が与えられる。素数 P で割り切れるような区間の選び方は何通りあるか？ 制約 \(1 \leq N \leq 2 \times 10^5\)\(2 ...

ダイクストラ法による単一始点最短経路を求めるアルゴリズム

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。 ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点と...

ベルマンフォード法による単一始点最短経路

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。 ベルマンフォード法は、単一始点最短経路問題を解く時に利用されます...

累積和で高速化！区間和を求めるクエリ

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられて、区間 [L, R) の和を求めたい時を考えてみます。 区間 [L,...

Binary Indexed Tree (BIT) の仕組みとその応用

Binary Indexed Tree は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)...

約数を全列挙するアルゴリズム

整数 N の約数とは「整数 N を割り切ることができる整数またはその集合」のことです。 単純なアルゴリズムでは約数の全列挙に \(O(N)\) だけかかりますが、約数の性質を活か...

[AtCoder] ABC157 D – Friend Suggestions 解説（400点）

問題概要 N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。 まだ友達関係ではないブロック関係ではない友達関...

グラフの連結成分に関するアルゴリズム

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。 連結成分がいくつあるのかを求めたり、同じ連結成分に含まれるのかどうかを判定する...

[AtCoder]ABC157 E – Simple String Queries (500点)

問題概要 長さ N の英小文字からなる文字列 S を与えられ、以下の二種類のクエリ合計 Q 個を処理する。 S の \(i_q\) 番目を \(c_q\) に変更するS の \(...

[AtCoder]ABC157 E – Simple String Queries (500点)

素因数分解のアルゴリズム

素因数分解とは「ある自然数を素数の積の形に分解すること」です。 1つの自然数 n を \(O(\sqrt{n})\) で素因数分解する方法と、複数の自然数を前処理 \(O(n l...

最小公倍数を求めるアルゴリズム

最小公倍数(LCM: least common multiple) とは、「0でない複数の自然数の公倍数のうち最小の自然数」のことを言います。 最小公倍数は、最大公約数を利用する...