ICPC国内予選2024参加記（0214sh7視点）

2024 年度の ICPC （国際大学対抗プログラミングコンテスト）国内予選に参加しました。メンバーは

0214sh7 (M2･数学･青)
zer0-star (B3･数理計算･黄色)
kenken (B2･数理計算･黄色)

です。明らかに異物がいます。

6 回目の参加

ICPCは規定により M1 までの 5 回参加することができます。しかし、参加資格をよく見ると

下記2条件の少なくとも1つを満たしていること。

大学または短期大学に入学、あるいは高等専門学校4年次に進学したのが、2020年かそれ以降であること。前記の入学・進学が複数回ある場合にはもっとも早いものが、2020年かそれ以降であること。

生まれた年が2001年かそれ以降であること（注：年度ではなく年であることに注意）。

とあります。この規定によると、

現役で入学
早生まれ

であれば 6 年目の参加が可能になります。ただし

過去のアジア地区大会の参加回数が5回未満であること（※国内予選のみの参加を含む）。

というルールにより参加回数はどうしても 5 回までであり、 6 年目に参加するためにはどこかで参加を諦める必要があります。このことは以前からよく知られていました。

しかし、2019年末からのパンデミックにより、

ただし：
2021年3月に実施された ICPC 2020 Asia Yokohama Regional および2020年11月に実施された国内予選については、1 回と数えない。
「2022年3月に実施された ICPC 2021 Asia Yokohama Regional および2021年11月に実施された国内予選」と「2022年12月に実施された ICPC 2022 Asia Yokohama Regional 及び 2022年7月に実施された国内予選」を合わせて 1 回と数える。

というルールが追記されました。これにより

現役で入学
早生まれ
2020~2022シーズンに参加

を満たせば 6 回目の参加が可能になります。

このルールの適用例は歴代でも珍しく、少なくとも東工大において 6 回目の参加例は昨年の eiya に続き 2 例目です。実は noshi91 や tatyam もこのルールの対象者でしたが、この二人は WF を使い切りルールの適用外になりました。

そんなわけで、そもそも同輩との参加が絶望的です。確かに年は離れていますが一人は昨年もチームを組んだ zer0-star ですし、ここに至るまで浮くこともなかったと思います。

東工大事情

tonosama がいなくなったとはいえ、ホスト校で枠が増えているとはいえ、それでも東工大は暖色が多く横浜進出争いは熾烈を極めます。

上位チームの色分布を書くと、

赤橙黄
橙橙黄
黄黄黄
黄黄青
黄青青
青青青
青青青
青青青
･･･

といった感じで、 3+1 チームが通過できるだろうという下馬評でした。traP全体練習や模擬予選の結果から僕の予想は「AMATSUKAZEとBocchi The Techが高確率で通過し、WADATSUMI･zer0shiki･ACORN･LastTsubameが残り2枠を争う」となりました。

screenshot_20240706-192921-3

ところで 29 チームは何ですか？

JAG 模擬予選

僕は A と E を担当しました( E の実装が鬼)。チーム最高レートだけあって後半の zer0-star の頼り甲斐はハンパない。この模擬予選でも F と G を倒してくれました。

ここで問題が発生します。 D 問題が通りません。考察にミスがあったとはいえリカバリーが効かず、 ABCEFG の 6 完という珍事を起こしてしまいました。

153

課題点

模擬国内や何回かの練習において

バグや考察ミスからリカバリーが効かない
実装を奪う判断が鈍い
後半思考が焼き切れている

など様々な問題が上がりました。とくに最初。
結局前日練習でも解決に至らず、問題を抱えたまま当日を迎えます。

国内予選

去年まで競技は参加せずに運営を行う人員が少なく、僕が選手でありながら運営も手伝う立ち位置にいました(アルゴ班班長だったからというのもある)。ですが、今年は tonosama をはじめ多くの引退選手が運営に参加してくれた＆後任の Sotatsu が立派に班長を務めているため、僕は選手としての立ち回りに集中できました。

リハを済ませ、懇親しつつカフェイン補充して競技開始に備えます。

kenken, Ponjuice が承認欲求モンスターを書き始め、街や本館を破壊させ始めます。なので勝手に加筆して西崎先生と熨斗袋を破壊してもらいました。(ﾉ∀`)ｱﾁｬｰ

A問題

何回かの練習ののち、僕が A を瞬殺しその合間に二人が B と C を読んでそれぞれ得意な方に割り振ることで初動は固まりました。僕が危なげなくAC。

B問題

今回は zer0-star が B を担当することに。僕は未読なので中身はわかりません。C は kenken に任せてよさそうなので B の実装に合わせて僕は D の考察に取り掛かります。

C問題

kenken が AC。この時 zer0-star は E と F を読んでいました。僕も E と F の考察をちょっとしましたが C が終わりそうだったので D に集中しました。

D問題

ここから佳境に入ります。盤面が $101 \times 101$ の大きさかつ向きも $4$ つ、この盤面からはみ出せばずっと直進し続けることから functional graph (僕は $6$ の字グラフと呼んでいます) のループを探せばいいのでそれを実装しますが、バグります。

この実装の裏で E 問題を kenken 、 F 問題を zer0-star が担当することになっており、 D を印刷し実装を kenken に譲ることを繰り返し zer0-star に手伝ってもらってデバッグが完了。なんとか AC します。

E問題

D を倒した僕は G の考察を任されます。順位表を見ていなかったので G なんだと思いつつ考察を進めていきます。 WA こそあったものの kenken が天才構築をこなしてくれました。

G問題

E を解いた kenken が G の考察に加わり、 F の考察をしていた zer0-star に実装を預けます。

kenken が加わった時点では $N$ が偶数なら半数に $+$ 、もう半数に $-$ を割り振って総和が $0$ になるかどうかの FT Robot をするのかなと考えていました。

そこで $N$ が奇数のときを考えると

	$a$	$b$	$c$
赤	$x$	$a - x$	$b - a + x$
青	$a - x$	$b - a + x$	$c - b + a - x$

として $x = c - b + a - x$ になるような $x$ があればいいとわかりました。このような $x$ の存在条件は $\sum A$ が偶数であることです。また $\sum A$ が奇数なら明らかにおじゃんなので $N$ が奇数の場合の考察が尽きました。

ここで $N$ が偶数の場合の考察が尽きていないことがわかり、前述の考察を聞いた kenken が( $\sum A$ が偶数、 $N$ が偶数のとき)

$A$ に偶数が一つでもあればそれ単体を半分にし、残りは $\sum A$ が偶数・ $N$ が奇数の場合に帰着できて Yes
そうでないとき( $A$ がすべて奇数のとき) は FT Robot で Yes か No か判定

という考察を出してくれて、

$\sum A$ が奇数なら No
$N$ が奇数なら Yes
$A$ に偶数があれば Yes
以上のいずれでもなければ、半分を $- 1$ 倍して総和を $0$ にできるかを FT Robot で(復元付きで)判定

で実装に移ることにします。 zer0-star が F にバグを埋めたようなので実装を奪って僕が G を実装します。その間 kenken には F のバグ探しを手伝ってもらいます。

FT Robot の実装をバグらせました！(そんな･･･) これにより僕が焦りで使い物にならなくなりましたが kenken が冷静にバグを潰してくれて、なんと一発で AC ！ kenken がいなければ AC できなかったでしょう、本当にありがとう。

F問題

順位表から H と I が難しいので一旦捨て、全員で F のバグを探します。結局 zer0-star が自分で見つけ、 1 回の WA ののち AC できました！

･･･終盤数十分は僕全然使い物になってないね･･･

H,I問題

7 完した時点で H と I は未読であり一応両方読むことにしましたが、順位表を見て WADATSUMI が 7 完しても捲られないことが確定したので歯茎を出し散らかしました。

終了

149

結果は全体 10 位、東工大内 3 位で文句なしの予選通過！！！素晴らしい！！！！！！！！
2019 年に東工大に入学して以来の悲願をラストチャンスでとうとう叶えることができました！！！！！！！！！

結論は上振れも上振れ。すべてが噛み合いました。各々が躍動し、D以降の 4 問全てでバグを埋めたにもかかわらず全てでリカバリーが効くという理想的な展開で走り切ることができました。

事前予想から大きく荒れることもありませんでした(新入生チームの mozu, mogamigawa, とくに gigaphox が活躍しておぢさんは嬉しい)。そして AMATSUKAZE 優勝おめでとう！

初の横浜も頑張ります。アジア行くぞ！でも行っちゃうと研究がやばいぞ！どうすればいいんだこの夏

おまけ

受け継がれてしまった悪しき文化

151-2 152-1