ICPC Yokohama Regional 2024 参加記

国内予選↓

toriidao.hateblo.jp

自分は Yokohama に参加するのは 2 回目．ラストイヤーなのでこれが最後．

去年の Regional の参加記を書いてなかったので軽く振り返っておく．

去年は CBT とよばれる医学部の進級試験のようなものが day1 とかぶっていた．CBT は朝 8:30 から夕方 18:00 まで試験会場に閉じ込められて，1 時間の試験を 6 セット走るという過酷スケジュールなため，ヘトヘトになりながら東京に向かったのを覚えている．

この試験は出題範囲が広いのである程度時間を割いて対策することが必須であった．もう一人のチームメイトが同じ医学科の同期であったこともあってチーム練をする余裕が全くなく，また US 配列に一度も触れることなく本番に臨まなければならなかった．試験の疲労が残り全く練習もしていない中での挑戦だったので、解くスピードはかなり遅かったが，事情を鑑みればこんなもんだろうと思って特に後悔は残らなかった．ほどなくして playoff というものが行われることを知った．60 チームが進出できる中で自分たちのチームは 61 位でボーダー落ちしていた．このときになって初めて多少ちゃんと準備しておけばよかった...とかなり後悔したが，数日後繰り上がりが発生したので 2~3 日以内に参加の意思を教えてくれというメールが運営から届いて無事 playoff に出場することができた．

ざっとこんな感じ．ここからは今回の Regional の話．

ベトナム playoff での経験で得られたものが多かったので，来年のシンガポール playoff にはなんとしても行きたいという思いが強かった．Yokohama と同じ US 配列を注文し，国内予選前から 3 人で土曜日に（秋ごろからは日曜日も）大学の図書館に集まって UC や CF gym の Regional の過去問で練習を重ねた．国内予選は 12 位で反省点がたくさん残る結果だったが，練習を積み重ねていくごとにチームメイトの特徴や役割をお互いに正確に把握できるようになり，連携がうまくとれるようになってチームとして安定するようになった．

UC を走っていると他の日本の ICPC チームが気になるようになっていた．SPJ, AMATUSKAZE, KUB1, Red Phobia, Anonyms, kotamanegi_hint_kureya あたりが気にしていたチーム．特に後ろ 3 つのチームと suzukaze は実力にほとんど差がないと個人的に思っていて，毎回彼らの順位をチェックしては自分たちの順位と比較して一喜一憂していた．

Day1

東北大のほかチーム Marines と同じ新幹線を取り，選手 + コーチ 8 人が東京駅で合流して横浜へ向かった．途中昼食を横浜駅で取った．

会場に到着して受付を済ませて中に入る．ちょうど真ん中あたりの席だった．Day1 は初めてだったのでちょっとワクワクしていた．チームメイトと適宜雑談をしながらルール説明やデモを眺めていた．デモで最初に WA を提出する茶番は恒例らしい？が，初めてだったので面白かった．Python で input() と input().split() だと型が違うので count の挙動が変わるみたいなことをしゃべったりした．

リハーサルではとりあえず事前に気になることを clar に投げた後，VS Codium の使い勝手についていろいろ試した．変数名の補間機能やシンタックスハイライトがあるかどうか気になっていたがちゃんとあった．去年にはなかった謎の補完機能が追加されていて使いづらかったが，設定をいじるのも怖かったので我慢することにした．問題を解かずにいろいろいじっていると運営の人に心配されて声をかけられたり周囲をうろうろされて様子を監視されたりしていた．

特に問題なくリハーサルが終わり，チーム紹介に移る．英語がまともに喋れないので日本語で日本人向けに TUPC の紹介をしたら怒られてしまった．すみません...

リハーサルが終わったら東北大 8 人で中華街で夕食を取りそのまま解散．suzukaze は 4 人一緒のホテルを取っていたが，ホテル代を安く済ませるためにやや遠くのホテルを取っていた．遠いことは認識していたが思っていたよりも遠く，身体への負担が大きかった．23 時に消灯したが，まったく寝付けられず最悪だった．寝ようにも寝られず，スマホで寝る方法を調べたり YouTube で睡眠用の BGM を流してみたりしたが全く効果なかった．結局寝れたのは午前 2 時頃だった．

Day2

6:10 起床．明らかに寝不足．ホテルの朝食を済ませて 7 時半出発．8時半ごろ到着し，コーチとお別れして入場．着席した後は初動について確認していた．コンテスト開始が急に 15 分繰り上げされてビビったが，コンテストまでの苦しい虚無の時間が苦手な自分にとっては助かった．

コンテスト

PC のセットアップを Dis さんがしている間に僕と仮君で A 問題を一緒に見る．何が書いているかさっぱり読めずぼーっとしているところに仮君が概要を伝えてくれる．区間 chmax する操作回数を最小化して与えられた数列を作ってくださいという内容で，操作を逆順に見ると簡単．制約が緩いので O(N\max(A)) かけて通す．(0:06)

続いて B 問題の概要を伝えられる． L 以上 R 以下の整数のうち popcount が最小になるものは？という内容で，セグ木の区間を意識すれば簡単．ちょっと実装に手こずったが AC (0:12)．

ここまでは想定通り．B 問題を書いているうちに Dis さんと仮君が残りの問題の分野を大雑把に把握してくれていた．ぱっと見自分は I 問題が得意そうだったので目を通すと，クエリ先読みをしたうえで l の降順にセグ木を使いながら答えを求めればよいことにすぐ気づく．Dis さんにセグ木の写経を発注して仮君に解法の概要を伝える．うまく伝えられず彼にはよく分からないと言われたが，割と自信があったしほかの問題も AC が出ていなかったのでそのまま I を書くことにした．ちょうど写経も終わった頃だったのでそのまま実装する．実装に詰まることもなく AC (0:29)．計算量をあまりちゃんと考えていなく，本番中は O(N\log N\log \max A) くらいで余裕だと思っていたが実際は O(Nd(\max(A))\log N) でそんなに余裕はなかった．

まだ I 問題に 2 チーム AC 出ただけで順位表に動きはなかった．ほどなくして E に AC が出たので二人に読んでもらうと簡単な構文解析チックな問題だった．実装は私がやったほうが良いと言われたので概要を聞いて問題文にある通りに実装して提出，AC (0:43)．

自分が E の実装をしている間に二人は K に取り組んでいて解けたらしい．仮君の実装を Dis さんが監視する体制にして二人が PC に向かう．自分は残りの問題を読むことにしたが，C 問題は問題文が何言ってるかわからず，D 問題は概要は把握したが何から手を付けていいか全くわからなかった．頭が全く働いていなかったので実装中の K の問題概要と解法を Dis さんから聞くことにした．ゼータ変換をして反転した bit を見ればよいと主張していて正しそうですねと言う．ゼータ変換をした後に自分自身が相手になってしまうことはないか？という疑問が湧いたので Dis さんに質問したらそこは大丈夫と言って確かにとなったが，全部 Y のときにコーナーになることに気づいた．全部 Y であるような index の配列を作ると楽そうと実装に口出ししてそのように実装してもらう．実装は全部終わったがそれでもちょっと怖かったので，ぺナを出さないことを優先して僕がランダムチェッカーを書くことにした．ちゃんとランダムチェッカーが落ちないことを確認して提出，AC (1:07)．

その間に kotamanegi_hint_kuerya が C を解いているのを見て C を Dis さんが読んでいた．概要を伝えてもらい，主客転倒したら最短経路やるだけではないか？と言った．Dis さんも同じようなことを考えていたようだったが自信がそこまでなかったように見えたので，かなり正しい解法のように見えますと主張して Dis さんに正しそうなこと納得してもらい，Dis さんに実装を任せる．解法が簡単な割に開始 1 時間時点ではほとんど解かれていなかったのが不安だったが AC した (1:18)．

この時点で 6 完 2 位．Screenwalkers に 1 分差で迫っていた．再び順位表情報が無くなったので解けそうな問題を探す．この時間帯はしばらく順位表を眺めてほかチームの動向をうかがっており，その姿がライブ配信にも映っていた．最初に F 問題を取り組んでいたがあまり筋のよさそうな解法が思いつかない．Screenwalkers が F 問題でぺナを吐いていて沼りそうな予感がしたのでいったん切り上げる．Anonyms が L 問題に挑戦していたので概要を把握する．連続する区間であってその和を d で割った余りが r であるようなものを削除していく問題で，直感的にこの問題は解ける気がしたのでこの問題に取り組む．制約が N\leq 500 なので区間 dp が怪しそう．複数回操作することでごっそり削除できるような区間が分かると嬉しそうな気持ちになる．いつもの区間をマージする遷移は簡単にできるが，問題は操作が括弧列のように入れ子構造のとき．これを O(N^3) で解決するそれっぽい解法を思いついて，Dis さんに方針を伝えて監視してもらいながら実装する．サンプルがあったので提出するが WA (2:12)．ランダムチェッカーを書くと入れ子構造のときの遷移が全部カバーできていないことに気づく．今の方針だとかなりまずいことに気づいて一から考え直し．しばらく手が止まる．私は L を粘ることにして仮君と Dis さんは正解者が増えてきた D に着手する．

開始から 3 時間ほど経過．徐々に 7 完が増え始めそれとともに suzukaze の順位もずるずる落ちていく．だんだん焦りがでてきた．L が全く分からなくなってしまったのでいったん私も D に手を付ける．仮君と Dis さんは一緒に考えていて，私は一人で考えていたが，焦りのせいか考察が進まない．少しして二人が D を解けたと主張する．解法を聞いたが全く理解できない．二人はそこそこ自信がありそうに見えたので仮君に実装に入ってもらうように言ったら，実装は私がしたほうが良いと言われた．解法を詰めてもらって実装方針を伝えてもらい，再び Dis さんの監視の下で私が実装する．解法は通り掛け順に頂点に番号を振っていって得られた 2 つの木の頂点を対応付けたうえで適当な積を取るというもので，結局なぜその解法が うまくいくのかよくわからなかった．実装は割とうまく書けて，サンプルがあったので提出するが RE が返ってくる(3:37)．いくつか assert を付けていたところがあったので一つずつ確認すると入力の長さが 1 のときに壊れていることが分かった．それだけ例外処理をして再び提出して AC (3:39)．順位が 14 位から 5 位に上昇し一安心．

順位表的には FGL あたりが解かれていて，自分は L に専念する．ランダムチェッカーで落ちたケースをしばらく考えていると，区間の中で削除操作が何回できるかに注目するのがよさそうなことに気づく．ただこのままだと 区間 [L,R) の中で k 回の削除操作をすることができるか？という bool を dp に持たせることになるが遷移が O(N^4) くらいになって，bitset 高速化は不可能ではなさそうだが厳しそう．もう少し考察を進めると，ちょうど k 回削除操作ができるときちょうど k-1, k-2, \ldots, 1 回操作することも可能なことに気づき，結局区間ごとに最大で何回削除操作できるかを管理すればよい．Dis さんにまた監視されながら実装を進め，嘘解法で落ちたケースもちゃんと正しい値が返ってきており，ランダムチェッカーでも落ちない．今度こそ満を持して提出，AC (4:27)．

ここで playoff 進出を確信．一気に力が抜けた．L の考察・実装中に仮君が F を考えており，自信のない解法が生えたようで，残り時間も少ないのでダメもとで書いてもらう．その間に私と Dis さんは F と G を考える．G はそれっぽい解法が生えるが実装がやばそうで 30 分では無理と判断し F を考えると，いい感じに 3 点を選んで外接円を考えればよさそうなことに気づく．F を実装中の仮君は書いてみたがサンプルがあわないらしい．仮君に外接円の解法を共有し，Dis さんには幾何ライブラリを写経してもらう．仮君と二人で解法を詰めたがもう時間がほとんどない．ごちゃごちゃやっていたらサンプルがあったので奇跡を信じて提出したが WA．そのままコンテストが終了した．

凍結中の順位表を確認し，playoff 進出で間違いないことを確認．3 人で喜んだ．

その後，9 階に上がって Yes/No．KUB1 の最後の追い上げと Screenwalkers の圧倒的強さに感動した．自分たちは序盤のアドバンテージがそのまま残り 8 完最速で 7 位．企業賞はもらえなかった．6 位の Red Phobia には G を通して抜かされてしまった．順位としては 1 つしか差がないが大きな実力の壁を感じた．

その後は懇親会．ベトナム playoff で仲良くなった阪大と京大の方々や，SPJ，審判団長の Y.Y. さんなどいろんな人と交流した．kotamanegi さんは早速 playoff が確定したチームに声をかけて discord を作っており頭が上がらない．シンガポールでまた会いましょうと挨拶をして会場を後にし，その日中に仙台に戻る人たちと一緒に帰った．

反省

コンテスト全体を振り返ってみると，序盤はこれ以上ないパフォーマンスが出せたが，中盤・終盤は実力不足を感じた．ここから順位を上げるためにはもう 1 完増やす必要があるが，正直今の実力だと厳しい気がする．L 問題が最初から正しい解法を引けていれば G 問題の実装に手を付けられた可能性はあったかなあ． 7 位という結果は上振れも下振れもせず実力通りかなと思う．国内予選では不甲斐ない結果だったが，そこから練習を積み重ねた成果が出せてそこそこ満足いく結果が得られたのはよかった．チーム力はだいぶ上がったが，個々の実力不足を感じる結果だったので，2 カ月後の playoff にむけてそれぞれの実力をパワーアップさせて東北大初の WF に行けるように頑張りたい．

さいごに

このような素晴らしい機会を提供してくださっている運営の皆さん，本当にありがとうございました．Yokohama に選手として参加することはなくなりますが，今後は JAG として運営をお手伝いできればと思っています． 一緒にシンガポールに行くみなさん，引き続きどうぞよろしくお願いします．