ICPC2019国内予選 参加記
ICPC国内予選にチームchoKOdaiで参加しました。
3完(7897)で全体85位、学内3位でした。
これは普通だと予選突破できないのですが、慶應義塾大学は今年の†ホスト校†だったので、チーム選抜ルールの手順2が適用されて予選突破になりました。
チームについて
去年のICPCと同じメンバーで、ziroppeくんとspiderさんと僕の三人のチームです。atcoderの色は参加時点では緑緑水でした。
チーム名について
去年のICPCアジア横浜大会中継動画(ACM-ICPC 2018 アジア地区横浜大会 中継 - YouTube)の4:52:40頃にchokudaiさんが慶應からもchokudaiという名前のチームが出てきたらいいのにとおっしゃっていたのを聞いて、去年の冬くらいから温めていた名前です。チーム名決めのときに案として出してみたら概ね好評だったので決まりました。
(ところで、chokudaiさん本人に気づいて応援していただけました。わーい！)
ICPCはとりあえずこのチームを応援します pic.twitter.com/l5P0aveGjJ
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年6月28日
作戦
目的を国内予選突破に定め、そのための目標として、3完早解き、そして4問目をなんとか解く、ということを掲げました。ともかく3つを素早く通すためにチームで早解きの練習を何回か繰り返しました。spiderさんは忙しくて練習に合流できないこともあったので、僕とziroppeくんで早解きの部分をやって後ろの問題をspiderさんに見てもらうという形がだんだん固まっていきました。
本番前のいろいろ
模擬国内出ました。ABC3完で、Dのレーベンシュタイン解きたかったです。
キーボードの使い分けが禁止なことに気づきました。ziroppeくんがUSキーボードで他二人がJISだったので困りました。色々相談した結果、JISを使うことになり、ziroppeくんはJISでプログラミングをする練習をしてくれました。ありがたい。
本番前日
学内で模擬コンテストがありました。本番と同じ会場でプリンタなどの機械の使い方含めてリハーサルをしました。
問題は上のリンクで、これのC、Unordered Operators(構文解析の問題)が解けなかったので22時くらいまで学内に残ってチームで解いていました。その後なんとか二通りの方法でACできたので、みんなでハマトラに行ってラーメンを食べ、帰り際、駅前で本番の流れや、残りの時間でできることを話し合いました。今までチームで書いたプログラムで使えそうなのを印刷しておこうとか。いろいろ話していると流石に遅くなったので解散。家に帰ると0時くらいで、そこからネットを漁って使えそうなライブラリを印刷する作業をしましたが、途中で前日の徹夜がたたって眠くなって、寝てしまいました。
本番当日
以下、当日の終了後、深夜3時過ぎに書きなぐった駄文をそのままコピペします。
目が覚めたら8時で、朝ごはんもそこそこに急いで大学に向かった。1,2限は化学の実験で、銅イオンの溶液を振っていた。昼食を取った後に矢上キャンパスに向かって、ziroppeくんと合流。互いに前日夜に用意してきたライブラリについて互いに報告しあって、そのあとリハーサルの問題を解く。4問目の幾何はリハーサルにしては難しいなと思いながらも、方針は立って、あとはziroppeくんの持ってきた螺旋本の幾何の部分を使えばなんとかなりそうだなという感じで、その頃には4限の授業が始まる時刻が迫っていたので、別れて授業へ。ziroppeくんは授業がないらしくてメディアへC++の辞書的なのを借りに行ってくれていた。4限はプログラミングの授業。演習やるだけの日だったので、課題として与えられた4問を適当に40分くらいで解いて早退。gcdとlcmを求めろみたいなのがあったりして、競プロやっててよかったと思った。
会場に向かうと、コンピュータの設定をやったり、他のチームの子達と雑談したり幾何についてziroppeくんと話したりしながらソワソワと過ごした。16時過ぎくらいにはspiderさんもやってきて、チーム全員が揃った。再びライブラリについて報告したり、初動の確認などをした。問題の印刷について、1問ずつ印刷するのはコンピュータを占有しすぎると考えて、全部まとまったページの方を印刷することにした。ziroppeくんがホッチキスを持ってきていて、spiderさんがハサミを持っていたので、それで問題ごとに切ってまとめようという話をした。色々そういう作業をしていると、3秒前くらいに「あ、はじまるね」みたいな感じでぬるっと本番が開始した。
まずは、ziroppeくんに印刷の処理をしてもらい、spiderさんにプリンタに向かってもらう。すぐにパソコンでA問題を見る。やるだけ。ziroppeくんに横で見てもらいながらプログラムを書き始める。サンプルが通る。提出する。AC。spiderさんも帰ってきていて、問題を切ってホッチキスしてもらって、そのままC以降の問題を見てもらっていた。
僕とziroppeくんでBを見る。マンハッタン距離を愚直に見ていけば良さそう。とりあえず書き始める。ある文字に対して座標を対応させれば良さそう。map使えばいいか。あれ？ サンプル見ると、同じ文字がいっぱい埋まってる？ いや、アンダーバーは文字でない場所。でも、複数の場所に文字があったら、めんどくさそうだぞ。BFSか？ でもB問題なら同一文字は複数ないという条件がありそう。二人で問題文を睨む。問題文中に記述があって、その場合は考えなくて良いとわかったので、プログラムを完成させる。サンプルが通る。提出する。通る。やったー。ここまで20分。
spiderさんに他の問題の大体の感じを聞く。Cは行けそうということなので、コンピュータの前を譲って、spiderさんがプログラムを書き始める。僕が横でそれを見る。ziroppeくんはD問題を見に行く。とりあえずCは、dfsで(3^10)通りの手持ちの分銅でできる重さは求められるねーとspiderさんが実装していく。けれど、そこから先が詰まる。悩む。
横でziroppeくんがDについて考察しているのが気になって、内容を聞きにいく。聞いてちょっと考えて、左から見ていけば行けそうと思って「行けます」とspiderさんに報告。まだCが詰まっていたようなので、代わってもらってDを書き始める。ちょっと迷いつつもziroppeくんに見てもらいながら書き終わる。サンプルを試す。値が違います。え？ コードを見るけどどこも間違ってなさそう。悩む。
「Cわかった」と横から聞こえてきたので、Dのコードを印刷して、spiderさんにコンピュータを渡す。ziroppeくんとspiderさんでCの実装を始める。僕はちょっと離れて印刷したコードを見ながらうんうん唸る。5分くらい見て、iと0を書き間違えていることに気づく。コンピュータ貸してもらって、書き換えてコンパイル。実行。値が違います。はい、もう一度考えます。
コンピュータをspiderさんたちに返す。僕はさらにうんうん唸る。バグじゃなくて何か間違ってるかもと思って、問題文にもう一度目を通す。あ……誤読。全然違う問題を考えていたことに気づく。一回の操作でできる行為を、『隣接する一連のカウンタを押す』ではなく、『隣接する3つのカウンタを押す』という感じに間違えていた。辛い。でも、気づけてよかったと思いながら、正しい問題について考える。え、これ難しい。
ちょっとCの様子を見にいくとバグっているみたい。とりあえずCを通さねばと思い、方針を教えてもらう。コードの内容を教えてもらいつつ考える。みんなでワイワイとやっているとみるみるバグが洗い出されていった。(この辺り、すごくチーム戦で楽しかった)サンプル通る。みんなで提出。通る。やったーと盛り上がる。ここまで大体1時間50分。
残りの問題を机に並べる。「どれいきましょう？」と考える。順位表を見てみると、D,Eあたりが通ってる。Eはこれやるだけだよなー、と。でも、E以降通しているチームは基本的にDは通してる。ならDをやるべきだろうとなって、みんなで考え始める。二人づつで話したり、一人で考えたり、蟻本開いてみたり、順位表見て学内でD解けてる人まだいないねと確認したり、みんなで顔を突き合わせたりしながら色々なことを考える。AtCoderでこんな感じのあったなーとか(https://atcoder.jp/contests/abc116/tasks/abc116_c)。DPじゃない？ (でもなにを[i][j]に入れます？ となってた)とか。でも、全然解けそうにないまま、残り40分くらいになってしまう。
方針を転換して僕はFに行く。パズルっぽい感じで、あと僕の好きなグラフなので、閃けば実装まで行けそうと思った。spiderさんはDを考え続けることに。ちょっと経ってコンピュータがずっと空いてもったいないので、ziroppeくんがEを実装することに。Eは言われた通り全列挙するだけなのは初期からわかっていたけれど、実装がすごく重そう。さらにしばらくして、ここから考察して実装まで持っていくのは無理そうと結論づけて、D,Fから撤退し、Eに三人のリソースを全て使うことに。けれど、あまりに重くて、結局時間切れ。
あっという間で密度の濃い三時間に「お疲れ様」と虚脱していると、他のチームの人から「予選通過じゃない？」と指摘される。
学内3位だというのはわかってて、でも通るのか？ と思いながら見てみると、†ホスト校†の力でなんとか通りそうとわかる。浮かれながら先生のお疲れ様の挨拶を聞いて、学内の記念撮影を終えると、手計算で予選通過かどうかを確かめてみることに。東大強いなーと上から順に順位表を見ていき、通過を確信する。すっごい浮かれる。ウキウキしたまま、チームメイトのみんなで夕飯を食べにいく。せっかくだからステーキ食べに行こうということになってステーキ食べた。
チームの二人と pic.twitter.com/VozyJk4toJ
— ろい (@Roy_R_) 2019年7月12日
美味しくいただきながら色々なことを話した。店を出ると、秋のアジア予選に向けて精進頑張りましょうと、鼓舞しあって別れた。空を見ると月の光冠が綺麗に見えて、エモい気持ちになりながら帰宅した。
反省や感想や意気込みとか
目標にしていた予選突破を果たせてよかったです。また、慶應の次のチームとの差がほんのわずかなペナ差だったので、ABあたりの早解きの練習が生きた感じがして、それもいい感じです。
ただ、Dは通せてもよかったかなーと思うし、Eの実装をもっと早く始める判断をしていれば行けたのではというのも考えなくはないです。
しかし何はともあれ、一緒に戦ってくれたチームメイトに感謝を。で、秋もあるということなのでこれからも一緒に頑張っていきましょう！
ところで、個人的にアジア予選の本番までには青になっていたいです。
