前々回のエントリで、Union-Findの効率が少し悪いとコメントをいただいた。確かに、実務上の問題は小さそうだが、このデータの持ち方はイマイチかもしれない。 そこで、次のように書き直してみた。 各ノードにParentとRank情報を持つ 配列ではなくツリー構造…

ひどいデザインで有名なTopcoderのサイトだが、本当に目的の記事にたどり着けないレベルになってしまった。 個人的によく使うところをメモしておく。 SRM Match Editorials http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis アクテ…

クラスカル法（連結グラフの最小全域木を求める）はアルゴリズムがとても分かりやすくて好ましい。参考は例によって蟻本。 ・辺の集合から、最小コストのものを見つける ・この辺が、これまで取り出した辺と連結していなかったら使う。連結済なら破棄 →これ…

宇宙少年の息子のために、ボールやビー玉で太陽系を作ってあげた。そのときにいろいろ計算した結果を、捨てるのも何なので日記に書いておく。 まず太陽系の恒星と惑星。木星の直系を24cm（大人用のバスケットボールくらい）に合わせると、地球と火星がビー玉…

二次平面幾何の復習として、内積や外積、線の交点などを計算するコードを書いてみた。どこかで再利用するかもしれないのでクラス化してある。 参考にしたのは蟻本とこのサイト。 まず、X・Y座標の保持と、座標用の演算オペレーターを用意する。 /// <summary> /// Pon</summary>…

前エントリでPriorityQueueが用意できたので、最短経路を解くコードをダイクストラで書いてみた。PriorityQueueを二分ヒープで実装したため、計算コストはO((E+V)logV)になっているはず。 ダイクストラ法 - Wikipedia なお、C#のTupleがIComparableではない…

.NETのC#にはPriorityQueueがなくて困るので自作してみた。 二分ヒープを使った実装で、ほとんど蟻本のソースコードそのまま。ただし、次の拡張を行っている。 ジェネリック型に対応 昇順、降順の指定可 カスタムIComparerを指定可 Peek()、Count()、Clear()…