feature image

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

ICPC 2025 国内予選 参加記(zer0-star, zer0shiki 視点)

2025年度の ICPC (国際大学対抗プログラミングコンテスト)国内予選にチームzer0shikiとして参加して、結果は全体10位・学内3位でした。

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

ICPC - 東京科学大学デジタル創作同好会traP
『デジタル創作同好会traP』は、東京科学大学で活動するデジタル創作・プログラミング系サークルです。ゲーム制作を中心に、アプリ、音楽(DTM)、グラフィック(イラスト、3Dモデル、ドット絵、動画)などのクリエイティブ活動の他、競技プログラミング(競プロ)やCTFも行っています。
タグ"ICPC"が付けられた記事一覧

登場人物

敬称略でいきます

zer0shiki

昨年と同じく黄黄青の編成。0214sh7(すく)が抜けてcomaviusが加入したかたち。

他チームのみなさま(メンバー略)

運営陣

老人

科学大[1]のICPC事情について

これは東工大・科学大の参加記で無限回言及されていることではありますが、それでも書きたくなるくらい全部に重大な事情なので書き残しておきます。

科学大のみに絞った順位表 デカすぎる!正規の大学とやり方が違う!

科学大の特徴として、層が異常に厚いです。それも、上から下までずっと厚いです。traP[2]で定期的にICPC練習会を開いていたり、競プロerと競プロ初心者・非競プロerの距離が近いことがここまでの層の厚さを生んでいると思っており、それ自体はとても喜ばしいことです。しかし、予選突破争いをする立場としては、非常にヤバいです。

まず、ホスト枠があるとはいえ、予選突破が高確率で4チームのみなのはヤバいです。科学大の有望チームは5チーム(ACORN, AMATSUKAZE, HAOU KAYAMA, o3-kayama, zer0shiki)あり、その5チームないし下3チーム(ACORN, HAOU KAYAMA, zer0shiki)での最下位争いをすることになります。

さらに、その下のチームも、枠争いに全然参加できるだけの力を持っており、常に後ろから刺される危険性は付き纏います。

助けて〜

しかし幸いにも、全体10位以内に入ったチームは無条件で突破となります。そのため、10位以内に4チーム入ることができれば、ホスト枠と合わせて5チーム仲良く突破することができます。(理論上11チームまで可)

そうなってくれれば、本当に嬉しいです。AMATSUKAZEのnoya2さんとは帰る方向が一緒なのでよく喋りながら帰ってたんですが、頻繁に「東工大[1:1]から5チーム出たらアツいね〜」という話をしていました。

ちなみに、「上から下までずっと厚い」といっても下が厚い分には関係ないのでは、と思いきや問題文の印刷に時間がかかります。業務用のデカいプリンターを借りてきていたのに!

模擬国内より前

時は4月、卒業してしまったすくさんに代わり、zer0shikiは新たなメンバーを求めていた。なぜか今年は去年のチームをほぼ続投みたいなチームが多く、すでにそのようなチームが人を引き抜いていたため、メンバー探しは難航を極めた。

なんやかんやあって、5月の頭にcomaviusくんをチームメンバーとして迎え入れることが決まった。

traPの練習会に参加したり、UCに参加したり、独自に適当なセットを走ったりしていた。

模擬国内

本番と違って早めの時間帯からなので、3人で集まってこころ(台湾まぜそば)を食べた。

こころ

とりあえず一番後ろの席(使えるスペースが大きい)をとり、本番で使う計算機室のPCの環境をいじっていた。幸い昨年のときの環境がそのまま残っていたため、ファイルを多少整理する程度だった。

コンテスト中は、Eまでこれやるだけじゃね?と言って解いていたらF以降解けなくて大変なことになってしまった。

終わった後もしばらく意気消沈していた。

国内予選より前

あと1週間もないということで、頻繁に集まって(時には他のチームとも)練習をしていた。

noya2さんと会うたびに、「まだ来週だから大丈夫」「まだしあさっての次で名前も知らない日[3]だから大丈夫」「まだ今日と明後日の間に明日という無限があるから大丈夫」という話をしていた。

前日は特に集まりはしなかったので、エルデンリング(ナイトレインではない)とスト6をしていた。

冷蔵庫に消費期限が切れててヤバそうな肉があったが、味噌漬けだからと言い訳をして、じっくり焼いて食べた。(前日なのにバカすぎる!)

国内予選当日

やばい!

とうとうその日が来てしまい、激焦り

とりあえずゆっくり(10:30ごろ)起床をしてゆっくり(13:50ごろ)食事をした。この日もこころ(台湾まぜそば)を食べた。

こころ2

前日のヤバ肉の影響もなく、むしろ台湾まぜそばを食ったにしては胃腸の調子が良いくらいだったので安堵

kenkenが模擬と同じ席を確保していたので、とりあえずリハーサルにログインしたり、oj-bundleをインストールしたりしていた。

気付けばもう本番2時間前を切っており、やばい!

他のチームを見ると、寿司打をやっていたり謎のタイピングゲームをやっていたりしたので、こちらも漢字でGOをすることに。覚えてないけど去年も予選直前に漢字でGOをしていたらしいです 笑

直会(なおらい)という言葉が出題されて、chokuaiだ、と思うなど

そろそろ時間も近いし終わるかと思ったら最後の問題の答えがボロカスだかなんだかで、さすがに縁起が悪いぜと思ってもう1回やった。

パソコンとスマホの電源を切り、出陣!

事前にAをzer0-star、Bをcomavius、Cをkenkenが解くことに決めていたので、まず俺がパソコンに座ってAを開いた。

A

見た瞬間解けたが、 かけてもいいのは国内予選が終わるまで気付かなかった(0:02)

問題文は2並列で表示していたので、とりあえずCを見とくことに。

B

Aをやってる間に解かれてたが、なんかややバグってそうだった。まあ一瞬で直ってAC(0:07)

C

kenken「まあ普通にやればよいです」俺「そうですね」(0:14)

D

ABCの実装問みたいで嫌だなあ怒と思いながら睨んでいると、comaviusから「1行目・1列目と同じであるか全部反転させてあるかのどちらかなので、01列に帰着できます」と言われ、「確かにそうであるし、判定した後は1行目・1列目をその01列として使用できるなあ」と思った

そして「01列が入れ替わるインデックスに変換すれば判定できます」とも言われて、そのように実装できたので、意気揚々と提出するとRun-Errorで絶望

う〜んと思いながら眺めると初期化してないstringの要素に代入していることが判明、逆に手元で通るのヤバいだろと思いながら再度提出すると、またしてもRun-Errorで絶望

2ペナ最悪すぎると思いながらひとまずEに代わってもらう。

とりあえず印刷してグッと睨むとバグを発見できたので直してAC(0:43 +2)

ここ反省ポイント

とりあえずEとFが解けてそうなのでGを見ることに

E

Dが沼ってて見てないけどcomaくんが解いててくれました(1:03)

F

これも全然見てないけどkenkenが解いてくれました(1:09)

G

3次元幾何やりたくね〜と思いながら眺めていると、これ幾何的考察を使うだけで幾何じゃねえな?と気付く

並行な辺の間に面が貼られているときは面の数が1減ることに気付くが、辺の伸び縮みなどを考えると対応する辺のペアを考えるのが難しそうで、よくわからず

comaくんから「辺の長さは関係ないです」と言われるも、俺は「そうなんかなあ」と言っていた(アホ) kenkenに聞いたところ、辺の長さが変わっても同相変形なので答えは変わらないらしいです

なんかどの辺とどの辺を対応させるかでDPとかすればいいんかなあとか思ってたら、しばらくしてcomaくんが「これ並行になる辺があったら必ず1減るので、setにぶちこむだけでいいですよ」と言いだして、俺に入力を整数で受けとるパートの実装を依頼してきた。

自信ありげだし確かにそうかもなと思いつつ実装していたが、それで通るなら簡単すぎね?G問題やぞ?と思って半信半疑だった。

comaくんに交代して、案の定すぐに実装が終わったためとりあえず出してみたらACで、そんな〜 笑(1:46)

普通のセットだったらこの速度でGまで解ければ激アツなのもあり、通った瞬間みんなで暴れてしまった(昨年の反省さん......)

このあたりでこのセット、何か変......?状態だった(後で聞いたらEくらいからその兆候があったらしい)

H

Gの考察と同時に考察してもらっていた。

(())があればその間は通り放題なのと()()...()のようになっている区間は無視できることを使えば、がんばれば解けそうという話をした。

解けそうなので、完全に任せてGが終わった後はIの方に移ることにした。

Iを眺めて唸ってる間に頑張って実装をしてもらい、見事AC(2:05)

この時点でうっかり歯茎を出しそうになるが、冷静に順位表を見ると、全完が4チームもあり、ワンチャン全完しないとまずいかもという気持ちになったため、マジでIに全力を注ぐことに

I

Hをやってもらっている間にいくつか考察のパーツだけは生まれていた(同じ色の点を追い越すことはないとか)ので、とりあえず色をdistinctに変換する処理だけをkenkenに実装してもらっていた

一度動かしてしまった後でも過去改変できることを生かして貪欲できないかとか変なことを考えていると、comaくんから「色 について のペアの正しい位置関係からのズレを , のペアと交差していないペアで左側と右側にいるものをそれぞれ とすると 自明な下界 + が答えです」という考察が飛んでくる。

そうなんだ、と思っていたら実装を依頼されたので、やる

ちょうど交差しないペアの数え上げの実装が終わったタイミングで、上記の考察に嘘があったことが判明する。

とはいえちょっと修正すればよさそうなので修正してみたところ、全然合ってなさそう......

そもそも今実装がどうなっているかというと、

として が答え、みたいな実装だった。(詳細は違うかもしれません)

とりあえず2で割る必要ないんじゃね?とか言って に変えてみると、なんとサンプルが通り、コーナーっぽいケースも試してみたところ手動解と一致した!

しかし、デバッグ出力を見ると、試した全部のケースで が0になっており、明らかに異常な挙動を示している気がしてヤバすぎる!

とは言え残り16分ほどしかないのでガンガン提出していくフェーズだという合意がとれたので、とりあえず提出してみることに

内心はこれで合うわけないよ〜とか思っていたところ、なんとAC(!?!??!???!)(2:46)

国際大学対抗ギャグコンテスト笑

(というか今考えると は全然自明な下界ではない)

とりあえず順位表を見るとたしか7位くらいで、ペナ差でいくらかまくられるとしても予選落ちはないだろうという判断で、歯茎を剥き出しにした。

ワクワク順位表観戦タイム

とりあえず科学大のメンツに注目すると、o3-kayama, zer0shiki, ACORNが全完、AMATSUKAZE, HAOU KAYAMAが8完で、場合によってはAMATSUKAZEが落選、5チーム通るなどの番狂わせがありえて激ヤバということが判明する。

その後しばらく大きな動きはなかったが、終了2分前ほどになって突如AMATSUKAZEとHAOU KAYAMAがIに提出を投げ、うおおおおと思っていたらAMATSUKAZEがAC、HAOU KAYAMAがペナで一気に盤面が動いた。

そしてこの時点で学内4位のACORNが10位だったため、このまま行けばHAOU KAYAMAまで通過可能で、夢の科学大5チームか!?とざわめきが走る。

しかし直後THSがIに提出を投げ、どうやらACなら10位以内に入られそうという状況で、どうか通らないでくれ〜と祈る時間が存在した(THSのみなさますみません🙇🙇🙇)

しかし、我々にとっては残念なことに、ACとなり、HAOU KAYAMAは敗退となってしまった。

最終結果は、冒頭の画像の通りだが、

の4チームが通過となった。

国内予選の後

同部屋(人数が多いため2部屋に分かれていた)のACORNやAMATSUKAZEと喜びを分かち合ったり、Tsukuyom1に祝福されたりしつつ、感想戦(主に、今年のセットヤバくね?という話)をしたりツイッターなどをしたりしていました。

その後は科学大競プロer御用達のカレー屋さんに行き、ほぼ貸切状態の中大量の注文でキューを破壊するなどしていました。

カレー屋さん

そしてなんと、カレー屋さんにすく(0214sh7)さんが来ており、激アツの邂逅を果たしたのでした。

うれぴ ありがとうございます🙇🙇

あとは、カラオケに行ったり、ICPCとは全然関係ない飲みをしたり、労働をしたりして今日に至ります。

あと今この参加記を徹夜で書いているので日本語がヤバい

感想

今年は例年から見れば異常事態とも言えるようなセットで、簡単めであるだけでなく、ギャグだったり、高難度重実装や高難度幾何・構文解析が無かったり、謎のセットでした。(それでも上位勢がちゃんと上の方に来ているのはさすがだなという気持ち)

まあ結果通ってるからオーライなのですが、どういう意図があったのかはちょっと気になるかも(henoさんのツイートを見ると、5チームくらいは全完が出ることは想定どおりそうで、明確にこれでよいという判断があったことになる)

ところで、企業賞はもらえませんでした(よこせ怒怒怒)

感想1

競プロはずっと趣味でやってて、ICPCも当初はせっかくだし出とくかくらいの気持ちだったのですが、いつの間にか選手としての気持ちでICPCをやっていて、

みんな、好きって言うから
やってみただけなんだけれどさ
きっかけは誰しもそんなもの

気づいたら私にも
プライドなんて芽生えちゃって
本物のアーティストね?

tokiwa, 星宮とと『Vanguards』

って感じ!

あと、チーム科学大として他大に勝ちたいみたいな気持ちもあって、それで言うと今回は割と良かったんじゃないでしょうか

感想2

そういえば東大のチームが全員ずっと情報を隠匿していた(今もしている?)のはなんでなんですかね?知ってる人がいたらこっそり教えてください

おわり

12月のYokohama Regionalではplayoffへの出場を賭けて争うこととなります。それまで応援よろしくお願いします。


  1. 東京科学大学 理工学系(旧東工大)の学生は、東京科学大学(特に理工学系)のことを、基本的に身内の間では東工大と、対外的あるいはちゃんとした雰囲気を出すときは科学大と呼ぶことが多いです。ギャグの文脈ではScience Tokyoと呼ぶこともあります。東科大とは言っていません(すいません) ↩︎ ↩︎

  2. traPを知らない競プロerへ 東京科学大学デジタル創作同好会traPは、科学大最大規模のサークルです。学内の競プロerの多くが所属しているためICPC関係のことはtraPで音頭をとってやっています。競プロサークル以外の側面も大きいため、競プロ初心者・非競プロerにもICPCに参加してみようかなと思ってもらう機会になっています。 ↩︎

  3. やねあさって、やのあさって ↩︎

zer0-star icon
この記事を書いた人
zer0-star

インターネット以外全部したことあります

この記事をシェア

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

関連する記事

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 アナリティクスについて 特定商取引法に基づく表記