投稿

Union-Find

イメージ
Union-Find とは 　素集合データ構造を扱うアルゴリズム。 　つまり、グループ分けを扱える。ただし、1 つの要素が複数のグループに属することはない。 Union-Find のアルゴリズム 　Union-Find には、主に Union と Find の 2 つの操作がある。 Union(x,y) 要素 x を含むグループと要素 y を含むグループを統合する。x と y が同じグループなら何もしない。 Find(x) 要素 x を含むグループの値 (例えば、グループの代表の要素) を返す。  実装方法 　高速に Union-Find を行うには、それぞれのグループを木とした素集合森でデータを扱うとよい。それぞれ、木の根をグループの代表者とみなす。初期状態において、各要素は自分のみのグループに属する。 Union と Find それぞれを工夫することで高速化を図る。Union は Find を用い、それ以外の部分は \(O(1)\) であるため、Union と Find の計算量は同じである。 Union 　2 つの木の高さまたは要素数を比較し、小さいほうの根を大きいほうの根に連結する。どちらか好きなほうを実装すればよい。 どちらを用いても、Union または Find の計算量は、\(O(\log n)\)。 　また、Find の高速化で木の高さが減少することがあるため、Find の高速化と併用すると正確な木の高さは取得できなくなることに注意。要素数は変わらないため、取得できるようにしておくといいことがあるかも (競プロで使うことはある)。 Find 　Find の計算量は木の高さ (Find する要素と根の距離) に依存する。そのため、Find しながら木の高さを減らしていく。以下の 3 つのうち好きなものを実装すればよい。 ・path compression 　[Find する要素] の親を新たな要素とする。これを要素が根になるまで続ける。根まで到達したら、辿ったすべての要素の親を根に書き換える。 ・path splitting 　[Find する要素の親, 要素の親の親] を新たな [要素, 要素の親] とする。これを要素が根になるまで続ける。 ・path halving 　Find する要素の親を要素の親の親に書き換える。その後、要素の親 (元...
コメントを投稿
続きを読む

ワーシャルフロイド法

イメージ
ワーシャルフロイド法とは 　グラフのすべての頂点の組 (u,v) に対して、u から v への最短距離を求めるアルゴリズム。 　辺のコストが負でもよい。 ワーシャルフロイド法のアルゴリズム 頂点 u から頂点 v への距離 d[u][v] を u から v への辺 (u,v) のコストで初期化、辺がなければ無限大としておく。また、頂点 u から頂点 u 自身への距離 d[u][u] は 0 としておく。 以下の操作を k=0, 1, …, n-1 (頂点数: n) の順に行う。 グラフのすべての頂点の組 (u,v) に対して、通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに限定したときの最短距離を求め、その距離が d[u][v] より小さければ d[u][v] をその距離で更新。 距離 d[u][u] < 0 となる頂点 u が存在すれば、負閉路が存在する、存在しなければ負閉路も存在しない。 説明 アルゴリズムの 2. の操作 (図) 　例えば、こんなグラフがあったとする。 　例えば、k=2, u=4, v=6 なら、以下の範囲で頂点 u から頂点 v への最短距離を調べる。(頂点集合 {0, 1, 2} ∨ {4, 6}) 　これを、(k, u, v)=(0, 0, 0), (0, 0, 1), …, (0, n-1, n-1), (1, 0, 0), …, (1, n-1, n-1), …, (n-1, 0, 0), …, (n-1, n-1, n-1) の順に調べていく。(一応、k が k=0, 1, …, n-1 の順なだけで (k, 0, 0), (k, 0, 1), …, (k, n-1, n-1) は順不同。) 通れる頂点を限定したときの最短距離ってどう求めるの？ 　[通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに限定したときの最短距離 (以下、d k [u][v])] は、すべての頂点の組 (u, v) で、[通れる頂点を頂点集合 {0, 1, …, k-1} ∨ {u, v} の頂点のみに限定したときの最短距離 (以下、d k-1 [u][v])] を求められていれば簡単に求められる。 　まず、[通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに...
コメントを投稿
続きを読む

ベルマンフォード法

イメージ
ベルマンフォード法 ベルマンフォード法とは 　グラフのすべての頂点に対して、ある頂点からの最短距離を求めるアルゴリズム。 　 ダイクストラ法 と違い、辺のコストが負でもよい。 ベルマンフォード法のアルゴリズム スタート地点の頂点からその頂点自身への距離は 0 とし、それ以外の頂点の距離は無限大としておく。 以下の操作を n-1 回 (頂点数: n) 行う。最後に、以下の操作をもう 1 回行う。 すべての辺に対して、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。 最後の 1 回の操作で、[終点の距離] > [始点の距離+辺のコスト] である辺があった場合、与えられたグラフに負閉路が存在する、なかった場合、負閉路は存在しない。 例と説明 ベルマンフォード法の動き (GIF) 説明 　スタート地点を頂点 0 とする。 　スタート地点の距離は 0 で初期化する。 　この時点で、スタート地点から各頂点へ 0 ステップ (0 回の移動) で行ける経路のうち最短の距離が求められている。([0 ステップで行ける = 移動しないで行ける] なので、頂点 0 のみ行ける (距離は ０)。) 　(1回目) すべての辺に対して、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。(今回は、辺 (0,1), (0,2), (0,4), (2,1), …, (4,3) の順に更新しているが、順番は関係ない。) 　この時点で、スタート地点から各頂点へ 1 ステップ以下で行ける経路の最短の距離 以下の距離 に更新されている。(もともと各頂点で 0 ステップで行ける経路の最短距離が求められている。辺を走査すれば +1 ステップの距離がわかるため、各頂点への距離は、少なくとも 0 ステップ または 0+1 ステップで行ける経路のうち最短の距離 以下 には更新される。( 以下 としているのは、辺の走査順によっては、+2 ステップ以上調べられる場合があるからである。(例えば、辺 (0,4) のあとに辺 (4,3) を調べているため、頂点 3 は、この時点で、2 ス...
コメントを投稿
続きを読む

ダイクストラ法

イメージ
ダイクストラ法とは 　グラフのすべての頂点に対して、ある頂点からの最短距離を求めるアルゴリズム。 　辺のコスト (距離) は非負である必要がある。 　例えば、こんなグラフから、 このように、頂点 0 からの距離 d を求められる。 ダイクストラ法のアルゴリズム スタート地点の頂点からその頂点自身への距離は 0 で最短距離として確定し、その頂点を u とおく。それ以外の頂点の距離は無限大としておく。 すべての頂点への最短距離が確定するまで、以下の操作を繰り返す。 u からの辺がある、すべての頂点 v の距離を、[v の距離] と [(u の距離) + (辺 (u → v))] のうち小さいほうに更新する。 確定していない頂点のうち、距離が最も小さいものを最短距離として確定し、その頂点を u とおく。 例と証明っぽいやつ ダイクストラ法の動き (GIF) 説明 　スタート地点を頂点 0 とする。 　辺のコストは 0 以上なので、スタート地点の最短距離は 0 で確定する。 　頂点 0 から 1 ステップ (1 回の移動) で行ける頂点 (頂点 1、頂点 2) の距離を更新する。 　(頂点 1: (初期値: ∞) → (頂点 0 の最短距離: 0) + (頂点 0 から 頂点 1 への辺のコスト: 2) = 2) 　(頂点 2: ∞ → 0 + 7) 　この時点で、確定していない頂点 1 ~ 4 のうち、距離が最小の頂点、頂点 1 を最短距離と確定できる。 　( 証明的なやつ: 今、頂点 0 から 1 ステップで行ける経路の探索をした。それ以外で、頂点 1 にたどり着くには、頂点 0 から 2 ステップ以上移動しなくてはならない。頂点 0 から 1 ステップ移動するときの最短距離は、頂点 1 に行く場合で、距離は 2 である。辺のコストは非負なので、2 ステップ移動する距離は 2 以上だとわかる。なので、頂点 1 の距離 2 は最短距離であるとわかる。) 　次は、新たに確定した頂点、頂点 1 から 1 ステップで行ける頂点の距離を更新する。 　(頂点 2: 7 ≦ 2 + 6 なので変化なし、頂点 3: ∞ → 2 + 2) 　この時点で、確定していない頂点 2 ~ 4 のうち、距離が最小の頂点、頂点 3 を最短距離と確定できる。 　( 証明...
コメントを投稿
続きを読む

とりあえず VSCode を入れたい (C++, gcc, Windows)

イメージ
　競プロ用に VSCode を入れたのでメモ。 Visual Studio Code (VSCode) と gcc のインストール VSCode のインストール 　まず、VSCode のサイトから [Windows] をクリックでダウンロード ([Windows] と User Installer [64 bit] は同じ) (全ユーザーにインストールしたいなら System Installer)。 ・VSCode のダウンロードリンク 　(  https://code.visualstudio.com/download  ) VSCodeUserSetup-x64-X.XX.X.exe (X.XX.X はバージョン) がダウンロードされるので実行。使用許諾契約書に同意すると、追加要素を選択する画面になる。 ・デスクトップ上にアイコンを作成する 　デスクトップから VSCode を起動できるようになる。 ・エクスプローラーのファイル コンテキスト メニューに [Code で開く] アクションを追加する 　ファイルを右クリックすると [Code で開く] から VSCode でファイルを開ける。 ・エクスプローラーのディレクトリ コンテキスト メニューに [Code で開く] アクションを追加する 　フォルダを右クリックすると [Code で開く] から VSCode でフォルダを開ける。 ・サポートされているファイルの種類のエディターとして、Code を登録する 　ファイルを右クリックすると出る [プログラムから開く] に [Visual Studio Code] が追加される (そのファイルの種類に VSCode が対応している場合)。 ・PATH への追加 　Code コマンドで VSCode を開けるようになる。 で、[次へ] -> [インストール] を押してインストール完了。 gcc のインストール MSYS2 のインストール 　いろいろインストールするのに便利な MSYS2 を入れておきたい。msys2-x86_64-XXXXXXXX.exe (XXXXXXXX はバージョン) をダウンロード。 ・MSYS2 のダウンロードリンク (普通はこっち) 　(  https://www.msys2.org/ ) ・バージョン違...
コメントを投稿
続きを読む