C#

初等整数論の基本の復習

2016/8/20誤記修正基本的な数学がいまいち使いこなせてないので復習しておく。参考にしたのは蟻本と以下のサイト。 http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ ユークリッドの互除法 整数aとbについて、a > b > 0 かつ a % b を r とした…

Topcoder Marathon Match Round90の参加日記

TopcoderのMarathonMatchは、過去3回参加していずれも上位3割くらいの結果に終わっている。よって目標は上位2割。 これまでの反省点まとめ 問題をちゃんと読む 紙と鉛筆で考えてから組む。いきなり実装しない Web等を参考にしすぎない。アルゴリズムは自…

Union-Find書き直し(C#)

C#

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

C#実装(Kruskal法とUnionFind)

C#

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

アメリカ大手IT企業での就職面談(失敗記)

半年ほど前だが、アメリカの超大手IT企業からスカウトが来て、そのくせ電話面談で落とされるという屈辱的な経験をしたので、戒めとして晒しておく。 4月下旬 LinkedIn経由でリクルーターからメッセージが届く。デトロイトで本社採用SDE(Software Development…

二次平面のベクトル演算(C#実装)

C#

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

ダイクストラ法の実装(C#)

C#

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

C#でのPriority Queue(優先キュー)実装

C#

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