ACM/ICPC アジア地区予選 東京大会

ICPC

tanakh2005-11-07


ICPCに参加してきて、途方も無く疲れたので、
昨日、今日とずっとふさぎこんでいました。
本当に疲れました。

・一日目 → はしゃぎすぎた
・二日目 → はしゃぎすぎた
・三日目 → 体力・精神力の限界が来た

三日目は口を開けば疲れた、と言っていたような気がする。
不快な思いをさせちゃってたらごめんなさい。


とりあえず、フォーマルな？文章ができました。
http://fxp.hp.infoseek.co.jp/icpc2005/regional/
私の視点からの問題の解け方が全て書かれていますので、
もしよろしければ参考にでもしてやってくださいな。


以下、インフォーマルな文章でもつらつらと書いておこう。

        • -


11月3日。朝9時ごろ出発。
新幹線の中でRobocodeを動かしてみる。
12時ごろ着。まだほとんど人が来ていなかった。
13時まで待って一番乗りでRegistration。

待っている間の光景。しょっぱなから飛ばしまくる。
はい、いきなり変なことをしていたのはうちのチームです。


登録が済んでから昼食に行っていなかったので昼食に。
東京工科大の食堂を使わせてもらうことに。
食堂着。2Fにて。

すごいものを発見。

ツャラポクて…。


食堂は2〜4Fに別々な店舗が入っているようだった。
とりあえず2F軽食堂に突入。
食券を買おうとするが、お金が入らない。
しまった。休業中だった。
仕方が無いので、3Fに。
今度はやってそうだ。メニューを決めて中に。
しかし、なんだか様子が変。
中の人いわく、「今日は貸切。4Fならやってるけど、あと3分でオーダーが終わる」
仕方が無いので、4Fに。
今度はなんとかなりそうな雰囲気、でもメニューがカレーとそばしかなかった。
仕方が無いのでカレーを注文。ようやく昼ごはんにありつけた。
しかしまたなんでいきなり大変な目に遭っているんだろう…。
帰り際にテーブルに積んであったコミックハックを失敬する。
http://blog32.neec.ac.jp/archives/50052771.html
これはいいネタが手に入った。


会場に帰還。かなり時間ぎりぎりだった。
いきなりコーチに怒られる。
「うちらは悪くないよ〜」
コミックハックをテーブルの上に放置。
さすがみなさん、食いつきが違いますね。
写真を撮って開会式を聞き流して(どうせひとつも聞き取れませんよ〜だ)
練習セッション。
練習セッションだけど、私は本気だ。
(というのも、去年練習セッションで一位取ったら本選でも一位が取れたから、
縁起担ぎという意味合いが大きいのだ)
スタート。一問目、数のmax、2分。二問目、方程式、3分。
三問目、一行72文字echo。7分。
さて、さすがにトップだろう…とスコアボードを見ると、
合計11分のチームが…2分負けた。
チームIDと座席の位置から推測するにトップはNimrodチームに間違いなかった。
くそー、こんなところまで本気でやら無くてもいいのに…。
ショックを受けながらお菓子を食べに行く。
そこかしこに愚痴をこぼして帰ってくると、
スコアボードに異変が。4問正解チームが出てる。
あれ、4問目ってJavaチャレンジじゃなかったの？
よく読んでみると、何を送ってもYesが返るとなっている。
ああ、なんでそういうところを見落としているんだろう。
早速適当なファイルをSubmitする。うちも4問正解になる。
しかも、スコアがこの時点でトップに。
どうやらNimrodは4問目でミスしたようだ。
と言うことは、さっきまでに4問目を送っていたわけで、
実質的に最速はうちで間違いなかったようだ。


ひと悶着あったものの、練習でトップが取れて満足。
一息ついてコミックハックを読んでいると
緑服のスタッフのお姉さん？がやってきて
そんなもん読まないの、と一蹴。
あははは、もう練習は済んだので…とか言っていると
ここで超重要事項を教えてもらうことになる。
なんと、Nimrodはオープン参加になると言うことだ。
Nimrodがいなくなるんだから、おめーら頑張れ、
要約するとそんなことを仰って帰って行かれた。
おほー、これはとても良い事を聞いた。
これでFirst Placeがずっとずっととりやすくなる。


そういうわけで、コミックハックを読むのはやめて、
いろいろと検証作業に入ることに。
・abort() → Runtime Error
・スタックオーバー → Wrong Answer (Runtime Errorにならない)
・ヒープ使いきり → Runtime Error (MLEにはならない)
・ゼロ割りエラー → Runtime Error (Floating Point Exception)
・出力しまくり → TLE (OLEにはならない)
・タイムリミット →
大体三分とあたりをつけ、170秒と190秒待つプログラムを送りつける
170秒 → Yes
190秒 → TLE
∴三分で間違いなし
大体完了。
いろいろ試しているときに気づいたんだけど、GCC4の最適化はすごすぎる。
末尾再帰を普通に最適化してしまう。
というか、末尾じゃない再帰も最適化してしまう。
CPS変換？いや、どうなってるのか分からんけどすごすぎる。

int f(int n)
{
  if (n==0) return 0;
  else return n+f(n-1);
}

これに一億とか突っ込んでも平気で計算している。
恐るべし、GCC4。


それも終わってやることが無いので、まだJava Challengeが始まっていないけど、
Robocodeを走らせて見る。
まぁ、これぐらいいいでしょう？
それから、JavaChallngeが始まる。
まずは何もしないものを作ってみる。
えらく苦戦。というか、Eclipseの使い方が良くわからん…。
何とかプロジェクトが作れた。APIとかを調べながら戦略を練る。
うーむ、なんか思ってたのと違う。
とりあえず、現在見えている敵の位置を管理するルーチンを書こうということになった。
Mapに格納するとしたのだが、Mapをイテレートする方法が分からない。
というか、何でMapにはiterator()メソッドが無いの？
ずいぶんかかってKeyのセットを取ってからそれをイテレートする実装に。
で、それができたあたりで「残り10分です」
はぁ？なにそれ。私はてっきりあと二時間以上残っているものだと思っていた。
計画が完全に駄目になった。
もうどうしようもないので、サンプルにあったSpinBotから適当にソースを抜き取って貼り付け。
結局出来上がったものは、"余計な処理をする"SpinBot。
こりゃひどい。もうどうでもいいや…。


それから、食堂に集まって来賓の言葉を聞いたり自己紹介をしたりがあった。
全体的に面白いのが多かったね。面白けりゃいいってものでもないけど。
うちのはλ文字山が思った以上に受けていた。
さすがにこの選手層だとえらく話が通じますね。
あと、チーム説明は攻撃的過ぎるとの評も頂いた。
まぁたしかに、あれは勝つ気まんまんに見えますわな…。
でも、実際にそうだから良いんですよ！
食事はいつもどおりバイキングスタイルだったが、
寿司の良いネタは一瞬でなくなる。
私がのそのそしていたら、イカとかっぱしかのこってないの…。
こりゃひどい。サンドイッチとかサラダとか食べてましたよ。


それでこの日は終わりなので、泊まるところに。
私はなんだか知らないが一日目はホテルに泊まれるものだと思っていたら、

こんなところに送り込まれてしまった。
山の中。山の中のコテージ。そりゃないだろ〜…。

ギャップをお楽しみください。
明日は万全の体制で望みたいのに、これではなぁ…。
そこはいろいろすごいところだったが、風呂場が特にすごかった。
脱衣所と風呂場の仕切りなし。寒いって。
夜は息苦しくてなかなか寝付けなかった。
ほんと大変だった。


次の日、起きたら持病の喘息が若干発症していた。
おそらくほこりのせいだろうか。ああ、なんということだ。
朝食の時間まで待って朝食に。食堂までは急な斜面を上り下り。
よりにもよって一番遠い部屋が割り当てられてしまったもんだ。
朝食をゆっくり食べていると結構時間が遅くなってしまった。
それからまた部屋に戻って、荷物を取りに言って、バスのところに向かう。
ところがここで大失態。
バスの時間が10分早くなったのをみんな聞き逃していたらしい。
(私はそもそも全連絡事項をスルーしてるけど…)
コーチから電話が何度もかかってくる。
ああ、私は悪くないって。
山道を走る走る。ほんと、試合前にこんなことしたくないんだってば。


そして会場に。


(本選の様子は参加記に書いたのでカット)


(学校見学もカット)


そして表彰式。
スコアボードでNimrodに次ぐ順位を出していたとはいえ、
失格と言うことも考えられるので、ちょっと緊張。
そして、First Place 'combat'。
やったー。今年も勝てるとは。
正直今年はつらい戦いになると思われた。
昨年度が終わった時点では今年はGokuriも抜けるし
東工大の強いところも抜けるし、
あそこも抜けるしあそこも抜けるし、
敵はGNCぐらいだな、とか思っていたんだけど、
まさか東大にここまで埋もれていた人たちがいたとは。層が厚すぎますね。
その層を全て打ち破り、かつ海外チームにも勝つとなると、
ほんともう大変で…。
まぁ、何にせよ勝ててよかった。
インタビュー受けたり、コメント考えたり、Nimrodの人の
話を聞きに行ったり、いろいろ楽しかった。
湯浅先生がわざわざ会場に来てくださっていた。
私なんかのために来ていただいて、光栄でございます。


それからセミナーハウスに帰って二次会。
なんというか、公式にお酒が出た？いいんだろうか。
それともあれは非公式イベント？
何はともあれ、はしゃぎすぎた。
多分一番はしゃいだのはうちのM君とGNCのNさんだろう。
このたび彼らの愛し合う瞬間が激写されてしまったので
そのうち出回るかもしれない。
私も入手したら拡散に協力しよう。


この日はとても疲れた。
8問分のコードをぶっ通しで書いた上に立て続けで
M氏とN氏のテンションに付いていくのは自殺行為とも言える…。
すごく疲れたので、11時過ぎには寝てしまった。


次の日。ボーリング。
ボーリングをする前から疲労はピークに。
というか、疲弊しきっているのが分かりきっているのに
なんでこう、次の日ボーリングなんていれるのかな…
主催者は何を考えているんだ(こういう場合は温泉と決まって…)。
まぁでも、せっかくなのでボーリングをする。
私は見かけによらず？平均8本ぐらいは倒せた。
(ストライクとスペアはちっとも出ないんだけど…)
で、チームのスコアはダントツ最下位。
だんだんましにはなっているんだけど、そういうレベルだ。
でも、ほかの京大チームもしょぼい点だったので、
京大とはそういう大学と言うことで納得だ。
で、必死に頑張っていた私であるが、
第二ゲームの途中で体力の限界が来る。
気分が悪くて動けなく…。
唇青いとか言われたけど、やっぱりそうなってましたか。
とりあえず、テンションを落として安静にしていると
終了するころにはなんとか歩けそうなぐらいには体力が回復した。


それでなんとか家に帰るに至る。
やっぱ家はいいよね…
本当に大変な日々でした。
今日になってようやく体調が本調子になってきたのだが、
今度は北京行きが目の前に。私の体力は持つのだろか…。