ICPC2019国内予選 参加記

　皆さんこんにちは、おきもちです。2019年7月12日(金)に行われたICPC2019国内予選の参加記です。やや長いです。

結果

チームokimochiは全体4位で、無事アジア地区予選横浜大会に出場できることになった。やったね！

f:id:sigma1113:20190713110852p:plain
5完内1位でした、全体的に早かった

メンバー

  • risujiroh:なんかいろんなことを知っている。ICPC的には幾何に強いのが特長(模擬国内予選では幾何を通してくれた)。国内予選時点ではcodeforces赤だったが...。
  • idsigma:上の2人には実力は劣るのでAOJ-ICPCの400点くらいまでをできるだけ埋めて前半の問題で詰まらないようにしていた。練習では最短距離系やグリッドでなんかやるのをよくやっていた気がする。冗談で冷えたらおきもちとか言ってたらチーム名になった。

　東大B4のトップ層(ツートップ？)の2人と駒場に幽閉されたM1のチーム。3月くらいにチームを組みませんかと言われたのだが、まさかこの2人と組めるとは思っていなかったのでかなり嬉しかった。「アジア連れてってもらうか～w」と思いつつ、実力は劣るのでなんとか足を引っ張らないようについていきたいという焦りもあった。
　3月のRUPCから何回かチーム練をしてきたが、チームで総合するとそれなりにバランスが取れていて、それなりにICPC力のあるチームだと思う。分担もうまくいくようになって、チーム力が上がってきているのも感じていた。模擬国内予選がかなりうまくいって5位だったので、十分チャンスはあるねという印象だった。

当日の様子

開始前

　13:00くらいに先に会場に来て適当に何問か解く。その後risujirohが来て、kort0nを待つ。彼にPCとプリンターを持ってきてもらうことになっており、雨だったので傘を差しに駅まで迎えに行く。ところで

f:id:sigma1113:20190713112741p:plain
各駅停車に乗らないと駒場に着けない
　全員揃ったのでとりあえず準備を始める。プリンターくんをPCに接続しようとするが、プリンターくんが大学のWi-Fiを検知してくれなかった。よく考えたら市販のプリンターがそういうWi-Fiを検知しくれるわけなくないんですよね...。
　仕方がないので生協に有線を買いに行く。戻ってきてプリンターくんに接続するが、PCが認識してくれない。よく考えたらこういうのはPCにドライバーを入れる必要があるのでいろいろ探して入れる。ついに接続がうまくいき、「よかった～」とか言いながら試しにリハーサルの問題文を印刷しようとて出てきたのがこれ。
f:id:sigma1113:20190713113218j:plain
は？


「??????」じゃないんですよ、「??????」なのはこっちなんですが...。

完全におきもちになってしまった。確かにチーム名はokimochiだけどこんなところでおきもちになるとは思っていなかった。必死でググりながらコマンドプロンプトでなんかするとかを試していたが、まともな状態に至らず時間もないことから用意したプリンターくんの使用を諦める。かなしい。

仕方がないので会場の印刷機を使うことにしたのだが、手段を選ばないので、印刷機の一番近くのスペースに陣取った。一応席は割り当てられていたのだが、後ろのスペースも使ってよいとのことだったのでそうした。catsatmatと背中合わせだった。

f:id:sigma1113:20190713140309p:plain
2分くらいで書いた会場の本質情報
　その後なぜかPC上のICPC用のアカウントからkort0nのメインのアカウントのファイルが参照できることに気付いたので(ルール違反)、また必死でググりながらなんとか解決する。chmodとかいうコマンドを使ったんですが、慶應のチームでchmodなんとかみたいなチームがあるのを後で見つけて笑ってた。その後なんとか監督から競技開始の許可をもらえた。競技開始10分前だった。

コンテスト中

　まずkort0nが一瞬で問題文をpdfでUSBに保存し(駒場会場では印刷用途に限りUSBの使用が許可されていた)、すぐさまrisujirohに受け渡す(この間20秒なかったと思う)。この流れがあまりにスムーズすぎて開始早々面白かった。kort0n曰くこの流れをシミュレーションしていたらしい。
　Aをkort0nがすぐに通しFA。それと同じくらいにBの問題文を理解し、bfsするのか～と思いながら実装に入る。実装が重いと考えていたのだが、よく考えると各文字の位置を持てばマンハッタン距離で終わりということに気付きあぶね～と思いながら実装を終える。サンプルが合ったので出すと通る。沼にハマる前に気付けてよかった～。
　Dをkort0nが解けたというので実装してもらうが嘘だったので考え直してもらう。コードを印刷しに行くと言ってからなかなか帰ってこないなと思っていたのだが、テストケースも印刷していたらしく大量の紙を持って帰ってきた。なんやねん。
　実装を紙で詰めていたrisujirohがCを通す。Dも正しい解法がわかったらしく書いてもらう。その間にE以降を読む。Eは問題を読んでこれはkort0nの担当ですねとなる。Fはグラフで面白そうだけど全く分からん。Gはやりたくない。Hは問題文を理解するのもつらくて捨てっぽい。チームとしては幾何はそれなりに戦えるはずなのだが、これは無理そうですねという気持ちになった。
　Dが通ったのでrisujirohがなんとなくの方針を伝えてEをkort0nに投げる。この時点で2位だったのでEでハマらなければ大丈夫そうみたいな気持ちはあった。risujirohとFを考え始めるが、何もわからない。「FはFlowのF」ということわざがあるが、全域木でFlowなんて聞いたことがない。40分くらい2人で唸っているとkort0nがサンプルが合ったと言い出したので実行を始める。5分くらいで実行が終わって投げるとケース1が通る(ここで叫びそうになった)。サンプル2も投げると通り5完。kort0nの実装力にちょっと引いてしまった。
　かなり安心したが気を抜かずにFを考える。いろいろ3人で言い合いながら貪欲を立てたりするがサンプルに打ち砕かれる。線型代数的なアプローチも試していたのだが全然うまくいかない。実験コードはバグる。そうこうしているうちに残り10分となり、この時点で3位だったので通過を確信する。順位表を見ながら雑談をしておしまい、と思ったら突然Heno Wolrdに抜かれてさすがだなあと思った。終わった後は通過の喜びを分かち合った。

　終了後satashunからFの解法を聞く。綺麗でかなり感動したのだが、的外れなことばかりを考えていて悔しかった。こういう問題が解けるようになりたいね。
　監督の先生に挨拶しに行く(僕は元々お世話になっていたので、他の2人の紹介という感じ)。kort0nは存在が認知されていた。自腹で海外大会行ってもいいよとは言われたけどどうしようかなあ(思い出づくりになりそう)。

打ち上げ

　駒場キャンパスの近くにはOaksという定食屋があるのでそこに入った。そうしたら次々とICPCのチームが入ってきて実質ICPC打ち上げになった。他チームのトークがかなり面白かった。Gの考察が終わっていたチームがあったので聞いた。まあ考察内容的には解けてもおかしくないくらいだとは思ったけど、実装に2億時間かかりそうだった。
　ところでこれは日経コン懇親会のときも思ったのですが、risujirohはワイングラスが似合う。

まとめ

　自分のした仕事はわずかなものだったけど、横浜大会に行けることになって素直に嬉しい。このチームで5時間セットを戦えるということも嬉しい。5時間ともなると一人ひとりのやるべきことも増えてくるはずで、力をつけていきたいなあと思った。
　チームメイトの2人には本当に感謝しています。もう数か月よろしくお願いします。また、他の横浜大会に出場されるチームの方とお会いできるのを楽しみにしています。

ところで

　研究しないと...。