ACM-ICPC 2018 国内予選参加記 - mtsd

ACM-ICPC 2018 国内予選に参加しました。

・チーム決め

昨年度はIQ94としてhyksm, mtsd, polyominoで参加しましたが、エースhyksmが参加資格を失ってしまったので、新たなメンバーを探すところからスタート。

同期で競プロをやっていたのはkopricky, mtsd, pachicobue, polyominoの4人であったため，3人チームをどうにかして2つ作ることになりました。
（去年のJAG夏合宿はmtsd, pachicobue, polyominoで参加していました）

たまたま、伝手があったのでats君を誘うことに。新しいエースの誕生です。

色々あって、くじ引きの結果チームメンバーはats, mtsd, polyominoの3人になりました。

チーム名はランダム生成した結果、Apollopiaになりました。
それっぽい感じの名前になって幸先が良かったです。

読み方は「あぽらりるれろぴゃ」です

ICPCチーム名決まったー！ pic.twitter.com/iL9hyMAOXG
— ホハム (@soiya_ksk) 2018年6月1日

・模擬国内予選

模擬国内予選はそこそこ失敗して20位。
グダりまくってFが間に合わずかなり厳しい気持ちに。
この順位じゃ通過は明らかに無理で悲しい気持ちになりました。

・国内予選本番前

今年で最後なので結構気合を入れて臨みました。
前日は何か実装しておこうとカーリング2.0などの練習をしました（バグらせてpolyominoに呆れられました）。

当日は駒場に集まってプリンターは共有される形式なので、プリンターのための席取りが大事。高速印刷のプロ、polyominoが動きやすいような席取りをゲット。

後ろの席にはKAunter、さらに後ろの方には同期チームのboku_buecoderがいました。
今年から上位10位以内は大学制限なしで無条件通過ということで、実質10位以内が通過条件。この辺りのチームは10位以内争いにかかわってくると思っていたのでどこが行けるかなとワクワクしながら開始時間まで待っていました。

・国内予選本番

とりあえず問題を開いて、polyominoがプリンターに高速でキューを送り、急いでプリンターの元へ。
プリンターを待つ間、ats君と2人でA問題を読み、ats君がA問題を書きました。
polyominoが帰ってくる頃にはA問題をAC (4:03 1完)。
印刷のプロpolyominoにしては意外とプリントに時間がかかったなぁ～と思っていたら、polyomino曰く「絶対一番最初に印刷できたと思っていたのに、開始前からプリンター前にスタンバってる人がいて遅れた。まとめて印刷せず1枚ずつ印刷していて、マナーが悪かった。」とかなりお冠。

ここからは問題を手分けして読むことに。
とりあえず僕とpolyominoがB問題、ats君がC問題を読みました。
B問題は紙を折っていく問題で、これは普通に面倒くさそうだし、バグらせそう・・・
atc君がC問題は簡単と言っていたので，先にやってもらうことに。

サクサク書いてC問題AC (18:53 2完)。

その間にB問題を紙コーディングしていたので、とりあえず書いてみるも答えが合わず。
そうこうしていると、ats君とpolyominoからD問題は解けたという話が来たので、デバッグを印刷して、Dを先に書いてもらいました。
印刷したものをチェックしていると、配列のindexを書き間違えていることに気づいたので、いったんパソコンを戻してもらって書きなおしたらサンプルが一致。
もう出しちゃえの精神で出したらAC (38:12 3完)。
この時点で4位！かなり順調でした。ムーブとしてもかなり連携が取れていました。

D問題もすらすら進んでAC（57:57 4完）。
この時点で2位！！かなり順調（以下略）。

次はどれをやろうという話で、僕はE問題、ats君がF問題、polyominoは後の問題を読んでいました。
E問題（浮動小数点数）はとにかく問題文が長く何を言いたいのかが全然読み取れず、大苦戦。ずっとオーバフローするのでは？と頭を抱えて、clarを飛ばそうか、ほかの問題を解こうかという話をpolyominoとしていました。
ここでかなり詰まって、ずるずると順位が落ちて10位圏外に。問題が理解できていなくて解けないという感じだったのでかなり険しい気持ちでした。

そうこうしていると、ats君からはF問題は多分解けたけど計算量がマズそうと伝えられました。polyominoが「計算量は国内予選は気にしなくていいよ」とats君に伝えて、斜交座標系から座標変換の式を直す担当であるところの僕に「式を書いて」という指令が（それくらい出来るっしょと思いながら式を書いてpolyominoに渡しました）。

F問題をats君とpolyominoで書いている間に、ようやくE問題の題意を把握。
与えられる桁数を勘違いしていました。これはシミュレーションするだけだから行けると確信。
Fよりは流石に簡単だと思うから書いていい？と伝えて、とりあえず一通り書きました。しかし、なぜかサンプルが合わなかったのでパソコンを取り上げられました。デバッグ出力して印刷キューをpolyominoへ。

F問題を書いてもらっている間に、E問題で更新する変数の間違いに気づき、これを直せば行けると宣言。パソコンを取り戻して直したらサンプルが合う！
E問題 AC (2:26:10 5完)
このタイミングでの順位は8位。上位に3チーム東大がいたので、このまま10位から出ると落ちてしまうことが確定してしまうギリギリの状況に。

残りの時間的にF問題が解けるかどうかで終わりだったので、G問題を考えつつ、とにかくats君がF問題を書いているのを見守ることに。
すると、EのACからそんなに立たないうちにF問題のサンプルが大体あったけど微妙に合わないという報告が。
サンプルを図に書いてみたら、どうやら三角形の向きを両方向見ていないか？という話になり、それを直してもらったところ、サンプルが合う！
実行時間が少しかかるもF問題 AC (2:36:46 6完)
ats君凄い・・・

この時点で5位だったのでもう安泰だろうと喜びながら、とりあえずGをガチャガチャ書いてみましたが、普通に書けず終了しました。

結果としては5位（大学内4位）で国内予選突破でした！