feature image

2025年7月5日 | ブログ記事

ICPC 2025/26 模擬国内+国内予選参加記(shobon 視点)

ICPC 2025/26 の模擬国内と国内予選にチーム AMATSUKAZE で参加しました。メンバーは shobonvip、noya2 さん、こめだわらさんです。国内予選は8位で、横浜regionalへの出場権を獲得しました!

この記事を読んでいる人はこの記事も読んでいます

ICPC国内予選2025参加記(Astral__2視点)
ご挨拶 こんばんは(∵) ICPCの模擬国内予選・国内予選にACORNというチームで参加しましました。結果、ホスト校枠でなんとかYOKOHAMAへの進出が多分決定しました。ありがとうーーーーー チーム編成 * Astral__ ... 7/3まで週4でインターンやってました * cho57020 ... 我がチームの最終外交兵器 * otoshigo ... ラストイヤーオブザイヤーノミネート 模擬国内予選参加記 いつもありがとうございます 関わったのだけ書きます A こういう短い問題文が好きです D otoshigoさんから良さそうな解法をもらったので、良さそうオブザイヤー2025を進呈しました F 典型~と言っていたら解けたけど、見た感じ運が良かったみたいです H A~Fまで解いた時点で順位表を見るとびっくり、FよりHのが解かれてるみたいです。これ通さないとな~という雰囲気が漂っています。しかし残念ながら、我がチームには数学に強い人が居ません。えーーーー リザルト 校内2位で突破ライン

それまで

AMATSUKAZE は三年の歴史があります。一昨年は shobon, noya2 さん, ebi さんのチームで、一昨年で ebi さんが引退、去年は Hemimor さんが引退しましたが、そこにこめだわらさんが入ってくれました。今年は自分が引退です。

メンバー

科学大の ICPC 事情

科学大からは 28 チーム出ましたが、今年はその中でも最も強いチームが 5 チームありました。AMATSUKAZE はチームレートでいえば科学大一応最強ですが、負ける確率がかなりあります。そもそも国内予選自体の性質としてパフォーマンスの分散が激しいということがあります。最強無敗チームのスクウォでさえ国内予選を落ちかけた話は恐怖です。

練習

国内予選のために毎週1回くらい集まって3時間コンテストを走りました。traP でも ICPC バチャが開かれていたのでそれに参加しました。

模擬国内

模擬国内は5位(出場チームの中では3位)でした。担当は A,D:shobon, B,E:noya2, C,F:こめだわら(協力あり)、その後は不定という感じです。最初は印刷が届くのに時間がかかるので実装中に画面を半分に分けて次の問題を見せています。

A~C

mex を求めるだけでした。答えは n+1 以下なので で求めました。B, C も問題をチラ見しましたがそんなに難しくなさそう。(A 0:01, B 0:05, C 0:09)

D

インタラクティブです。 noya さんも読んでましたがやることはすぐ分かったので伝えるとよさそうと言われ実装したら通りました。(0:14)

E

Eは noya さんの担当ですが構文解析なので自分がやることに。結局二分木ができるのですが、各葉っぱに対して(到達可能なら)根からそこまでのパスにある変数名の種類数を求めればOKです。ちょっとバグりましたがなんとか通りました。(0:37)

F,H

F はかなり詰まったようです。みんな困ってるようなので自分は問題を聞いたのですがしばらくしてnoyaさんが分かったようなので G, H の問題を眺めました。G 問題はやばそう。H 問題もやばそう。

H 問題で素数の場合原始根を用いて考察。こめだわらさんと協力して、 CRT も使うと完全に問題が解けることが発覚しました。 F 問題がバグったようなので印刷をして H 問題を書き始めます。頭がバグり F 問題と交代します。実際の実装でも原始根を取り出してしまったのですが、よく考えれば別にいりませんでした。また交代し H 問題を書き上げ AC しました。(2:10)

F問題の印刷を自分も眺めバグを探します。DP遷移が間違ってることに気付き noya さんに伝えたら間違っていたらしいです。結局そこだけがバグっており F 問題を AC しました(気付いてよかった)。(2:22)

G

G問題はやばそうなのですが、ほぼ考えるパターンがないということが発覚。しかし角に点がある場合を考慮できてませんでした。(4パターン程度ある)こめだわらさんが詰められたようなので実装開始。しかし、バグらせたまま終わってしまいました…… 方針はあっていたらしいです。

I も典型ですが間に合わず。

国内予選

13時半起床、14時大学到着。その後ご飯を食べ、リハーサルの「席替え」が全然解けず(最後は解けた)、「今日はだめだ~」みたいに言ってました。

A,B,C

A問題を見ると、因数分解すると明らかに が答えなので書きました。(0:01) B 問題、C 問題もすぐ通りました (0:05, 0:10)

D,E,F

D 問題は明らかにペナルティが出やすい問題なのですが、ペナルティは絶対避けたかったため慎重に全パターンを整理しました。焦っていて noya さんに相談したりしました。頑張って書いたら250行くらいになってしまったのですが、もっと賢いやり方があったようです(泣)バグったのでFと交代したりもしました。結局1発で通ったのでよかったです。(0:45)
F もその後すぐ通りました。実装はこめだわらさんです。(0:53)
E 問題は に対し noya さんが線形時間で解いたので noya さんが心配して解法を確認しました。よさそうだったので出したら AC でした。制約の小ささは時に罠。 (1:03) すでに6完が多く一桁の下位ではありますがここから相当な難しさになるのでかなり有利です。通常の国内予選であれば…

G

G 問題は凸多面体で、角度の累積和を取って辺や点などを対応していくのかな~という感想でした。解けたつもりでしたが実装しても合わないので noya さんと交代して 1 から書き直してもらうと通りました。なんか自分の考察にちょっと嘘があったようです。(引退)(1:40) この時点で順位は7位とかで焦りました。

H

H 問題はこめだわらさんがすでに解けていると主張。問題を見て解法を聞くとよさそうでした。UnionFindとかでやると楽そうと言うとなぜか驚かれその実装が始まりました。
その間に I を見ます。これは不可能と思いきや、考察を進めると転倒数を求める問題に帰着します。ただし、 回求める必要があり、適切な差分更新が必要でした。領域木は重いですがnoyaさんがそれで解けるといい詰め始めました。H問題はバグったらしいですが、印刷を見ても要因がわからず(よさそうだった)。結局こめだわらさんがバグの要因を見つけ直して出してみると通りました(ある配列の初期値がバグっていた) (2:18)

I

I 問題は noya さんが書くので見つめました。差分更新の厳密な式は自分も把握していなかったのですが、書き終わると実行してみて合わず。デバッグすると、いろいろと差分更新が足りなかったりバグっているらしかったです。その間にタイムリミットが迫っていますが、科学大の3チームが全完しさらに焦ります。その時の順位は全国12位/学内4位くらいで、一応通過ラインではありますが全完しないと負けの可能性が高いです。
こんなに通っているのに複雑な差分更新のはずがないとサンプルを見てみると、どこを切り開いてもコストが一緒になりそうで、「実はどこを切り開いてもよい」というエスパーを立てて間に合わなそうならそれを提出したいと言いました。そして、I がバグっている間に I のエスパーコードを書きます。終了 4 分前くらいにエスパーコードを書き終えましたがバグっていました(泣)結局 I のコード 2 つを並列に進めますが、終了 2 分前に自分のコードのバグに気付き直すとサンプルが合ったので出してみるとACが出ました(奇跡) (2:58) 全国7位/学内2位となり、勝ちがほぼ100%確定しました。
提出後は全国上位10チームに科学大が4チームおり、ホスト枠の+1で5チーム横浜にいけるという夢の状況が一瞬うまれました。しかし最後の最後に1チームが逆転全完し HAOU KAYAMA が敗退することになりました……。

反省

D はかなり複雑な実装をしてしまいましたが、テクニカルなことを思いついて実装できるかというと、まあできるけどうーんという感じです。ペナなしはよかったです。
G は反省です。角度の変化は 180度-(それ) なのに気付きませんでした。内角に引っ張られた……
I は ACORN から話を聞きましたが円の弦の交わりと聞いてびっくりしました。言われればそうだけど……天才?我々は転倒数しか見えていなかった。
まず科学大に来る時点で優秀なのですがその中でも天才ばかりと戦う必要があります。天才はカバーしにくいので横浜regionalは対策しやすい競プロ知識と経験で勝ちにいきたいと思います。

さいごに

国内予選・模擬国内のスタッフ、さらに科学大のICPCスタッフにとても感謝です。引退したら来年スタッフになろうと思います。横浜でも頑張ります!

shobon icon
この記事を書いた人
shobon

黄溜まりの   自明非自明      最上川

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2023年9月26日
traP コンペ 2023 夏 sponsored by ピクシブ株式会社 運営後記
abap34 icon abap34
2023年7月13日
アルゴリズム班はやとき王選手権「競(けい)プロ」を開催しました!
abap34 icon abap34
2022年10月11日
アルゴリズム班にKaggle部を設立し、初心者向けデータ分析体験会を開催しました!
abap34 icon abap34
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2023年7月5日
Kaggle部で機械学習講習会を開催しました!
abap34 icon abap34
2023年4月29日
CPCTF2023 PPC作問陣 Writeup
noya2 icon noya2
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記