« 型推論C++ | Main | Wiki公開 »

July 02, 2005

ICPC2005国内予選

1年前の「/Oxの悲劇」から1年、オセロ、コンパイラ、CPUエミュレータと着実に実装経験を積み重ね、我々Team UFOはTeam UFO/Oxとなって再びここに戻ってきた。

競技中の我々をサポートするものは、かの飲料と、マシュマロである。

結果はUnno氏の日記に詳しいが、国内14位、学内9位という結果に終わった。またもやklonoaに、さらには3年生2チームにも負けるという結果に。どうしたものか。

俺は開始後、おーくらと共に問題を読んで評価するという作業をまず行った。今年の問題は、ぱっと見での難易度が判定しやすかったように思う。Eは捨てることとし、残りの5問を解ききろうということになった。

Cは見るからに簡単で、残り30分といった場合でも余裕でできそうに思われたので、とりあえずできそうだけど面倒そうなFに取り組むことになった。思えば、タイムでの争いを考えるならば、とにかく解けるところから解いていくことを考えるべきだったのかもしれない。

Fは2つのフェーズからなる。第1のフェーズは始点及び「汚れたタイル」を頂点とみなし、全頂点間の最短距離をそれぞれ求める。おーくらがDPのようなアルゴリズムを考案。それによると、w*hのマップ上に最短距離を書き込んでいく。この際、「最短距離1を書き込むループ」「最短距離2を書き込むループ」…と順に行っていくことで、各点の最短性が確実に保証される。
第2のフェーズは先ほど求めた距離情報を使って、始点から出発し全頂点(「汚れたタイル」)を巡回する最短経路を求める部分だ。いわゆる「巡回セールスマン問題」であり、一瞬ひやっとしたが、頂点は高々10程度なのでなんとかなるだろうと判断。練習会において同じような「20の頂点を巡回する」という問題を見ていたのが役立った。一応「現在わかっている最短距離を既に超えてしまったらそれ以上の探索はしない」という条件だけ付けて全経路を探索。

いくつかのコンパイルエラーを取って実行すると何かヘン。vectorのどこかをはみ出しているのかと思ってじっくり探すが見つからず。入力データがおかしい?どうやら、VC++でコンパイルしたプログラムにcygwinの/dev/clipboardからの入力をリダイレクトするとヘンな値が読み込まれるらしい?他の方法でデータを与えるようにしたら、一発accept。実行は第1、第2のデータともに一瞬だった。

しかし、コーディングに時間を使いすぎた。まずはタイピング。初めてさわるX40の英語キーボードで大会に出ようというのがそもそもの間違いだったという説もあるが、日本語キーボードでもそれほど速いわけではないし、あまり関係ないか。あとはソースコードが無駄に綺麗だ。class Solverとか書いてるし。

そんなこんなで、今年もアジア大会は夢のまた夢。さらに悪いことに、例えもう一問解いていたとしても無理という驚愕の事実。なんてこった……。とりあえず、チームメイトの2人は本当にお疲れ様。

全問正解しちゃうようなチームの戦いの様子を記録したビデオとか見てみたい気がする。どのような役割分担で、どのようなタイミングで何をすればいいのか。そういう面の向上も重要だと思い知った一日だった。

|

« 型推論C++ | Main | Wiki公開 »

Comments

Post a comment



(Not displayed with comment.)


Comments are moderated, and will not appear on this weblog until the author has approved them.



TrackBack


Listed below are links to weblogs that reference ICPC2005国内予選:

« 型推論C++ | Main | Wiki公開 »