ACM-ICPC 2018 国内予選参加記

「priMe.caT*1」というチームで人生3回目の国内予選に参加しました。

2018年国内予選 | ACM-ICPC 2018 Asia Yokohama Regional

チームメンバー

ixmel先輩…主に実装担当。

T.M先輩…主に考察担当。

ぼく…テンプレ写経やサンプル図示やデバッグなどを担当。雑用係。

先輩方がM1で今年でICPC引退なので、今年限りのチームです。

国内予選まで

5月中旬ごろにチームメンバーが決まったので、そこから（部の活動も含めて）週3くらいでチーム練をはじめる。あと国内予選対策のための部内合宿を行ったりした。

練習のおかげか、国内予選1週間前にあった模擬国内予選*2では、国内予選の参加資格のあるチームの中で7位という素晴らしい成績をとれた。いえい！w

うちのチームは6完9位でした pic.twitter.com/maKpBKMFoA
— ixmel (@mel_fall524) July 1, 2018

模擬国内後はライブラリを少し追加したり去年の国内予選の後ろのほうの問題を解いたりしていた。

国内予選

大雨の影響で大学が休講&JR運休で参加が危ぶまれていたものの、3人とも大学にたどり着くことができたので、ixmel先輩の研究室で出ることに。（研究室には作業している人が何人かいて、うるさくして少し申し訳なかったです…）

コンテストが始まって、ぼくがテンプレを写経している間、先輩がABを読む。テンプレ写経が終わってすぐixmel先輩がAを書いてAC。その後Bの実装方針をixmel先輩と一緒に考えながら実装していた。T.M先輩はCとDの考察をしていた。Cが全探索でできそうだと言われたので、解法をきいて、Dの考察をしてもらう。Bの実装が終わってサンプルを試すと、半分より右側や上側で折った時にバグってることがわかったので（というか考慮してなかったので）、そこを直して提出してAC。ixmel先輩にCの解法を伝えて実装してもらう。Dは各チームの勝ち数はわかるので枝刈り全探索で解けることがわかって、T.M先輩にEFの考察をしてもらう。CはすぐACしたので、ixmel先輩にDを実装してもらう。Dの実装が終わってサンプルを試してみるとだいぶ遅いので枝刈りを強化したりする。その後提出するとAC。このとき全体4位で結構盛り上がった。

この段階でEとFの両方ともの解法がわかっていなかったので3人で考える。Eは繰り返し二乗法で二進数の足し算をやればいいのかなあという話になってixmel先輩が実装を始める。（実装だいぶ手こずっててつらそうだった。）実装が終わってサンプルを試すとサンプルがあわない。つらい。Fが1辺の長さを二分探索して下辺のy座標を決め打ちしてしゃくとりっぽくやるとできそうと思いつく。Eの考察を再びT.M先輩に任せてixmel先輩とFの実装をする。つらそう。なんとか実装を終える。サンプルをためすと合うけど遅い。計算機パワーを信じて提出することにする。Fはpcしゃんにがんばってもらう*3。T.M先輩がEの解法を思いついたのでixmel先輩が実装する。実装つらそう。実装がおわってサンプルを試すとサンプルが再びあわない。かなしいね。Fのデータセット1つめがおわりません。コンテスト時間がおわりました。（Fの計算量がやばだったことがあとで判明しました。）

結果は4完23位。（4完最速）

f:id:wk1080id:20180708164824p:plain