2024 年度の ICPC （国際大学対抗プログラミングコンテスト）Yokohama Regional に zer0shiki で参加しました。国内予選の参加記 で言及した通り 6 回目にして初の Yokohama です。国内予選は 10 位でしたがどうなるでしょうか。

当日まで

国内以後は JAG 合宿に参加し、その後 UC に参加して 5 時間コンや US キーボードの練習をします。何度か走るうちに、 kenken は実装が苦手でありチームとしてもそれをわかって立ち回るようになりました。ただし完全に回避するわけではなく kenken が重く考察している問題は kenken が実装するようにしています。

シンガポールに行くための学内争いはこのポストの通り。優勝争いには干渉できないので無視し、「 WADATSUMI に勝つ」「ある程度上位に入る」ことを意識するようにしました。

1 日目

zer0shiki + Ponjuice の 4 人で横浜で有名なデカカツ屋に行きました。

会場に無事到着。 初めての Yokohama で新鮮な気分です。

その後はリハーサルです。ジャッジは馴染みある DOMJudge だったのでエディタの使い方とインタラクティブを軽く見て clar を飛ばしまくりました。

zer0shiki + WADATSUMI + tatyam の 7 人で民泊を取っていたのでそこに泊まります。男 7 人でまさに修学旅行の雰囲気で、部屋のテレビに YouTube をキャストしてゆゆうた･クサヤ人･岩井星人とかそこらへんを見ました。

久しぶりにゆゆうたの動画で大笑いした。俺ゆゆうたの動画で笑ってもいいんだな。 23 歳だけど。

2 日目

ちょっと早く目が覚めたので起床喇叭で音害をかまします。

無事に全員起きて過剰供給されてたパンを朝食にして会場に向かいます。

競技

9:30 開始のはずが 9:15 に始まってマジでびびった。初動を決めてなかった(??????)ので国内予選を参考に僕が A 、 zer0-star が B 、 kenken が他で解けそうなものを見つけることにしました。

A 問題

何事もなく AC と思いきや塗る必要のない色で塗ってしまい 1 WA してしまいまし。 zer0-star の B と平行して修正して AC 。

B 問題

読んでません。 zer0-star が解いてくれた。

E 問題

この時点で 2 完しか出ていなかったのでどれを解くべきかわからず僕もざっと全体を見てとりあえず F 問題を考察することに。この間に kenken が E 問題を AC し他の問題にもぱらぱらと AC が出始めたので F を捨てて僕は K 問題に向かいます。 kenken は C 問題、 zer0-star は I 問題に向かったはず。ここらへんの記憶が曖昧です。

K 問題

少し考察しているうちに部分集合に自分の情報を配る DP を思いついて書くが計算量が $O(3^M)$ で、 $M\le 20$ でそれはまずいと止められたので DP を見直すとまさしく高速ゼータ変換であることに気づいた。高速ゼータ変換を書いたことがなかった(????)のでそこだけ kenken に書いてもらい出すと WA 。しばらく頭を悩ませていると zer0-star にコーナーケースを指摘され、そこを直すと AC 。二人に指示を仰いで C 問題に向かいます。

C 問題

読解が大変！先に読んでいた kenken の話を聞きつつサンプル 2 をとりま主客転倒すると得るべき木がなんか最短経路木っぽいのでダイクストラを写経すると通りました。

暗雲

zer0-star が Mo を思いついていて、ただ時間制限がキツいと話していました。これに同意しつつも一度出してみようとなり zer0-star が Mo を写経して提出するも案の定 TLE 。

kenken が G を進めるも問題が出るわ消すわのいたちごっこ、僕と zer0-star は I 問題に根本的な解決策を見いだせずただ時間が経っていきます。暗雲が立ち込んできます。そう、我々は──

もともと zer0shiki は上振れと下振れがはっきりしているチームで、国内予選や模擬、JAG合宿でも上振れれば国内トップ 10 クラスのパフォーマンスを叩き出せるものの下振れた際は持ち直せず水色パフォくらいに終わっていました。 WADATSUMI と渡り合ったり上位に入るためには上振れを引くのが大前提であり、かつ下振れに陥った際に持ち直せた試しがないため、この状況は絶望的です。

5 完のまま順位表が凍結します。

I 問題

下振れてからの立て直しが成功した試しはない、でもやるしかない。考察を続けているうちに隣接する約数を左下にとるいくつかの長方形で作用表せることに気づきました。

求めるのは max なのでセグ木で行けそうだと思い立ち、 zer0-star の同意も得られたので kenken の G を奪って実装。これで AC を取ることができました。

D 問題

ここで力尽きそうになるも順位表を見て WADATSUMI が凍結前 7 完。我々は 8 完することが勝ちの最低条件となっており凍結前の状況から解くべきは D と G であると判断、あまりに解ける見た目をしていませんが kenken が G を通し切ることを信じて zer0-star とともに D に向かいます。

考察をしているうちに辺どうしにいい感じの一対一対応が取れるならその積でいいことを思いつき、さらに辺 $1-2$, $2-3$, $\cdots$, $(n-1)-n$ に一対一対応させるように並び替える方法がちょうど 1 通り、さらにそれが区間スケジューリングで実装できることを突き止めます。 構文解析だけ zer0-star に書いてもらいそれらを書くと AC できました。

回顧

終わってから振り返ってみると、セグ木を思いついてからのパフォーマンスは僕の短くないキャリアの中でも経験のない凄まじいものだっと思います。解法を思いつくのもそうですが、実装もミスがなく全てを一発で書き切るのは再現できる気がしません。負けたら終わりの状況が生んだ意地や執念なのでしょうか？負けたくなかったのは勿論ですが、ここまでさせる程の強烈な思い入れは ICPC になかったはずなので僕の中でもまだ説明がついていません。

G 問題

その執念をもってしてもチームメイトにラストパスを出すまでが精一杯でした。 D を通した時点で残り 10 分ありましたが僕はここでダウン。 kenken に後を託します。

しかし AC に至らず。

終了

最終結果は ABCDEIK の 7 完でした。 WADATSUMI の凍結前と同じ完数でありペナ差で劣るため自視点で負けが確定してしまいました。

結果としては上振れと下振れの中間くらい。下振れを引いたときにここまで立て直せたのは初めてです。立て直すためにこれほどの執念を要するあたりこのパルプンテっぷりはどうにもならないのでは？

YesNo を見ると WADATSUMI が凍結後に G を通し 8 完していました。我々が G を通せていたとしても負けていたようです。素直に負けを認められるだけ G を通していてくれて有り難いですね。

懇親会

終了後は会食で様々な人とお会いしました。

緑の T シャツを着ていたのは西崎先生が集めたスタッフなのですがほぼ全員が traP であり見知った顔の多いこと。そのほかにも本当に書ききれないほどの人と会話しました。話題の多くが昔話になってしまったのはあまり良くないことですが･･･

撤収の際にスタッフが風船を割りまくるのですが、スタッフで来ていた jupiter_68 君がわざわざ僕の前に風船を割りに来ました。コラ～！
仕草はクソガキですが未来の科学大を背負うであろう期待のB1です。みんな覚えてね。

最後に横浜を観光して帰りました。

旅路の果て

これにて ICPC Yokohama Regional 2024、ひいては僕の学生競技プログラマーとしての 9 年間が終わってしまいました。高校の先輩や部活の顧問の先生のすすめで JOI に参加したのが始まりで、Nafmo2 らと校内争いを繰り広げたのが 7 年も前ですね。その後東工大に進学し traP アルゴリズム班班長になり ICPC に参加することになりますが、東工大の Yokohama 進出争いは高校の学内争いと比べ圧倒的に、とにかく熾烈でした。結局 Yokohama に初進出するのに大会でも異例の 6 回を要しました。それでも 1 回でも来ることができたのは本当に良かったです。欲を言えばその先も見てみたかったですが、敗因が実力不足だった以上ここが終わりであることは受け入れます。

9 年も続けるくらいなのですから、競プロは楽しい！学生競プロer は引退ですがもちろん競プロは続けます。今後は社会人競プロerとしてお会いしましょう。今までありがとうございました！そしてこれからもよろしくお願いします！

おまけ

もっと良い写真はなかったんですか？