ICPC 2022 国内予選 (2022/07/08)

登場人物

  • torisasami

チームのリーダー的存在。先生。tokusakurai とは前期教養時代のクラスメイト*1。研究室振り分けで第 14 希望に配属され、最近は研究室での話をよく聞く。卒業に向けて頑張ってほしい。競プロでは初手の考察の筋の良さに定評があり、高難易度問題をあっさり処理してしまうこともしばしば。

  • sapphire15

torisasami と ICPC 出たいねという話をしていたところに駆けつけて来た救世主。サファ先。チームの良心である。いわゆる「パソコン」やコンピュータサイエンスにも造詣が深く、いつも助けられている。競プロでは主に構築問題や AGC などの adhoc 要素の多い問題を得意としている。

  • tokusakurai

筆者。チームの中では知識枠(?)。寒色時代に torisasami に手取り足取り競プロを教えてもらったが、最近では口癖までうつってしまっている。チーム戦では他の 2 人が途中まで考察して詰まっている問題を寄せ切って美味しいところだけかっさらうハイエナプレイを得意としている。

チーム名

チーム名決めをしているときに「おいしい庄内空港」と言ったら 2 人にウケが良かったので delicious airport で "DELIAIR" に決定。他にも全員が 9,10 月の秋生まれであることから "Fall Guys" という案もあったが、ありきたりすぎるということで却下された。去年の PG BATTLE で 2 位だったんですが、結果発表のときに "おいしい庄内空港" を見て某社長が「何これ」みたいに言ってたのを許してません。

本番まで

(普段デスクトップでやっているのであまり行く気はなかったが)一週間前くらいに対面でやるかを打診したところ sapphire15 が部屋を取ってくれて急遽行くことに。そのためにノート PC に json をそのままコピペするなど付け焼刃の環境構築をして準備した*2。当日は 13 時すぎに家を出て駒場に向かった。電車の乗り継ぎがあまりにもスムーズだったのでラッキーだなあと思いつつ 14 時前に駒場に着くと sapphire15 が既に着いていて書籍部の前で合流した。もう 2 年以上来ていなかった駒場に懐かしさを感じる、ということはなかった。その後書籍部で数学書を見たりした後借りていた部屋へ向かい、noimi が院試の出願の締め切りを勘違いしていないかという話題で sapphire15 と盛り上がっていた。時刻はまもなく 15 時になっていたが 2 時間前に準備をしていたはずの torisasami がまだ来ない。心配になって LINE をするもこれから電車に乗るところだったようで、「まじめにやって」*3と送った。そうこうしている間に torisasami が到着し、学生選手権のオンサイトに通るかなどの雑談をしていたら気づけば 10 分前になっていた。

作戦

学内での競争が激化している中で、全体 10 位に入らずして国内予選を突破するのはほぼ不可能だろうということはわかっていた。昨年一昨年の結果を見るに 6 完できればおそらく通るという感触はあったので、基本的にはそこが目標になると思っていた。完数を増やす上では早めに後ろの方の問題にも目を通しうまく分担する必要があるので、 torisasami に先に C 以降をみてもらうことにした*4。結局開始時の作戦は以下のようになった。

  • sapphire15 がサクッと A を通す
  • tokusakurai がサクッと B を通す
  • torisasami が C 以降の問題を見て、やりやすそうな問題をやる

本番

16:30:00 開始

実は本番開始 1 分前頃から急にトイレに行きたくなっていた。本当は本番前に行こうと思っていたのだが、部屋を出たところでちょうど torisasami に鉢合わせたことで行くのを忘れていたのだった。例年通りコドフォったらその隙に行こうなどという甘い考えをしていたのだが、その期待は裏切られまさかの定刻スタートとなった。sapphire15 から A が解けるという声が上がり、torisasami からも今年の C は簡単だという声が上がる。その一方で自分は B 問題の読解に苦戦していた。

16:34:37 A 問題 AC (sapphire15)

ようやく B 問題も読めてきて、1 周すれば 1 枚は減る的なことが問題文に書いてあったので愚直にシミュレーションすれば良いっぽいことがわかり、実装に着手する。saphire15 は D,E を見比べて、D が torisasami の得意分野である数え上げということで E に向かうことになった*5

16:37:53 C 問題 AC (torisasami)

torisasami が C を爆速で通し、なんと暫定首位に躍り出る。後から見れば、C 問題で FA を取った Aobayama_dropout と 13 秒差でかなり惜しかったようだった。torisasami は sapphire15 に託された D に向かう。その後数分して何とか B の実装が終わるが、サンプルで Segmentation Fault が取れず、早くも追い込まれていた。デバッグの仕方を sapphire15 に教えてもらうも gdb が入っていないことを怒られ、結局コードを共有してデバッグをしてもらった(本当にありがとう)。無事に mod を取り忘れてる箇所があることが発覚し、事なきを得る。

16:53:27 B 問題 AC (tokusakurai)

2 人に次何をやったらいいかを聞くと、sapphire15 から E のチェッカーを書いて欲しいという依頼があったので、問題を読んでチェッカーを書き共有する。その後 D 問題に取り組む torisasami から「長さ N の数列に含まれる長さ 1,\dots,K の増加部分列の個数の数え上げが高速にできるか?」と聞かれる。O(NK\log N) より速い解法がわからなかったので、どうしてその問題に帰着されるのかを聞いてみたところ帰着される問題が別の問題であることが発覚し、解決した。

17:28:36 D 問題 AC (torisasami)

sapphire15 が E で少し苦戦してる感じだったので話を聞くことに。F 問題が簡単だった場合のリスクが大きいということで torisasami にはひとまず F に行ってもらう。このあたりで torisasami が 5 完早解きできればかなりアツいという*6。E の今考えている解法を聞いたところ、どうやら乱択を考えているようだった。黒板を使ってとりあえず確定するところを埋めてみたいな実験をしてたところ、どうやら解法の整理がついたらしく、ひとまずここは任せることにした(正直なところ、解法が非決定的なところもあってかなり不安視していた)。F に取り組む torisasami からも 3 乗 から落ちないという相談を受けるが、問題をよく見ると構文木のノード数は 333 以下なので 3 乗でも間に合うと主張し、自分が構文木構築パートを実装し、メインパートを torisasami に実装してもらうことに。苦戦しながらもしばらく実装していると sapphire15 から E の勝利宣言が出る。

18:16:52 E 問題 AC (sapphire15)

ありがとうサファ先。サファ先神。信じ切れなくてごめん。この時点で暫定 5 位でノーペナでタイムも良く、さらに F 問題も解けそうということで国内予選突破にかなり近づいていることを感じていた。なんとか完成した構文解析パートを torisasami に渡し、sapphire15 とH 問題を考える。永続木がどうこうと言われるが、気分が高まっていることもあり何のことだか理解できなかった。その間に torisasami が実装を終えてテストケースの実行に入るが数分待っても終わらないという。コードを共有してもらって落ち着いて見てみると、再帰でメモ化をしていないことがわかり、それを指摘すると実行が終わるようになる。これで一件落着かと思いきや、今度は WA が出る。出力を見てみると空文字列になっているところがあり、文字数計算パートのミスも発覚する。*7

19:00:00 順位表凍結*8

現状 6 位だが、確実に通すためにはもう 1 完が欲しい。その後も F を提出しては WA を繰り返し、3 ペナまで行ってかなり焦りはあった。そこでとりあえずサンプルを自分で作ることを提案し、実際に ?(?(?(?(a)a))cba) で cb が返ってくることがわかり、それが直るまで色々修正していると今度こそ通る。

19:18:43 F 問題 AC (torisasami)

気が付けば辺りはすっかり暗くなっていた。最後に 10 分くらいあったので GH を考えたり、順位表を見て抜かれそうなチームがあるかを考える。幸い E までがハイペースだったので 6 完で抜かれうるチームがほとんどなかったこともあり、この時点では全員いけると思っていたと思う。

19:30:00 終了

3 人で揃って torisasami のパソコンの前に集まり、緊張しながら F5 を押す。

終結

終結果は 6 完 (25808) で総合 7 位、学内 4 位でした!

最終順位表抜粋

最後の F 問題の AC が順位に影響しなったのは少し残念なところもありますが、5 完以下に終わる強豪チームも結構いるので 6 完したという結果はとても良かったと思います。

終了後

torisasami の鍵垢を覗くと、どうやら noimi や nok0 さんなどと打ち上げをしようとしているらしい。自分は飲めないし noimi に何されるかわからないしいいかなという感じだった。その後も torisasami のアカウントで勝手にツイートして怒られたりするなどしてグダグダしてるといつの間にか 20:30 を過ぎていた。他の部屋(競プロ関係ない)に遊びに行っていた sapphire15 も帰ってきて、一週間くらい前から行きたいと言っていたサイゼに行くことになった。サイゼで豪遊*9した後はもう 23 時前になっていて、自分はもう疲れたし帰るかといって 2 人と別れたが、2 人はその後 noimi らの飲み会に行ったらしい。みんな楽しかったと言ってるし、せっかくだからちょっと行ってみた方が良かったかもしれない。学内 ICPC 参加者の方はまた地区予選のときよろしくお願いします。

終わりに

チームメイトの torisasami と sapphire15、コーチの enjapma さん、ICPC 運営陣の方々、一緒に戦った他チームの参加者の方々など、みなさんありがとうございました。特に個人としては 1 問しか通してないのでチームメイトの 2 人には迷惑かけたと思います。厳しい戦いでしたが何とか結果を残せて本当に良かったです。

*1:実は noimi も同じクラス

*2:まじめにやって

*3:torisasami 語録の 1 つ

*4:昨年は C からかなり険しかった

*5:これがなかなか好判断だった

*6:終わってみればこれは正確な見立てだった

*7:このあたりの話は https://twitter.com/torisasami4/status/1545668395433349120 が詳しい

*8:実際は順位表凍結はなかったらしい。え?

*9:これで 2000 円かからないから安いものです