ICPC アジア地区予選に参加してきました。 @izuru_matsuuraと@cormoran707と共に、神戸大学のTEAM HARAIとして参加しました。 A,B,Fを通して27位でした。

1日目

trialでは右shiftが変なキーボードに驚く。xmodmapで_を^[[Aに退避させ、_をshiftで上書きした。 強いプログラマが沢山運営に関わっているのに、どういう理由であんなものが採用されてしまったのか気になる。

java challengeもした。提出しても一向に実行されないので動作確認できない、問題文中から座標が0-basedなのか1-basedなのか読み取れない、queueが詰まってるなあと思っていたらweb serverも落ちる、と大変だった。java、queueが詰まってるなあと思っていたらweb serverも落ちる、と大変だった。同じ大学の人が回ってきて、なぜここにいるの？と聞いたらjava challengeのstaffとのことだった。 ぐだぐだだったし、結果もサンプルを投げただけのチームの優勝であったが、これはこれで面白くはあるし、余興としては十分なのかもしれないなと思う。

2日目

コンテスト

国内予選では15位を、模擬地区予選では私は欠席したが18位を取っていたので、開始前は、1桁順位を目標にしたいとか言っていた。

xmodmap等に慣れているのは私なので、開始直後に私が設定を書き、チームメンバーが問題を読むという分担をする。 設定を終えると、A問題が解けそうだと聞かされる。しかし読んだ人間が実装を不安そうにしていたので、私が書く側でのペアプロをする。通る(開始後16分)。 次にB問題。そう難しくない幾何らしい。安全のため私が見る側でペアプロ。コーナーや誤差でWAを生やす。 debugは任せて、C問題が解けそうなので書こうという話になる。ペアプロのため問題を聞かされるが、あまり理解できない。 ぐだぐだしてる間にBが通る(開始後75分)。C問題は2人に任せた方がいいと判断して身を引く。

E,F問題が私が得意そうな問題だということでEとFを読む。 Eは分からなかったが、Fは好きな感じの問題。 $O(p^2r \log t)$で解けそうだ、ということに。 でもちょっとTLE怪しくない？と言われる。C問題が通ったらとりあえず書いてみるか、という話に。 紙の上で概算すると$10^9$となり、なるほどこれは怪しい、F問題だし二分探索するだけの簡単問題なはずはないよなあ、ともう少し考える。 「解けたかも」「おお、よし聞こう」「えっとね、ああ、ごめん違った」みたいなやりとりを5,6回繰り返した後に、後ろから見ていけば$O(p^2r + pt)$で解けると判明。 ちょっと考えたことを全て、信頼の置ける人間に話して聞いて貰える状況は、非常に問題が解きやすくてよい。普段の2倍ぐらいの能率があるように感じる。 一見二分探索に見えるのは罠だったんだよ！みたいなことを言った。 後から聞いた話によると、二分探索で十分だったらしい。思い付かなければよかった。

この時点では、4完はできそうだなみたいなことを思っていた。 わりとよい気分で、ちょっと休憩をとトイレに行ってパンを食べて戻ってくる。 Cが謎のWAで止まっているので、Fをペアプロ。しかしこちらもバグを埋める。つらい。 ここからCとFを必死のデバッグ。私はずっとFだけしていたが、Cもつらそうだった。 Fのサンプルは明らかに弱いので、テストケースを書いたら明らかな考察漏れが判明し修正。しかしなおWA。 間違ったケースを作って混乱したりもした。 仕方がないので二分探索を書いて投げてみるかということになり書いていると、先程の考察漏れの修正の修正漏れに気付く。 直したら通る(開始後4時間51分)。

残るCは、どういうアルゴリズムで書いていたのかまったく把握してなかったので、特に口を出さず。 結局通らなかった。 後からCを解いてみると特に難しくなかったが、本番で嵌ってしまうと抜けだすのは難しい。 来年に向けての対策は考えるとして、今回は、単に運が悪かったと思っている。

最終的にABFの3完。27位。 くやしいが、Fを解けたことには満足している。 来年も頑張りたい。

懇親会

IBMのとこ行ったら神戸大学の卒業生の人がいた。 googleのパズルを楽しんだ。 リクルートの人に、code festival楽しかったです、って言いに行ったら、何のコンテンツが一番良かったか聞かれたので、短縮王を推しておいた。 去年の懇親会の企業ブースは、彼らが求めているのは私なんかじゃなくてもっと強い人なんだろうなあ、という思いで見ていたが、今年は特にそのような思いはなかった。 実際に求められているかは別として、1年間でなんらかの自信が付いたのだろう。

深夜

本番で解いていなかったC問題とD問題を解いた。

3日目

エクスカーション。 cyberdyneという大学発のロボットスーツの会社と、高エネルギー加速器研究機構へ。 面白かったことには違いないが、私にはロボットや物理は分からないし、もう少し情報系の話が聞けてもよかったかもしれない。

ACM ICPC 2015 アジア地区予選 参加記

とても楽しかったです。 ありがとうございました。 来年もまたよろしくお願いします。