こんにちは。eiyaです。
12/8～12/10に開かれたACM-ICPC 2018 Asia Yokohama Regionalに参加してきました。
ICPCとは
国際大学対抗プログラミングコンテスト(International Collegiate Programming Contest)の略で、大規模な大学生(高専生)向けの競技プログラミングの大会です。
3人1チームで1台のPCを用いて、3～5時間で、6～12問の問題を解きます。
成績が良いと国内予選->アジア地区大会->世界大会と勝ち進むことが出来ます。
今回僕たちが出たAsia Yokohama Regionalは複数開かれるアジア地区予選のうちの一つです。
参考：3分でわかるICPC
参考：2017年の参加記
チーム
僕は60odnight（グッドナイト）として参加していました。
メンバーは
です。
東工大からは他にnarianZとnew_moon_with_faceが出ています。
予選
横浜大会の前のオンライン予選では13位でした。
B問題が実装難ということで予定していた問題配分を急遽変更するなど柔軟に対処出来て良い成績を収めることが出来ました。
本番1日目
練習日です。今年は午後からで、書類類を書いて自己紹介をして練習問題を解きます。
事前に配られた環境で確認してはいたのですが、CLionというエディタがステップ実行が出来るGUIデバッガ付きで感動していました。（eiyaは普段Visual Studioのデバッガに頼っているのでデバッガが使えないと辛い気持ちになる。）
A～Dまである練習問題のうち、僕はBを解きました。
本番2日目
コンテスト本番です。
コンテスト
今年はA～Kまでの11問を5時間で解きます。
始め3問のA,B,C問題は難易度順で、他はランダムな順番に並んでいます。
が、なんとABC全てバグらせました。なんと最初の正解が出たのが開始から55分後で、Aを解き終わるころには約2時間たってしまいました。
僕はC問題とB問題を解いていたのですが、単純な計算ミスや度重なる誤読の結果、いつまでたっても正答できず。その結果自分のことにかかりっきりになり、60°さんが解いているA問題が実装方針を正しく選ばないと辛い問題だというのに気が付くのがかなり遅れてしまいました。
並行してbatonさんがG問題を解き、開始2時間時点で4問正解という形になりました。
その後他のチームが解いているD,E,K,I問題を見るという方針で解いていきます。
このあたりから記憶がかなりあやふやなので時間系列がめちゃくちゃです。
一度batonさんが解こうとして失敗したD問題を、僕が解けると主張して書いていきます。
並行して読んでいたK問題ですが、昇順という条件を見落としていて「簡単すぎでは？？？？」となったので、ちょうどDをバグらせていた僕とbatonさんが代わってとりあえず書いてもらいながら誤読を探します。割とすぐに昇順と書いてあったことに気が付きました。
Kがバグったので交代してDのバグを直しました。ところがDPの値として結果の部分文字列を保存していた為、メモリをO(N^3)で使うコードが完成し、実行した結果2GBあるメモリを全て食いつぶしました。（悲しい）60°さんと相談した結果、Dは値を保存しなくても経路復元をすればよいことに気が付いたので書き直して投げてトイレに行きました。
帰ってきたらちゃんと正答の証の風船が席についていて良かったです。
しばらくするとKも正答を出すことが出来ました。
E,I問題を考察していきます。
I問題は解けなくて、E問題は僕が完全マッチング（難しい）に帰結させてしまい、悲しい気持ちになりました。何もしないよりはと言ってEを力技でねじ伏せようとしていましたが、バグが直らずコンテスト終了です。
最終結果はこんな感じです。
ICPCは解くまでにかかった時間の総和がペナルティになるので、ABC分ペナルティが凄いことになってますね...
表彰式とディナーパーティー
表彰式の前に簡単な解説があったのですが、なんとJ問題が解け得る問題だったことが判明します。
今回の個人的な反省は問題の選球眼が弱かったところですね...
僕たちは6問正解の16位でした。他のチームが解いている問題は解けたのでとりあえずは良い結果かなと思います。
東工大の他のチームは
- narianZ 7問正解の8位
- new_moon_with_face 4問正解の32位
です。
今気が付いたんですが、位,位,位ですね。
残念ながら今年は東京工業大学から世界大会に行くチームは出なさそうです。
表彰式の後ディナーパーティーがあって、他の大学の競技プログラマと話したりコミュ障をしたり企業の方と話したりしました。
感想
バグらせたのを除けば、今の僕が出来ることはやり切ったと思うのでとりあえず満足しています。
世界大会までは今の僕では届かないけど、もう少し頑張れば届き得るという手ごたえがつかめたのは大きな収穫だったと思います。
また来年も出場できるよう頑張っていきます。
