最小全域木の探索について アルゴリズム ナイーブな実装だと計算量が 程度。ノード数が多いグラフでは計算量をいかに落とすかがポイントっぽい。 プリム法 グラフ の頂点全体の集合を 最小全域木(MST)に属する頂点の集合を とする。 から任意の頂点 を選び、…

グラフの探索方法のメモです。 実装の詳細というよりも、概念のメモです。 幅優先探索 1.キューに入れる(add)。訪問済にする。 2.キューが空でない限りループする 2-1.キューから取り出す(remove)。 2-2.隣接ノードに訪問する。未訪問の場合のみ、キューに入…

小ネタ 小ネタです。プログラミングをしていると、最小公倍数とか最大公約数を求めよ。 みたいなシーンに遭遇します。以下のプログラムで簡単に求められます。 public class Sample { public static void main(String[] args) { long a = 10001; long b = 95…

剰余環について AtCoderの問題で剰余環についてふと思ったので、復習しておきます。 用語 同値類 集合 で同値関係 が定まっているとき、 を を変域とする変数とする。 の空でない部分集合 が の2つの条件を満たす時、 を同値関係 に関する同値類という。 を…

LinkedListについて 基本的なことですが、以下の問題を解いていたときにうっかりやってしまっていた事項です、、 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp LinkedListに入っている先頭から末尾までのすべての要素を順番…

累積和 区間に含まれる特定の個数を高速に求める方法をAtCoderで学びました。累積和と呼ばれるアルゴリズムのようです。 理解したことを整理しておきます。 AtCoderでの問題は以下です。 https://beta.atcoder.jp/contests/abc084/tasks/abc084_d 簡略化のた…

ガベージコレクタ ここではJavaのガベージコレクタのうち、パラレル型ガベージコレクタ(スループット型ガベージコレクタとも呼ばれます)について紹介します。パラレル型ガベージコレクタはUnixベースのマルチCPU環境ないしは、64ビットJVMではデフォルトのガ…

深さ優先探索(Depth First Search)とは グラフを探索するアルゴリズム。可能な限りある頂点に隣接する頂点を訪問するという戦略に基づいています。 未探索の接続辺が残されている頂点の中で最後に発見した頂点 の接続辺を再帰的に探索します。 の辺のすべて…