prime's diary

そすうの日々を垂れ流しちゃうやつだよ

ICPC 2017 Tsukuba Asia Regional 参加記

競技プログラミング

2017/12/16-18に行われたICPC 2017 Tsukuba Asia RegionalにチームPrimeDragonとしてamano, nikuttoと参加してきました。

コンテスト前日まで

15日

生活リズム的に16日の朝早くから出られそうにないので徹夜することにした。Redbull飲んで徹夜する。

16日

徹夜のおかげで無事新幹線に乗れる。

初つくばエクスプレス乗車。（京都大阪間に比べると）値段高いですね…

中学校の知人とばったり出会う。偶然ではなくてICPCに出てるらしい。

JAXA見学。管制システムかっこいい…

リハーサルではコンテスト時の段取り（誰が最初にテンプレートとか書くのかとか）を確認、コンテストシステムに慣れる。 プログラムが実行されるサーバーと手元の速度差を確認。（ほとんど違いはなかった） 印刷やClarを投げる練習もした。

筑波学院大学でWelcome Party。 京大の伝統（？）でチーム紹介は短めに。 料理がだいたい茶色系だったのはなんでだろう…おいしかったけど

歩いて会場から宿まで歩いた。さむい。

ちょうどARCがあったので参加。3完できたのでまあまあ良い結果。

寝る。

コンテスト当日(17日)

朝

緊張してあんまり寝られなかったけどおかげで寝坊せず起きられた。

朝食はつくばカピオの近くのCASAってところで食べた。natsugiriさんとかがいた。

コンテスト本番

記憶が曖昧なところがあるので時系列おかしいかも知れないです。

コンテスト開始。

まず、Xmodmapの設定（Caps LockをCtrlにする）、.vimrcやテンプレートを書く。 その間にAやBを読んでもらう。

書けた時点でAが読めて解法もわかったらしいので教えてもらって書く。AC。 Bが解けるらしいので交代する。

Cを読む。特に難しいところはなさそう。Bを解いている間に実装を詰める。 BがACしたので交代してCの実装をする。サンプルが通らなくて焦るが、インデックスがずれているだけだった。 2個もずれててこんなずれるはずないだろと思っていたが、サンプルは通るので投げる。AC。

この時点で10位ぐらいだった気がする。出だしとしてはいい感じ。

ここからは難易度順に並んでいないので簡単そうな問題をさがす。 Fが始点と終点からDijkstraすれば良さそうなので解けると主張するが、それだけだと経路が長くなるか判定できないと言われてたしかにとなる もうちょっと考えると最短経路上の辺で作った部分グラフ(DAGになる)で橋になっているかがわかれば良いことがわかる。 コードを書いてサンプルも通ったので投げる。WA。コード印刷するが原因わからず。

その間にGで実装軽そうな方針が立ったので書いてもらう。AC。

まだわからないので他の問題を考えていた。Iが解けるらしいので書いてもらう。AC。

ようやくFで橋の判定アルゴリズムが間違っていたことに気づき（DAGという条件で軽く書けると思っていたが、嘘解法だった）、ライブラリの橋検出を写す。AC。

この時点で5位くらいだったかな？かなり良い順位。このまま比較的解いている人の多いEを通せば良さそう。

しかし、EでDP解（これが正解）ではなく貪欲法解をずっと考察していていくつも嘘解法を作ってはだめとなっていた。

結局Eは通せずにコンテスト終了。

コンテスト後

解説&順位発表&表彰。D実装つらそう…こんなんコンテスト中に通せる気がしない… 結果は6完で7位。

夕食&企業ブース見学。料理うまい。前日に比べて彩りもあってよかった。 企業ブースを一通り回る。 レコチョクのパズルを解いて景品（モバブ、アメなど）をもらう。このことが後々生死を分かつことになる。 あとドワンゴのWA投げでトランプをもらった。

企業賞みたいなのでレコチョクからワイヤレスイヤホンをもらう。結構良いやつっぽい。

E通してればWF行けたんでは？とか一応まだWFの可能性ありそう、とかのコメントももらった。まさかWFの可能性がある順位取れると思ってなかったので嬉しいが、余計Eを解けなかったことが辛くなる。

昨日と同じく歩いて宿に帰る。つくばカピオからは近い。

この日はなかなか眠れなかったのでオセロでモンテカルロ木探索を実装した。合法手生成でバグってうまく動かなかった。

ホテルの自販機でDrPepperが売っていたので人生で初めて飲む。謎の味がした。 よく考えたら寝れなくて困ってるのにカフェイン入り飲料を飲むのは間違っていた。

結局朝6時頃に就寝。

コンテスト翌日(18日)

企業見学のためつくばから東京に移動しようとするが、つくばエクスプレスが30分ぐらい遅れて遅刻する。

企業見学前半はLINE。以前ISUCONで行ったことがあるが、当時は渋谷にあったので新しい新宿のオフィスに来るのは初めて。 窓からの眺めが良かった。あと叙々苑の焼肉弁当が美味しかった。

企業見学後半はPFN。ICPC/JOI出身者がすごく多いらしい。ロボットの制御もやっていたのは知らなかった。

解散。このあとせっかく東京に着たのでオフ会して終電で帰った。途中で持ってきていたモバブの充電が切れたが、レコチョクからもらったモバブのおかげで生きながらえた。

感想

E通したかった…