ICPC2017 国内予選 参加記
ゆらふなさん( @yurahuna )とらてあくん( @ratetion )と、「sparsely_populated_regions」というチーム名で参加しました。
チーム名は限界集落の英語表記*1で、口に出して読むと575っぽくなっているのがポイントです。
結果はABCDの4完 35位で、アジア地区にはなんとか進出できそうで一安心です。
国内予選以前
LiveArchiveなどの問題を使って3時間セットを5回ほど解いたり、模擬地区予選に参加したりしていました*2。また、ICPCの1週間前にはメンバー3人でDPC*3出場を兼ねた広島旅行に行って親睦を深めたりしていました(?)
コンテスト
他のNAISTチームとともに会議室を借りて出場しました。しょらーさんとめんふぃむさんが手伝いに来てくれたので、印刷物を運んでもらったりしました。以下コンテスト中の様子。
コンテスト開始直後はらてあくんとゆらふなさんがディスプレイでそれぞれA,B問題を読み、僕はテンプレートの写経。その後は印刷されたC問題が来るまで暇なのでらてあくんの横で一緒に読んでいた。解法を確認するとよさそうなので「よし任せた」と言ったあたりでC問題が届き、ひと目でめんどくさそうなオーラを感じ取る。
よく読むと制約に甘えて池のサイズの決め打ち全探索をやれば良いことがわかり紙コーディングを開始する。紙コーディングが終わった頃にはちょうどA,B問題が通っていたので交代。Bでは僕のsplit関数ライブラリが役立ったらしくて嬉しい。
Cを写経してちょっと直すとサンプルが通ったので提出してAC。3完時点で経過時間は43分だったので「おっわりといい順位かな」と思って順位表を見るとそれでも30位くらいだった。みんな早すぎる。
先にD問題に取り掛かってくれていた二人に合流すると、すでに重要な考察であるところの「min(N,M)の値は高々22、全探索とbitDPを組み合わせれば解ける」がすでに出ていた。念のため検証すると問題無さそうだったので、全探索側を僕がbitDP側をゆらふなさんという分担で実装を開始。
確か20分くらいでお互い書きあがったものの両者ともサンプルが合わない。タイプミス・初期化ミス・ループ変数ミス等々を30分ほどかけて修正してAC。この時点でも30位くらいで、流石にここから10人に抜かれることはないかなあと、とりあえず一安心していた。
らてあくんがE,F問題を読んでおいてくれたのでとりあえずE問題を聞く。なんとなく構文解析をやりたかった&なんとなく解けそう だったのでE問題に取り掛かることに決める。ゆらふなさんに考察を任せ、僕はひとまず構文解析パートを書いていた。式を全列挙して良さそうという事と列挙の方針を聞き全体の実装を開始したが、結局サンプルを通すまでには至らずコンテスト終了。
反省点
- 他のチームのコードを見ていると、C問題の池の容量を評価する部分でかなり冗長なコードを書いてしまっていました。
- Dのバグで時間をかなり浪費してしまったのが痛かったです。入力形式や変数にそれぞれの流儀があるので、2人で1つの問題を解くというのも考えものですね。
- 僕達の方針だとEの実装が結構大変だったので、E問題を後回しにしてF,Gを解く決断をすべきだったかもしれません。
全体的に実装パートが酷く結構な時間を無駄にしてしまったので、うまくやればもう1問解けたのかなあという後悔の残る結果となりました。
さいごに
ICPC国内予選は何度出ても本当に緊張するのですが、アジア地区大会進出をかけて熱くなれる大好きなコンテストです。
僕は今年で引退なので最後の国内予選でしたが、アジア地区で悔いを残さないために チーム練習・考察＆実装練習 を頑張っていきたいと思います！
