HAL研プログラミングコンテスト

http://www.hallab.co.jp/progcon/2005/index.html

後でやろうやろうと思っていたら終わってました。
がががががーーーん。とてもショックです。(賞金が…)
22日までと思っていたら、22日に結果発表だったのですね。

というわけで、腹いせにコードを書きました。
超適当な実装ではありますが、ローカル(PM-1.2G)にて452847のスコアをマークしております。
サンプルをサブミットしたらローカルの半分ぐらいのスコアたっだので、
だいたい20万は越えているのではなかろうかと。
ちゃんとシステムに投稿された方がおられましたら、
私のコードがいかほどのスコアになるか推測していただければうれしいです。

プログラムの方は、
連結判定にunion findを使っているので、
これを単にDFSにすればやや高速化されるはずですし、
BridgeListを何回も参照しているにもかかわらず
毎回メソッドを呼び出しているので、これをどこかメモリにおいておけば
これまた速くなるはずで、
グラフを辺のリストじゃなくて隣接リストにすればルート作成が速くなるはずで、
一方通行辺が二つあったときのルート修正のループ探索が馬鹿サーチなので、
工夫すれば速くなるはずで、
いろいろ面倒な高速化を全くやっていないので、
きっと全部やれば1.5〜2倍ぐらいは速くなると思われるのですが、
どんなもんですかね。

ところで、これを書いてる途中でVisual C++ 2005 Express Editionを
導入したのですが(そのためコードのインデントががたがたですが…)
なかなかいいですね、久々のビジュアルデバッガは。
でも、2003との違いはツールバーしか分からなかった。