以下の内容はhttps://kumakumatime.hateblo.jp/entry/2024/12/23/030515より取得しました。


ICPC 2024 Asia Yokohama Regional 参加記 by Kite_kuma (SPJ)

ScreenWalkers が台湾で優勝したので,ここで優勝するしかなくなった.もともとこちらは圧倒的に格下でスピードも考察力も全く足りていないので,得意ジャンルのどれかで一発当てるしかない.具体的には,私が謎の幾何をやるか,zkou が天才構築パズルを解くか,nok0 が数え上げを解くかのどれかでしか勝ちがない.出題される問題の傾向によってはこちらに全くチャンスがないこともあり得る (というか,9 割くらいはそうなる) と思っていた.

1 日目についてはおまけってことでまた後日に書きます.


あまり良く眠れないままホテルで朝を迎える.普段は部屋を寒くして寝ているため,ホテルの部屋は室温が高く寝づらく感じる.寝汗を流すためにシャワーを浴びて,朝食を取りチェックアウト.会場までの道のりで審判団員の 〇pt さんを見かけ,話しかけて良いか分からず挙動不審にしていたら普通に話しかけてくれた.まあ今日は期待してて下さいよ!と言ったら笑いながら「ノーコメントです」と返されて,こちらも笑ってしまった.

8:40 に集合予定だったが,nok0 が 10 分くらい遅刻して,8:50 ごろに入場.使い古されたライブラリの束を取り出して,自作した環境構築のマニュアルを眺めつつ,ああもう自分にはあと 5 時間しか残されていないのだなと覚悟を決めた.

開始.私がもたつきながらも環境構築を済ませ,nok0 が A を通した後に,私が zkou に教えられながら B を書き上げる.予定通り C から問題を読んでいく.C は最小全域木っぽいがよく分からない.D はなんだか考察が重そうな数え上げに見える.E でも読むか…と思っていたところに nok0 から I の解法を提案される.大筋を納得して,細かい部分を考えつつセグ木を写す.その間に後ろで zkou が K の解法を思いつき nok0 に提案する.実装も軽いので PC を交代して K を書いた.K がペナって焦るもなんとか通し,私が I を通す.

それなりに順調な滑り出しに思えたのだが,この時点で確か 4 位くらいでしかなかったので焦る.本当は 2-3 位であれば良かったのだが,選んだ問題の順序のせいでもありしょうがない面もある.E がよく解かれているので,見てみると文章が長いだけの簡単な DFS なのでこれを書く. 通ったものの,実装がもたついたことと,これを先に読んでいればという後悔により少し落ち込む.

次に取り組む問題が分からなくなったが,順位表を見ると C が解かれている.よく分からんと思ったのだが…これって頂点 1 から重み付きで Prim 法やれば行ける?と提案する.zkou に若干疑われるも,これだけ通されているならこれくらいしか解法がないだろうということで書き始める.ほどなくして AC.実は最短路木を取っているだけであることに最後まで気付かなかったのはここだけの話.

次に私,nok0, zkou の 3 人でそれぞれ L, F, D を取り組んでいた.3 人とも難航していたものの最初に解法を提案したのは F をやっていた zkou. スタート地点の折り返しの点が高々 4 通りしかないので,そのうち 3 つを取って外心を取れば良い,という説明で納得できた.これなら実装も外心くらいしか非自明なところがないし,それほど重くせずに書けそうだ.zkou と 2 人で実装を行い,サンプルが合って提出するも WA になってしまう.ScreenWalkers もペナっている様子だったので焦らずミスを探す.まず制約が小さいので全ケース出力できることに気付き,出力させてみる.今後投げるときはこの出力結果に差分が出たときだけで良い.zkou が折り返しの点として他にも 2 点考える必要があることに気付くと,少しだけ差分が現れる.これで勝ったな,と思い提出するとさらに WA.原因不明,悪夢の連続ペナに心が参る.この問題は愚直解と突き合わせるなどのテクニックが効かないのが辛い.ひたすら自分のコードと向き合うだけの時間が続く.

nok0 が D を書き始める.私は途中ふらっと L に寄り道したりしながらも印刷された F のコードにおかしいところがないか確かめる.何度読み返しても合っている…もうだめか,と思って,諦めつつ実装を少し代わってもらい,もう 1 点,直方体の向かいの点についても調べることにしてみる.

…差分がある.え,うそ….これが F 問題の FA になり,かなり沈んでいた順位表で 5 位にまで上昇した.続いて解法の正当性が怪しいと話していた D も通り,突然 2 位になった.うおおおおおおお ScreenWalkers 抜いてるやん!!!!…あのーシンガポールの方邪魔しないでもらえますか?とか言ってたら ScreenWalkers も F を通して再逆転され,我に返った.

ここまでで 3 時間強.あと 2 時間で G と L いけるやろ,と思っていた.L は解けそうなのだが,微妙に解けない.G で二分探索するアイデアだけ zkou に渡して詳細を詰めてもらい,L を nok0 と 2 人でやるも,なかなかアルゴリズムに辿り着かない.

ここで zkou に G の解法を提案される.これは解説スライドにあるものと全く同様のもので,これをシビアなクエリ制約で出題することに震えたが,どうせ勝つのには必須だし,解けるものは実装するしかない.zkou にそばで見てもらいながら実装を始める.

中央から始めるせいで初回のみ場合分けが必要なのもかなり面倒だ.ちなみにこのとき L はまだ計算量解析が分かっていない箇所もあるのでいったんやらないことにしていた.悶え苦しみながらもなんとかサンプルが合い,残り 40 分ほどで提出するも WA.焦りが頂点に達しつつ必死にデバッグする.残り時間が少なくなっても焦らない余裕が本当に欲しいといつも思う.幸い入力を作るのは簡単なので,色々なケースを試してみると…コードに色々と穴が見つかっていく.それらをひとつひとつ潰して,最後に提出したのが 4:54 経過時だった.どうせこれが通っても L をやる時間はないので,ジャッジ結果を見ることなく G に他のサンプルをいくつか入れてバグがないかを確かめていく.どうやらバグもなさそうだなと思ったところで順位表を見ると,緑色の四角が見えた.残り数分.L が詰められていない以上もう何もできない.ああ,これで俺は終わるんだ,もう....nok0 が L を説明しているのに,放心状態になってしまい,何もまともに聞けなかった.

The contest is over. 順位表から見えているだけでも正解数で負けているので,自分の ICPC が終わったことが確定的だった.

「5 年間ありがとうな…本当に」

2 人の肩に手をやって言葉を掛けたとき,急に目頭が熱くなって,泣き出してしまった.なんか 2 年前もこんな感じだった気がする.そこからしばらくのことはあまり覚えていない.泣きじゃくりながら,来年も誰か見つけて出てくれよ,俺がコーチやるからさ,みたいなことをずっと言ってた気がする.

解説会.L 解けなかったことを強く反省した.H, J は面白そうなので後で解説片手に考えてみたい.LP 双対とか,マトロイド交差とか,なんか東大数理情報で聞きまくる単語ばっかりなんですが?そこまで辿り着けるレベルにはなれなかった….全体的にはどの問題も非常に面白く,最後の ICPC がこのセットで良かったなと心から思えた.

Yes/No セッション.横浜で Yes/No をいつもやっているあの方は本当に手慣れていてすごいと思う.特に "nyo!" が良かった.結果は去年と同じ 5 位.結局 AMATSUKAZE と KUB1 の両方に負けてしまった.どちらかには勝ちたいと思ってたんだけどな.こんな弱いやつの言うことなんてほっといてこれからも強くなって欲しい.

写真撮影で少しふざけたら 2 人に呆れられた.あれはまあただ単に,なんとなくそのまま帰る気分になれなかっただけなんです....

懇親会.阪大の vwxyz, 京大の naniwazu と雑談.この 2 人とは高校時代から縁がある.こたまねぎさんは ICPC ではめっちゃ頼りになるとか,WF で KUB1 は SPJ より明らかに強いと思ったとか,そういう話を聞いた.SPJ はどちらかというとチームワークでなんとかしているチームなのだが,結局もう少し個人の力を伸ばさなければ上では戦えないのだろうなと感じたりもした.あと vwxyz のインベーダー将棋が強すぎて勝てる気がしなかった.

解散後はチームの 3 人でジョナサンで軽く食べつつ喋った.私は来年以降の出場権を失ったが,実は 2 人はまだ早生まれとコロナ関係の特例で出ることができる.私の後継も見つかるかもという話をしていた.誰に来ていただけるか分かりませんが,幾何と構文解析,あと 2 人がやりたがらない諸々のことをよろしくお願いします.数え上げと閃き一発ゲーなら,本当に頼りになる 2 人です.5 年間一緒にやってきた私が保証します.

帰りの駅に向かうとき,話しながら歩く 2 人の後ろ姿を見て,おぞましいくらい強烈な物寂しさに襲われた.これからこの 2 人と遊びでチーム戦をやることはあっても,もう 1 台の PC と使いにくいキーボードをわちゃわちゃしながら取り合うことはないのだろうし,以前ほど本気で取り組んだりもしないのだろう.

私にとっては,SPJ とは競プロそのものだったのだ.大学で熱中していたこと,そのものだったのだ.

3 人で本当に,本当に色々な問題を解いた.走ったセットももう数えきれないくらい多い.最初の年は顔も知らないままずっとやっていた.2 年以降は大学の野外のベンチでやったり,カフェでやったりカラオケでやったり,くだらねーと言いながら重実装をしたり,チームメイトの天才的な解法に惚れ込んだり,旅行中にふざけて日本語禁止競プロもしたし,一緒に ARC を作ったりもした.

そして何よりの思い出は,残り少ない時間,全員で一丸となって一つの問題と PC に向き合い,一つでも多く正解をもぎ取ろうと戦ったことだ.うまく行ったときも,行かなかったときもあったが,どんなにつまらない問題セットだったとしても SPJ でのチーム戦は楽しかった.

なんで俺だけ先に終わっちゃうかねえ,ほんとに.そういうことを考えながら帰路についた.


これにてチーム SPJ (Kite_kuma, nok0, zkou) の ICPC は終了となります.nok0 の顔が広いこともあってか,これまで様々な人に応援していただきました.あとの 2 人が来年どうするかは分かりませんが,出ていたら応援してあげて下さい.JAG スタッフの方を含む ICPC 運営の方々,及び大学でコーチや監督員を引き受けて頂いた方々,今まで本当にお世話になりました.




以上の内容はhttps://kumakumatime.hateblo.jp/entry/2024/12/23/030515より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14