赤黒木のinsertをOCamlで書きました. removeはもっと全然面倒で, 書いてはみたけどデバッグに途方に暮れ挫折しました. module type OrderedType = sig type t val compare : t -> t -> int end module Make(Ord : OrderedType) = struct type elt = Ord.t ty…

Division One初参加!! と思ったら全問解けなくてなんとなくしてみたChallengeが失敗して-25点. 厳しいなあ.次回はまたDivision Twoです. まずは修行しよう.

前から気になっていたんだけど, 学校が冬休みで時間があったので, http://www.topcoder.com/のAlgorithm Cotestに参加してみた.250点問題, 500点問題は解けたけど, 1000点問題は無理でした. おもしろいこととして, このコンテストにはプログラムをsubmitした…

ここ数日, Dijkstra法が速くならないかと思ってFibonacci Heapを勉強して実装してみたんだけど, Binary Heapに較べて全く速くならなかった. なんだかなあ. もっともっと問題のサイズを大きくしたら違うのかもしれないけど, この場合どうもメモリ使用量の限界…

調べたことのメモ.Dijkstra法でグラフの最短経路を求めるプログラムを書いていて, 次のように書きたかったのが発端. d[i] = min(d[i], d[s] + g[s][i]); d[]はdoubleの配列型だとして, 問題は配列の中身に無限大に相当する値を入れたいことだ. たとえばd[s] …