木の直径とは ある頂点0からdfs(bfs)によって一番遠い点を求める。その点の一つをkとするとその点からもう一度dfs(bfs)によって一番遠い点を求める。その点の一つをlとすると、k, lが実際の直径となっている。 実装

エラトステネスの篩とは ある整数nが与えられた時、このn以下の素数を高速に列挙する方法である。計算量としてはO(n log log n)である。素数判定の方法をn回繰り返すとo(n √n)となる。これに対してエラトステネスはすごい速い。 エラトステネスの篩によって…

素因数分解とは nを素因酢分解するアルゴリズムは、1 ~ √nに対してaとするとnをaで割れるときにaで割れるだけ割れば良い。この時aが素数でなければaを分解せねばならないが、aは必ず素数である。 最後に残った数は素因数となっているので追加する。ここで1に…

約数列挙とは nの約数を考える。これは、素数判定と同様に1 ~ √nの間でのみ判定して、割り切れた整数をaとすると、それと同時にn / aを答えに追加すれば良い。 ここで注意点だが、a = n / aの時に両方を追加してはならない。 実装 // また実装する必要がある…

素数判定とは 与えられた整数nが素数かそうでないかを判定するアルゴリズムである。 普通に考えると、2 ~ n-1 でnが割り切れないかを確認すれば良い。しかし、 n = abとすると、min(a, b)は√nを超えない。これより2 ~ √nの間でのみ割り切れないかを考えると…

いもす法とは 累積和の応用であり、ある区間に一定値を足す操作を複数回高速でするアルゴリズムである。 実装 let mut imos = vec![0; 2 * 10usize.pow(5) + 2]; for &(s, t, p) in &stp { imos[s] += p as isize; imos[t] -= p as isize; } let mut need = …

累積和とは Σ(i = n) ^ m のクエリを高速に解くためのアルゴリズムである。 事前にΣ(i = 0) ^ m を求めておいて、これをS_mとするとS_m - S_(n - 1)が求めたい総和になる。 事前に求めるパートがO(N)であり、それ以降はO(1)でクエリをこなすことができる。 …

二分探索とは ある条件Pを満たす集合と満たさない集合の境界値を求める問題で、その集合の境界面が一つしかないときに使える。（説明が下手） なんかこう数直線でこっから右がokでこっから左がngってなっているみたいな、、、、 まず、全体を二つに分けて、…

順列全列挙とは 集合Sの元からn個選ぶ順列に関して簡単に全探索する関数がある。 実装 for v in (Sのiterator).permutations(n) これによって探索できる。 組合せ全列挙とは 集合Sの元からn個組み合わせる方法に関して簡単に全探索する関数がある。 実装 for…

半分全列挙とは 普通に探索すると、nかかるような探索について特殊な状況だと √n log √nで探索が終わる方法がある。これを半分全列挙という。 bit全探索の半分全列挙 実装 let n1 = n / 2; let mut s1 = vec![]; let a1 = a[..n1].to_vec(); for v in 0usize…

bit全探索とは 集合の部分集合全体を探索するアルゴリズムをbit全探索という。 実装 for v in 0..1 << n { let is_in = (0..n).map(|i| (v >> i) & 1).collect::<Vec<_>>(); これによって集合 S = {0, 1, 2, ..., n - 1}の部分集合全体を探索できる。ここでループv</vec<_>…

深さ優先探索とは グラフにおいて、いけるところまで深くいき、いけなくなったら引き返してまた同じことをする探索を深さ優先探索という。 実装 実装方法として再帰関数を用いる方法とstackを用いる方法がある。 再帰関数を使う方法は逃げてなのでstackでや…

幅優先探索とは グラフにおいて、ある頂点から初めてそこからの最短距離が短い順にグラフの頂点を探索する方法である。 実装 これはVecDequeを用いて実現できる。これは前後から取り出しができるvectorである。 let mut q = std::collections::VecDeque::new…

すみません。人からライブラリを拝借して一旦終わります。 理解できないですこれ。 // ---------- begin scc ---------- pub fn strongly_connected_components<G, I>(size: usize, graph: G) -> (usize, Vec<usize>) where G: Fn(usize) -> I, I: Iterator<Item = usize>, { let mut or</item></usize></g,>…

プリム法と同様に、重み付き無向グラフにおいて最小全域木を求めるアルゴリズムである。 クラスカル法とは 以下のアルゴリズムである。 辺集合Eを重みの小さな順にsortする。 その辺を追加しても閉路ができないのであれば、その辺を答えに追加する。この閉路…

プリム法とは、クラスカル法と同様に重み付き無向グラフにおいて最小全域木（とその辺の重みの総和）を求めるアルゴリズムである。 プリム法とは ある頂点を一つ選ぶ。 確定している頂点から確定していない頂点への辺のうち、重みが最も小さなものを通る辺と…

トポロジカルソートについて解説する。 トポロジカルソートとは 有向無閉路グラフにおいて頂点の並びであって、任意の辺に対してその辺が順方向に進むものへと並び替えることである。つまり、 頂点列(v{k_i})で任意の辺(v, v')においてv = v{k_i}, v' = v_{k…

今回はオイラーツアーを紹介する。これはある問題を解くためのアルゴリズムという感じではなくて、ある問題を解くためにこれを用意して応用して解く感じである。応用して解ける問題は徐々に追加していきたい。 オイラーツアーとは 木に対して頂点xからdfsを…

今回は単一頂点からの最短距離を求めるアルゴリズムであるベルマン-フォード法を紹介する。ここでダイクストラ法との違いはグラフ上の重みが負でも通用するところである。 ベルマン-フォード法とは 以下のアルゴリズムである。ここで頂点xからの最小距離を求…

今回は任意の頂点間の最小距離を求めるワーシャル-フロイド法に関して解説する。 ワーシャル-フロイド法とは 以下のアルゴリズムで任意の頂点間の最小距離が求まる。ここでdist[i][j]が頂点iと頂点jの最小距離とする。 次のようにdist[i][j]を初期化する。こ…

今回は最大公約数と最小公倍数の求め方を考える。 ユーグリットの互除法 ゆーグリッドの互除法とは、a, b(a > b)の最大公約数とb, a % bの最大公約数が等しいことを用いて、2つの整数の最大公約数を求めるアルゴリズムである。 これを用いるとgcd(a, b)が計…

正値重み付きグラフにおいて、ある頂点xから別の頂点への最短距離を求める方法として、ダイクストラ法がある。 ダイクストラ法とは 頂点xからの各頂点への最小距離を求めたいとする。この時、以下のアルゴリズムで求めることができる。 全ての頂点への最短距…

Rustにおいてグリッドのあるマス（i, j）に対して、その周辺を調べるときに境界条件の取り扱いが面倒である。そこで便利な関数を利用してこの周囲の探索を簡単に書く方法に関してまとめる。 方法 // 大きさ(h, w)のグリッドの // マス(x, y)に関してその上下…

ネガマックス法とは、ミニマックス法のうち手番の対称性に注目して実装をより簡単にしたゲーム問題用のDPである。手番の対称性とは、AとBが対戦するときにA, Bが取れる行動が等しいことをいう。 以下のような問題で用いることができる。 D - Game in Momotet…