ICPC アジア地区横浜大会 2022 参加記

チーム suzukaze_Aobayama (milkcoffee, karinohito, sotanishy) で，ICPC アジア地区横浜大会 2022 に参加した．

今回はオンサイトでできるということで，とても楽しみだった．一方で，コロナ前のICPCルール (ライブラリ写経やPC1台制限) に触れるのが初めてであり，不安でもあった．

目標は，全体10位 & 学内1位．

本番前

11/27 模擬地区
オンサイトでも開催されるとのことだったが，流石に東京は遠い.....ということでオンライン参加．数日前に本番のルールが公開されたので，それに則って参加した．US配列を使っていたのが僕だけだったので僕のパソコンを実装マシンにして，ライブラリも僕のを使うことにした．

初めてICPCルールでやってみての感想:

  • 他人の環境で競プロをするというのはかなり苦しい．みんな実行・デバッグの仕方やファイルの命名規則，マクロの仕様などが違うので，僕のマシンで実装するのは大変そうだった．
  • ライブラリの仕様の理解不足によるバグが発生したりして大変だった．また，写経ミスが多発．
  • 実装キューが詰まりまくり．バグが発生したときに，どのタイミングで実装待ちの人にパソコンを譲るべきかが悩ましい．また，実装待ちの人が手持ち無沙汰になりがち．

この辺はしっかり練習しないとな，と思った．

結果は6完16位，guestを除くと12位で，そんなに悪くはなかった．考察は割とスムーズに行って，最終的に attempt したすべての問題の本質的な考察は開始2時間程度で終わった．あとはひたすら実装キューの消化作業だったが，実装が重く，ライブラリが必要なものが多かったので，実装もデバッグも大変だった．

その後の練習

模擬地区以降，ほぼ毎週末チーム練を行った．コドフォの gym の海外 regional を中心にバチャを走った．並走してくださったチームには感謝いたします．

練習していく中で，次のような戦い方に固まってきた．

  • 実装と考察の分担は特にしない．全員がそれぞれ問題を読んで，解けたら自分で実装する．
    • 特にパソコン1台ルールだと，実装が得意な人が実装を引き受け，残りの人で考察を進めるという戦い方のほうがスムーズなのかもしれない．しかし，僕らは皆同じくらいの実力であり，得意分野も分散しているので，全員で考察したいという気持ちがあった．
  • 実装中に詰まったらすぐに離れて次の人に譲る
    • 詰まったらそのまま実装マシンを使って出力を見ながらデバッグしたくなるところだが，実装キューが詰まっているときはすぐに離れるように心がけている．マシンを使わないとデバッグが難しいのは確かだが，一旦実装から離れてコードを読むと頭が冷えてバグが見つかりがちである．ただ，本番ではコードの印刷がどれくらいのオーバヘッドになるかわからないのが心配．

ライブラリ

僕のライブラリは実装が冗長なので非常に写経しづらい．ICPC向けの簡潔な実装をした他の人のライブラリをパクってこようかとも考えたが，仕様が好みでなかったりした．結局，写経しづらくても使い慣れている自分のライブラリを使うことにした．

印刷するために，ライブラリをまとめたファイルを以下の手順で作る．

  1. 持っていくものを取捨選択する．心を鬼にして†断捨離†をする．
  2. 横浜国立大学のICPCライブラリの tex の設定をパクってくる．ありがとうございます．
  3. 選んだライブラリのソースコードとドキュメントを tex ファイルに貼り付ける．これは適当に Python スクリプトを組んだ．
  4. 手動でドキュメントをいじって微調整

2カラムで30ページ強になった．両面印刷すれば15枚程度と，結構コンパクトにまとまった．

お守りとして link/cut tree を入れた．チームに1本あると安心感が違う．

Day 0 (12/26)

この日は最後のチーム練で，2022 ICPC Southeastern Europe Regional Contest を走った．不快要素が少なくかなり楽しめ，良い感触が得られた．

夕方くらいから本番に向けてそわそわし始めた．修学旅行前夜や，部活の大事な大会前 (これは実際にそう) のような気持ちになっていた．夜は荷物や着替えをまとめたり，考察メモを印刷したりしていた．翌朝は早いので．早めの就寝．

Day 1 (12/27)

7時半ごろ起床．朝ごはんを食べて仙台駅に向かう．チームメイトと合流し，新幹線に乗り込む．新幹線では問題を解こうとしたが，画面を見ていると酔って気持ち悪くなってきたのでやめちゃった．

東京駅や横浜駅で他の東北勢と合流し，横浜駅でご飯を食べる．

カツを食べて勝つ！

腹ごしらえが済んだら会場の横浜産貿ホールに向かう．13時頃入場する．一応公式言語が英語になっているらしいので受付では英語対応だったが，スタッフも日本人なのでなんか違和感がすごかった．

suzukaze_Aobayama の席は一番後ろの方だった．これは結構当たりな気がする．会場全体を見渡せることと，後ろが気にならないというのが結構良い．席についたらICPC Tシャツに着替えて，チーム紹介ドキュメントを見たり雑談をしていたりした．

14時になり開会式が始まる．今年のオープニング動画もかっこよかった．

www.youtube.com

14:50からリハーサル．去年のアジアの問題がそのまま出るものかと思っていたが，今年はインタラクティブがあることもあってか全く違う問題が4問集められていた．印刷の手順やエディタの機能の確認をしつつ問題を解いた．全完したあとは，トイレに行く練習 (英語でスタッフに声をかける必要がある) をしたり，キーボードに慣れるために写経の練習をしたりしていた．

16:30からチーム紹介．喋りはチームメイトに任せて僕は名乗るだけだった．

終了後，ホテルに移動する．チームメイトと相部屋．同じホテルには他にも競プロerが結構泊まっていたようである．荷物をまとめたり一休みしたあと，東北勢で中華街に繰り出して夜ご飯を食べた．

↑とだいたい同じものを食べていた．もう完全に修学旅行気分です．

8時半頃またホテルに戻る．3人でAGCの赤diffを考察しないかと誘われ，AGC022 E - Median Replace を考えた．なんか3人で考察を言い合っていたら解けてしまい，感動した．

Day 2 (12/28)

朝7時頃に起床する．朝食を食べる．眠かったので軽く二度寝をする．

8時半頃に会場に着き，開始を待つ．

9:30開始．まず milkcoffee さんが環境のセットアップをしつつ，僕がA，仮の人くんがBを見る．Aは親の顔より見た貪欲だったので，セットアップが終わる前にマシンを奪い取り実装する．AC (A: 0:08)

その後，milkcoffeeさんがCから先，僕がKから前にひと通り見ていって，解けそうな問題を探す．K, J, I と見ていって何もわからね〜と言っていたところで，開始30分頃にFのACが出たことを確認したので，僕とmilkcoffeeさんでFを見に行く．

その間，仮の人くんがBのインタラクティブと格闘していたよう．WAが取れなくて大変そうだったが，通る (B: 0:45+2ペナ)

Fを考える．制約的に部分和問題になりそうなのと，何らかの偶奇がクリティカルになりそうということを感じ取る．ところが考察がそこから進まない．するとmilkcoffeeさんが，サイズ偶奇が等しい4つの集合に分けれるのが必要十分だという．これはかなり正しそうだが，そのままやると計算量が大きくなってしまう．さらにmilkcoffeeさんが，サイズが偶数で和が等しくなるような2等分の仕方を2つ持ってきて，それらの共通部分や差集合を取れば4つの集合が得られるという．これはかなり天才で，確かにこの制約で正しい答えが得られる．細かい所の正当性などいまいち理解しきれていないところもあるが，正しそうなのでそのまま実装に移る．たまたま僕が実装席に座っていたのでそのまま実装してAC (F: 1:45)．Fの 3rd AC だったようだ．

順位表を見ると，D, E, G にACが出ているので，3人で手分けしてこれらを読むことにする．Dはほか2人がすでに目を通していたので問題概要を伝えてもらう．実装がつらそうだが気合で行けそうな雰囲気の問題だったので，僕がDの実装に取り掛かることにする．

実装方針をあまり固めずに取り掛かってしまったので，実装が大爆発し，途方に暮れていたところで，仮の人くんがGを解けたというので実装を渡す．その間に僕とmilkcoffeeさんでEを考える．とりあえずサンプルを手でやってなんかいい感じの性質を見つけようと思ったが，ICPC文字列を探すのが下手すぎてサンプルの理解に30分以上かかってしまった．

Gに嘘が発覚したらしく，僕がDの実装を，仮の人くんがGの実装を代わる代わるやる感じになった．

Dを書いていたところで，仮の人くんが「次の問題が解ければGは解けます．木で，一つ固定のパスがあります．クエリが飛んできて，木の2頂点が与えられるので，それらを結ぶパスがその固定のパスと共通の辺を持つか？」と聞いてくる．それは解けて，固定のパス上にない頂点について，それを含む部分木が固定パスのどの頂点から出ているか前計算しておけばよいということを伝える．それで解けたらしく，Gの実装を渡す．デバッグが大変だったらしいが通る．(G: 3:35)

コンテストも終盤に差し掛かっている．そこそこのACが出ていたDとEを通すのが現実的だろう．僕は引き続きDの実装をして，残りの2人にEを見てもらう．

Dは流石に落ち着いて方針をちゃんと定める．4回転全部試し，x方向のシフトを全探索する．y方向のシフトは定数個の候補しかないので全探索する．シフトを固定したら，マス目を一つ一つ見ていって，oを取り除く場所と付け加える場所が1つずつあるかどうか調べる．この方針でやることにした．それでも実装はかなり大変である．

仮の人くんがEを見た瞬間解けたらしく (は？)，僕がDをやっている間に紙コーディングまで済ませてしまったらしい．Dで詰まったタイミングでEの実装を譲る．実装して少々デバッグし，提出する．計算量が結構ギリギリな解法らしく，提出後数分はジャッジ結果が帰ってこずヒヤヒヤしたが，Correct Answerが返ってきてチームが沸く (E: 4:39)

さて，あとはDだけである．これはなんとしてでも通したい．実装を終わらせ，デバッグをしばらくすると，サンプルが合う！一応自作ケースも試しておこうと，僕が実装していた間に作ってもらっていたケースを入力する．落ちる！困った．

原因がわからないまま残り1分になり，自作ケースがテストケースに入っていないことを祈って提出してみたが，Wrong Answerで終了．

5時間あっという間だった．

EFGが通ったのはなかなか良い結果であったと思うが，Dが通せなかったのは非常に悔しい．また，EFGに関しても僕はあまり本質的な貢献ができなかったので，少し残念だった．

閉会式．スポンサーの方々のありがたいお言葉を拝聴したあとは，解説である．去年よりは簡単な問題を用意したつもりだと言われたが，そんなことなくない？まあ高難易度のあたりはどちらにせよ解かないので知らないが，中盤の問題は去年よりも大変な感じがした．Dはうまい方針があるのかなあと思っていたが，解説でも場合分けが想定で，単に気合が足りなかっただけかなあ．Fはかなり難しい想定だったらしく，すんなり解いたmilkcoffeeさんがすごい．Jはかなりシンプルで面白い．Cはあまりにも天才．Hは，仮の人くんが得意そうな問題で，ちゃんと読んでいれば解けたかもと悔しがっていた．でも，あの順位表でHに行くのは勇気がいるよなあ......．Iは不可能．

待ちに待ったYes/Noの時間である．結構なチームが凍結後に通していて，僕らの順位が大きく下がったりしないだろうかと心配だったが，5完内で上の方に残れたので結果は13位．最後Dを通していたとしても，6完最下位になりそうだったので，順位は1位しか変わらなかったようだ (それでも通したかったが)．

その後懇親をし，東北勢と打ち上げをして解散した．

振り返り

個人的には結構冷えた感覚だったが，13位というまずまずの成績を収められたのは，F，Eをそれぞれ爆速で解いてくれたmilkcoffeeさんと仮の人くんのおかげだ．今回はただただチームメイトに助けられた．

PC1台の特殊なルールの中でもそれなりにうまく立ち回れたという感覚はある．詰まったらすぐ印刷して実装を譲るというのはちゃんと練習してきたし，今回もそのへんは本番でもスムーズに行けたと思っている．実装キューもあまり詰まらなかった．

今回のコンテストでは，考察力だけでなく，実装力の不足を痛感した．実装力というのは単に長い実装を素早くやるだけではなくて，バグりにくいコードを書く力，実装が楽な方針を選び取る力．特にPC1台ルールではデバッグの速度が非常に重要だと感じた．

最後に

コンテスタントの方々，スタッフの方々，素晴らしいコンテストをありがとうございました．

Aobayama_dropout の方々にもとてもお世話になりました．入学時からの憧れのチームだったので，同じ舞台に立てたことはとても光栄でした．結局今年は最後まで勝てないまま終わってしまい，そしてこれから先戦うことがかなわないのは残念であります．お疲れさまでした．

そしてチームメイト，コーチ，ありがとう．

来年はもちろん学内1位で国内予選を突破したい．dropoutがいないとはいえ，東北大には他にめちゃくちゃ強いチームがいるので，うかうかしていられない．dropoutがいなくなっても見ごたえのある東北大を目指します．