分かった. どうやら僕のやつの場合わけを1箇所だけまとめて, あとはRとBで区別して場合わけしているところをまとめれば本質的には同じプログラムになるみたい. うーん頭いいなあ.

赤黒木の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に較べて全く速くならなかった. なんだかなあ. もっともっと問題のサイズを大きくしたら違うのかもしれないけど, この場合どうもメモリ使用量の限界…