ICPC2004 in Haskell

Haskell ICPC

ずっとやろうと思っていたのだが、
なんだかほかのことをやっていたらこんなに遅くなってしまった。
ゲームが一段落した?ので気晴らしに解いてみることにした。
問題Dぐらいまではさくさく解けたのだが、
問題Eは結構めんどくさかったし、
問題Fはなんかへんなとこにはまり込んでしまって
とても疲れてしまった…


Haskellで解く場合の各問題のポイントでも。

  • 問題A

関数合成でとくとすっきり美麗に解ける。
(ここでかなり昔に書いた記憶が)

  • 問題B

普通に再帰だろう。
盤の表現に多少悩まされる。
この問題はサイズの上限が200なので、普通に[ [Char] ]とかでよいかと。
お好みでArrayでも。

  • 問題C

普通に深さ優先を実装。
Data.Ratioを使うと多少楽。

  • 問題D

これも普通に書ける。
(普通ばっかりやな…)
リストの内包とかのおかげでC++とかで
イテレータ使ってたところが幾分すっきり。

  • 問題E

これも普通に実装…
ただし、代数的データ構造とパターンマッチのおかげで
再帰的記述が相当すっきり。

  • 問題F

問題となるのはグラフの表現とグラフの探索であろう。
C++では隣接行列で表現したが、
Haskellではエッジリストで実装した。
今回はオーダがとても少ないのでこれでいいと思ったのだが、
各点からのノードリストの集合とかの方が計算量で有利かもしれない。
ただ若干実装は複雑になると思われる。
通りの名を文字列→整数の写像を作って最終的に整数のグラフで
問題を解いたのだが、よく考えるとそんな必要はどこにも無かった…
通りの数は全部まとめてnubでカウントできるし…
グラフの探索は文字列のままで問題なさそう。
(計算量は所詮定数倍定数倍…)


まぁ、大体こんな感じ。
というわけで、気になる(?)実行速度であるが、
各問題に対してFirst Input Dataの処理速度、

$ time ./a < a1 > dest

real    0m0.134s
user    0m0.030s
sys     0m0.000s

$ time ./b < b1 > dest

real    0m0.086s
user    0m0.020s
sys     0m0.010s

$ time ./c < c1 > dest

real    0m15.962s
user    0m0.020s
sys     0m0.010s

$ time ./d < d1 > dest

real    0m46.361s
user    0m0.030s
sys     0m0.010s

$ time ./e < e1 > dest

real    0m0.116s
user    0m0.020s
sys     0m0.020s

$ time ./f < f1 > dest

real    0m10.074s
user    0m0.010s
sys     0m0.020s

PentiumM 1Ghzにて。
Dが多少いらいらいら…
ABEは問題のオーダからいってほとんどノータイムだ。
CとFも許容範囲だろう。


で、ここはやはりC++の比較をするべきだろう。ソースは
http://fxp.hp.infoseek.co.jp/icpc2004/domest.html
これで。

$ time ./ac < a1 > dest

real    0m0.107s
user    0m0.100s
sys     0m0.020s

$ time ./bc < b1 > dest

real    0m0.280s
user    0m0.090s
sys     0m0.020s

$ time ./cc < c1 > dest

real    0m2.246s
user    0m2.102s
sys     0m0.030s

$ time ./dc < d1 > dest

real    0m12.304s
user    0m12.117s
sys     0m0.000s

$ time ./ec < e1 > dest

real    0m0.185s
user    0m0.040s
sys     0m0.020s

$ time ./fc < f1 > dest

real    0m0.827s
user    0m0.660s
sys     0m0.030s

一応…コンパイルはGHCもG++も-O2付きで。
ABEはこちらもノータイムなので
誤差の範囲だろう。
Cが8倍、Dが4倍、Fが12倍ぐらい。
Fがひときわ遅いのはグラフの扱い方のよるものだろう。
でもまぁ、このぐらいの速度が出ていれば(個人的には)満足である。


○今日の生成物
http://fxp.infoseek.ne.jp/haskell/icpchas.zip
問題A以外はC++版とそんなにアルゴリズムに違いが有るわけではないけれど。