ICPC 2024 Asia Yokohama Regional 参加記

ICPC 2024 Asia Yokohama Regional にチーム Screenwalkers の一員として参加しました。 練習や本番の様子を記しておきます。

ç·´ç¿’

特筆すべき点はあまりないかも。自分が駒場に、双子が本郷に通っていることもあり対面で集まれない日もそこそこ多かった。ただでさえ東大の1年は授業で忙しいのに、11月には駒場祭があり、所属している大学合唱団での練習も増えていたので、競プロに注力しきれなかったのはちょっと心残り。

バチャのセットは大体 E869120 さんが選んでくれていた。UCup や海外の Regional を解くことが多かった。毎回というわけではないが、そこそこ良い成績を維持できていたと思う。

全員 JOI 育ちなので得意分野が被っているかと思いきや意外とそうでもない。大雑把に言うとグラフ(特に木)・データ構造が自分、幾何・構築・ad-hocが square さん、文字列・数え上げ・インタラクティブが E869120 さんという感じなのだが、全員オールラウンダー寄りなので明確に分類できない問題についても3人の能力の和集合をとると良い感じに対応できる。そのため、問題とのマッチングがうまくいった回は大体が成功に終わった。

国内予選

時系列がごちゃごちゃになっているが、7月の国内予選についても少しだけ言及しておく。

国内予選ははっきり言って最悪の結果だった。1位を取る気持ちで臨んだにもかかわらず得られた結果は1位と2完差の11位。敗因は色々あるが、

  • 本番の環境が特殊だったにもかかわらず、前日までに諸々の確認を行うのを怠った。
  • 国内予選ルールでの練習が少なかった。3時間という短いコンテストに合わせた戦略を準備しておくべきだった。
  • コンテスト数日前に E869120 さんに色々あってチーム全体としてメンタルが整っていなかった。

などだろうか。この失敗を踏まえて、8月頃からは練習が多くなった。

Taichung Regional

実は、Yokohama より前 (11月上旬) に台湾の台中市で開催された Regional にも参加していた。もちろん WF に参加できる可能性を高めるという意図もあったが、うちのチームは (国内予選での失敗もあり) 本番に弱いのではないかという不安があり、経験を積むという目的も大きかった。

運良く台湾の強豪 std_abs を抑え優勝することができたため、Yokohama で SPJ または HHIJKT が優勝しなければ WF 確定という非常に心強い状況になった。この成功でメンタル・本番力・チーム力すべての成長を実感でき、良い流れに乗って Yokohama に向かうことができた。

Yokohama Regional

本編

前日の夜はあまり眠れなかった。緊張のせいなのかもしれないが台湾ではしっかり眠れたんだよな……。とはいえ特に誰かが体調を崩すということもなく、会場にも時間通りに到着することができたので第一関門は突破した。

コンテストは 20 分ほど早めに始まった。これが ICPC Timer というやつですか？最初のフォーメーションとしては、自分が環境構築、E869120 さんが A 問題、square1001 さんが B 問題となっていた。B->A の順に一発 AC し 2 完時点では 1 位になった。流石の早解き力である。自分は C~L から問題文が短いものを読んでいたのだが、3 問目くらいに読んだ K が簡単であることに気づく。実装して提出したがWA、え〜〜〜〜〜〜〜。序盤でロスするとかなりもったいないので、目視デバッグより安全に AC を取るべくランダムテストを実装。この見切りとテストの実装速度は良かった。実行してみるとすぐ落ちるケースがみつかり、試してみるとなんと REP マクロの罠を踏んでいた。#define RREP(i, l, r) for (auto i = r - 1; i >= l; --i) と書いていたんですね。皆様なら何がヤバいかお分かりでしょう。こんな初歩的なミスでペナ 20分 + 10分程度失ったのはかなり痛いが、それでもSecond ACだったのは安心。この間にPenguin FeedersがE,Iを通していて速すぎだろと思ったが、双子が爆速でI->Eの順に通してくれて心強かった。その間に自分はG,Hを少し考えていた気がするが、読むだけ読んでスルーしていたCが通されていたのでIを通して帰ってきたE869120さんと少し考える。最短路木がそのまま答えになったら良いんですけどねえ、などと話していたらE869120さんが証明してくれた。AC。この間のどこかのタイミングでsquare1001さんがLを実装していた気がするが、どうやら嘘解法だったらしい。ABCEIKの6問とその他で難易度に崖があり、ここで前半戦終了という感じか。

幾何担当のsquare1001さんがFで賭けにでていたので残った二人でG,Hあたりを見る。Gを読んで、真ん中一列の矢印の個数の差で左右どっちか決まるから二分探索できるんじゃないかということをE860120さんに伝え解法を詰めてもらうが、今思い返すとこれは最初のアイデアの時点で嘘解法で、これをもとに考察・実装を任せてしまったのはかなり痛手。Fは通らず、Gも実装にかなり時間がかかり、詰まってしまった。そこで自分がAMATSUKAZEに解かれていたDに移ると解けたので実装することに。3人が別々の3問に取り掛かるというのはかなりリスクが大きい(特に、全員詰まると破滅)が、Dは一発で通ったので安心した。その後双子にはF,Gを頑張ってもらいつつ自分はHを考えたりJの双対を取ってみたりしていた気がする。このあたりでGが嘘解法だったことが分かったので考察しなおす。1列見るのではなく2列見た方がよいことに気づき再度E869120さんにアイデアを投げ、考察してもらう。Lがしばらく手つかずになっていたことを思い出し考察してみると、時間はかかったものの解けた気になったので希望を持つ。しばらくするとsquare1001さんがFを通し、自分のLも(1ペナの末だが)通ったので勢い付き、今度こそ正しい解法を詰めてくれていたE869120さんにGを実装してもらう。AC。この一時間でF,G,Lの3問を通すことができ、完数的にもペナ的にも優勝がかなり堅くなった。自分がLを通した後square1001さんとJを考えていたのだが、square1001さんが今回のコンテストで一番の天才をしてJの正しそうな解法を生やしてくれたので、自分が正当性を検証しつつGが通った直後から実装してもらうことになった。

最後の一時間。square1001さんはまずJの実数の場合を実装。自分とE869120さんでHを考え、これ絶対Y.Y.さんだろマトロイド交叉だろなどと話していた。マトロイド交叉ということは絶対マッチングに似た解法で解けるはずということになり、それっぽい増加路のようなものを見つけて改善する方針をE869120さんから提案された。自分はこういうE869120さんの勘のようなものを会得できていないので正当性は分からなかったが、残り時間も少ないのでJが通ったらこれを実装することになった。その間にsquare1001さんがJの実数の場合で正しい答えを出力することを確かめていたので、お祈りしながら有理数の場合を実装してもらった。2回提出してWAだったが、ランダムテストをかけたり印刷したコードを残りの二人で読むなどしてデバッグに全力をかける。なんと残り15分でACした。あまりに強すぎる。最後まで諦めずE869120さんがHを超絶熱烈実装していたが間に合うはずもなくコンテスト終了。凍結された順位表から分かる範囲でも、少なくとともWF進出は確定していた。しばらくチームでお互いを労っていた。

Yes/Noにより無事優勝が確定。最後JがYesだった時に会場が沸いたのが嬉しかった。

おわりに

Regional 2大会優勝を果たし WF 進出を決められて本当にうれしい。国内予選のときからかなり成長したと思う。チームとしてさらに改善できる点もあるし、自分としてももっと強くなれると思っているので、今後の練習も頑張ります。WF も見ててくださいね。

(宣伝) 直前すぎるのですが、今週末12/28に自分が所属している東京大学柏葉会合唱団(@HakuyoChoir)の定期演奏会があるので、興味があればお越しください。チケットはこちら