ICPC 2024 国内予選参加記

ICPC 2024 に参加したので、参加記を書きます。

自分は東大からチーム mitatreaf で出場して、全体 19 位（学内 6 位）で Yokohama 出場はできませんでした。

ICPC 国内 mitatreaf(Mitarushi + atree + leafirby) で出てました　横浜には行けず……

— atree (@atree4728) July 5, 2024

チーム決め

同級生に競技プログラマはたくさんいて、誰かとは組めるだろうと高をくくっていたところ、いつのまにかみんなチームを組んでいた。焦って鍵垢で誰か組んでほしいです！とツイートしたところ、Mitarushi さんに声をかけていただき、その勢いで leafirby さんも加わることになった。チームメンバーはこんな感じ：

• Mitarushi (B2)
  • mitatreaf の mita 担当。黄色で、チームの中では一番強い。非純粋培養筆頭格。
• atree (B1、自分)
  • mitatreaf の atr 担当。青色だが、受験でモロモロの勘が鈍っている。
• leafirby (B1)
  • mitatreaf の (r)eaf 担当。水色で最後に ABC に出たのは二年前らしいが、ブランクを感じさせない実力があると思われて、少なくとも自分よりは強そう。

模擬国内の一週間前に初めて顔を合わせて（といっても初対面だったのは自分と Mitarushi さんの組み合わせだけではあったが）チーム練をした。国内予選の 2021-2023 を解いたが、どれも冷え気味ではあった。

模擬国内

国内予選の一週間前に JAG の方々が模擬セットでコンテストを開いてくれる。leafirby さんはサークルの用があるそうで、自分と Mitarushi さんの二人で出た。14 時からの開催だったが、リハーサルシステムで実験したりして適当に家を出た結果 14:00 駒場東大前着になってしまい、Discord で全力謝罪をしながらキャンパスを走った。

14:00 に駒場着　Give_me_sociability……

— atree (@atree4728) June 29, 2024

土曜日だったため手頃な場所が見つからず Mitarushi さんと立ち往生していたようで、少し遅れて食堂からコンテストに参加することした。やっとのことで PC を開いてみるとコンテストサイトが落ちている。ネットワーク周りの不具合でコンテストがこどふぉっているようで開始が 30 分延期され、遅刻は帳消しになったようだ（なっていません）。食堂に長居できないことも判明したのでキャンパスを徘徊し、学生会館で出ることにした。学生会館に着くと同じコンテストに出る競技プログラマ集団を発見し、そのあたりと少し喋った。

時系列はあまり覚えていないが、なんとなくの雰囲気でコンテストの様子を記しておく。コンテストが開始してすぐに自分が A を通した。A, B, C が簡単枠になるだろうと踏んでいたため Mitarushi さんは D 以降を読んでいたが、D がすぐにわかったようで、自分が B, C を読む間に D を実装してもらい、通る。B, C を読むと、C はそんなに簡単ではなさそう（コンテスト終了後に誤読していたことに気づく。条件が長方形でなくて共面だけだと思っていた）なのでその旨を Mitarushi さんに伝えて、自分が B を実装する間に考えてもらう。B は双方向リストをやるだけなのだが、 std::list のメンバをあまり覚えていなかったので、要素を配列で持ち、前後のポインタを index として持つようにして実装することにした。バグらせそーとは思いつつ、案の定沼ってしまった。Mitarushi さんに助けを求めると、愚直でよいと言われて、バカと申しますという感じになった。結局愚直を Mitarushi さんが書くことで B を通す（本当にすみません）。続いて考察が終わっていた C, F を Mitarushi さんが実装し、通る。自分はこの間に E を考えており、解法がわかったので実装を詰めておいた。Mitarushi さんが F を通したところで自分が E の実装を始めたが、これも境界値だったり off-by-one でバグらせまくり。Mitarushi さんとコードを共有し、独立にデバッグして何回か提出したものの通ることはなかった。全体 28 位で学内 7 位。

コンテストが終了したあとは同じ空間から参加していた同級生（筑駒勢）と問題についての話をした。国内予選は学内の端末（ECCS）から出ることになっていたがまだ環境構築に手をつけていないことを思い出し、その後図書館で ECCS 端末を初めて触ったりした。

環境構築

macOS の端末を使うことになり、環境構築は Mac 使いの自分が担当することになった。来年以降の出場者の知見になる可能性があるのでメモしておく。

管理者権限がないので、まあまあつらい。/usr/local を触れないので Homebrew もインストールできないかと思われたが、この位置は変更できるようで、$HOME/.local/homebrew に直接 clone してビルドすることで Homebrew は使えるようになった。gcc をインストールすることにより、悪名高き自分のことを GCC だと思っている精神異常 Clangの撃退に成功した（$HOME/.local/bin に PATH を通し、Homebrew の GCC からシンボリックリンクを貼る）。新しめの XCode Command Line Tools がないためソースからビルドが走ってしまい、30 分以上待たされるので注意。他にも gdb や llvm をインストールしたい気持ちになったが、このあたりのパッケージはより根本的に（？） XCode CLT に依存しているらしく、XCode CLT が outdated だと言われてインストールに失敗した。OS 自体をアップデートして xcode-select --install をすべきなのだが、管理者権限がないのでダメ。XCode CLT のバイナリをブラウザからダウンロードしてみたが、これも管理者権限がないとインストールできない。結局この問題は解決せず、不自由な環境での参加は致し方なさそうということになった。

あとは VSCode の環境についても書いておく。拡張機能は Extension pack ではなくて Clangd の方を使った（自分の PC でそうしているため）。プリインストールされている Clangd はバージョンが古くて不都合だが、Clangd 自体は LLVM の同梱物であるため先の問題により brew からは新しいものをインストールできない。よく覚えてはいないが、なにかをすると VSCode が最新版をインストールするか尋ねてきてくれるので、ありがたく従うことで latest のインストールに成功した。

次のようなディレクトリ構造にした。include 以下に bits/ やライブラリのシンボリックリンクを貼っておくと、.clangd だったりコンパイルオプションだったりが簡潔になってラク。

src
├── .clang-format
├── .clangd
├── ac-library
├── ... (好きなライブラリを src/ に clone しておく)
├── icpc_domestic2024
│  ├── A.cpp
│  └── ...
└── include
   ├── atcoder -> $HOME/src/ac-library/atcoder
   └── bits -> (brew --prefix)/Cellar/gcc/(version)/include/c++/(version)/aarch64-apple-darwin23/bits

国内予選当日

自分は一限があったので、それに出てから向かった。11 時を過ぎてから Mitarushi さんと浅野情報センターに着き、少し遅れて leafirby さんが到着しリハーサルに参加した（といっても問題はあまり解いておらず、環境構築に時間を費やした）。13 時に部屋の予約が切れてしまうので、chaircoolers(tada, anmichi, Ebishu) と KoD 先生とで本郷のサイゼリヤで昼を食べた。

初動をどうすべきかという話は度々挙がったが、本番では初め問題文が回ってこず、並列に問題を読めなさそうなので一番実装が速い人材が ABC あたりをやるべきだろうという話になり、Mitarushi さんが担当することになった。

16:30 きっかりにコンテストが開始する。特に問題なくコンテストサイトに接続し、Mitarushi さんが A から実装し始めるのを leafirby さんと応援した。印刷された問題文が配られたのは A, B, C が通ったあたりで、既に D の実装が始まっていたため、E-I を leafirby さんと手分けして読み始め、問題の概要を管理する紙に概要を書いた。E は構築、F はつらそう、G は見た目が素直な構築、H はつらそう、I は確率系のゲームという様な風に出揃った。G を leafirby さんが考えるとのことなので、自分は E をやることにした。このあたりで D が通り、順位表を見ると全体 4 位ですごすぎ。Mitarushi さんが F をやるというので実装をしてもらう一方、E, G はなかなか進捗しない。このあたりで自分が E 解けましたと主張し、F が通り次第実装に移れるように実装を詰めた。一段落して G に合流し、leafirby さんが天才構築を生やすなどして G も少しずつ進捗する。F の実装はつらそうだが、なんやかんや通った（本当にありがとうございます）ため、自分と Mitarashi さんの役割が swap され、自分が E の実装を始める。サンプルが合うのでデータセットをダウンロードし、実行するが、全然実行が終わらない。おかしいなあなどと呟いていると Mitarushi さんが解法を聞いてくださり、自分が $O((N^2{)}^N)$ を $O(N^3)$ だと思っていたことが判明する（バカすぎる）。萎えながら E を考え直すことにすると、隣では G が進捗していたらしく、重い（らしい）実装を leafirby さんが Mitarushi さんに押し付けることで G が通る。残り 30 分ほどのこの時点で A-D, F, G の 6 完であり、E が通れば Yokohama 行きも夢ではなさそうで、すみませんすみません……という気分になる。全員で E を考え始めると、なんだか Mitarushi さんが解けてそうな雰囲気になってきて、残り 10 分ほどの時間で爆裂実装を開始した。最初と同じように後ろで祈りながら、バグってそうな部分をいくつか指摘した。結局 5 分ほど時間が足りず、6 完でコンテストは終了した。

standings を眺めると、自分たち含めて東大の 6 完チームが 4 つ連続していて、しかもそれぞれ解けていない問題は分散していた。同部屋の SPJ のあたりの方々が「東大よわっ！」と叫んでいた。上位 10 位以内に東大が 2 チームしかいないのは珍しいらしい。

chaircoolers と遭遇したので彼らと一緒に本郷三丁目まで歩いた。Ebishu と anmichi とは本郷のやよい軒で夜を食べた。ICPC の話以外にも、進振りの話、Ebishu が RoboTech に入っているのでその話だったり、anmichi の将棋部の話だったりをした。

感想

19 位なので企業賞が生えていたらしく、Thinkpad のキーボードがいただけるらしい。株式会社 LegalOn Technologies、新しいオフィスを 19 階に構えてくれて、ありがとうございます……

コンテストの話をすると、（環境構築以外で）とにかくチームに貢献できなかったなあという悔いが残る。考察系の問題は得意でなく、アルゴリズムの知識でレートを稼いできたクチなのだが、ICPC の問題はそういうタイプの人間とはあまり相性がよくないようではある。来年以降 ICPC に出れるかわからないが、強くなる or 実装力をつける or 高度幾何・構文解析人材になるかして、チームへの寄与を大きくしたいなあと思った。チームメイト及び JAG 含め運営陣に感謝！