おここ

競プロなど

ICPC 2025 模擬国内・国内予選参加記（おここ目線）

参加記ってどんな雰囲気で書いてたか全然覚えてね～～～

パッションでいくぞ！

 

チーム紹介

今年は北海道大学から「y_1」というチーム名で参加した。全員の AtCoderID から suffix を一文字ずつ集めている。なんでこういう方法でチーム名を命名したのか忘れたな。メンバーについては以下の通り。

kouty(kouty)

y_1 の y 担当。C++ メイン。本格的にチームを組んで一緒にするのはこの ICPC 国内予選が初めて。数え上げに強い。 2024年に HokkaidoDekkaido で Yokohama Regional に行ったことがある。国内予選のタイミングでのAtcoder レートは 1893。

はと(hato_)

y_1 の _ 担当。Python メインだが今回は C++ で書いてもらった。2024年度は .Shaco でこの参加記の著者であるおここと同じチームで出た他、おここと一緒に色んな有志コンに同じチームで出ていた。高度典型・実装力に強い。過去二年 Yokohama Regional に行けそうなギリギリのところで国内予選を通過できていない。国内予選のタイミングでのAtcoder レートは 2060。

おここ (ococonomy1)

y_1 の 1 担当。C++ メイン。この参加記を書いている人。チームの中では一番 adhoc な問題が解ける考察力寄りだとされているが、本人的には考察力の安定性に自信がない。あとタイピングが速い。2023年に elephant_spaghetti で Yokohama Regional に行ったことがある。ICPC ラストイヤー。国内予選のタイミングでのAtcoder レートは 1962。

 

こんな感じのメンバーである。北大は例年ドラフトでチームを決めていて、参加する人の中で一番レート（その時点のレートか Highest かはその年による。今年は過去一年以内の Highest だった）が高い人が他の2人を指名して、選ばれなかった人の中で一番高い人が他の2人を指名して、……を繰り返していく。今年は北大に在籍していて ICPC 参加権があるHighest 黄色が3人であり、その3人でチームとなった。（今北大の競プロサークルである HCPC に所属している人で黄色中位以上がいないためせめて一人は欲しい感じはある。私含めて頑張りたいですね。）

 

チーム決め～模擬国内

チームメンバーを正式に決めたのが5月であり、そこから国内予選まで2か月もないため急ピッチで立ち回り等を練習する必要があった。基本月曜にサークル活動があり、それ以外にも何回か他の曜日にチームで集まって練習をした。国内予選や模擬国内の問題はセット通して全員が解いてないことがない（というかはと君が解いてない問題があるセットがほとんどない）ため、こどふぉの過去問の Div.2/えでゅふぉ や combined を中心にやった。一回結構立ち回りに失敗した回があり、その回では考察が割と進んだけど最終的に通せなかった問題が2問あった、さらにその2問どちらについても解法をチーム全体で共有できていなかったということがあり、これは昨年におここ・はとが属していたチームである .Shaco の国内予選の負けパターンにも共通するムーブであったため、序盤の問題でもペナが出たらチーム全体で解法を共有しようという話に。AtCoder レーティングは学内一位であり、かつ北大から1チームも Yokohama Regional に進んだチームがなかった回はかなり珍しいため、安定した立ち回りをとれば国内予選を通過できる可能性は高いだろうということもあり、一問一問慎重に行くことに。

また、最強コン予選（ARC201）ではチーム全体で5完して「これが国内予選なら……」という話が何回か出た。

 

模擬国内

国内予選の6日前に JAG によって行われること模擬国内予選。ちなみに JAG のページと言えば各々がチームのメンバーを発表？することで知られるチーム一覧のページだが、チームメンバーもこの日に書き込んだ。

 

 

このページは模擬国内の参加記も兼ねているため、模擬国内の参加記も。（下の方にある国内予選の内容と違って数日後に書いているから記憶がはっきりしてなくて分量がちょっと少ないです。）（あとここからチームメンバーの書き方がアルファベット表記・呼び捨てになります。）

開始したら ococo が A を開き、2分で AC。B を読んでいた kouty に「問題文は読めたがサンプルが合わない」と言われたため入ろうと思うが説明してもらってる間に自己解決したらしくそのまま通せた。これをやっている間に hato が C を通して、D を読むことに。「1文字目は明らかに '('  で2文字目最初の2文字で括弧列になるなら '(' だしそうでなければ ')' だなあ。あと N 回までしか聞けないらしいから一個のクエリについて一文字ずつ確定させていきたいなあ。」と言っていたらスタックに積みながら判定するとラクそうだと気付きそのまま実装に。'?' を出力し忘れて1ペナを吐いたがあまり時間をかけずに通せた。（コンテスト後に構築・インタラクティブはこういうフォーマットのミスが起こり得るし実装しなかった人がコードを動かしてみてサンプルが合ってるかどうか確認するのも良いかもね、という話をした。）これを実装している間に hatoと kouty が E 問題の考察ができたらしく、構文解析だから実装は重いが考察はそんなに重くないし間違ってなさそうらしいという話を聞き、hato に実装してもらいながら kouty と F を考えることに。O(N^2) が許されてるし辞書順最小を求められているから O(N) で valid かどうか判定できたら前の文字から順に A を試して B を試して C を試して……、とできる、という話になり、ここから約2時間、いろんな考察を生やしたりはと君に全探索+naive を書いてもらったり（最初は ococo が naive を書いたがなんか合わなかった）したが結局通せず。E/F 間は割と崖っぽい感じでそこの手前までを時間かけずに解けたのは偉かったと思う。

模擬国内～国内予選

月曜日にサークルで練習した後、毎週木曜日にやってるけど今週はやる？みたいな話になったが、立ち回りもどう動くか割と決まっていて「直前にチームで練習してそこで調子悪かったら本番が気分的に嫌」という話になりやらないことに。各々当日にパフォーマンスが出るように過ごした。ちなみに自分はモチベーションを上げるため、この参加記の国内予選までに書けるところ（模擬国内の話とか）は予選前に書いた。コンテスト後に書くことが減らせて一石二鳥。

↑と、ここまでを水曜に書いていたのだが、木曜は緊張で何かしていたい感じだったので、精神統一を目指して神社に。前厄であることが判明したが、浪人していない男性のラストイヤー組はほぼ全員がそうなのである。おみくじは引かなかった。絶対に凶を引きたくなかったため。

 

 

国内予選本番

大勝利！やった～～～～

↑これは国内予選前に参加記をどんなフォーマットで書くかを決めてる段階で書いてる。前祝いというやつですね。

マジで通過できた！やっぱ前祝いや！

 

以下、コンテスト中の話を。（特に自分以外の2人の行動については記憶違いがある可能性が結構ある）

ABC

過去数回の練習から A 問題は ococo がやることに。コンテスト前に印刷方法を確認しておいて始まったらすぐに印刷した後 A 問題を読む。「同じ問題有志コンで見たことある気がする？」と思ったが、多分この時思い出していたのは KUPC2024 - E で改めて見てみると全然違った。

atcoder.jp

計算量を削ることもできそうな見た目ではあるが A 問題だし大丈夫だろうと思い制約をパッと見て大きくないので二乗で計算するコードを書いてAC(0:01)。B 問題を読んでいた kouty、C 問題を読んでいた hato が共に問題文を読んですぐに実装にできそうな感じだったので D を読む。kouty が B を実装している間は hato と一緒に読み、「N,M の値が小さそうだから周期を全探索したい」的な話がでてきたところで kouty が B を通し hato が C の実装に移る(0:04)。kouty に問題の概要と全探索したいという話をすると、お互い多少の嘘方針を生やしながら「valid なら縦・横それぞれで見た時に種類が2個しかない」という話が出てきて、それならランレングス圧縮を見ることでできそうと思い、そのくらいのタイミングで hato が C を通した(0:13)ためそのまま D の実装に移る。今回はライブラリを使えるため、ABC 速解き用に作っていたランレングス圧縮のコードでちょっとラクができた。一部縦横がごっちゃになってサンプルが合わないタイミングがあるも、そこまで時間をかけずに修正をできて AC(0:24)。これを通せた時点で全体3位で「今コンテスト終わってくれ！」になってた。

D

ococo が D の実装をやっている間に hato・kouty が E を読んで考察をしていてその内容を聞く。根から遠い方に時間ギリギリのところがあったらそこの上にその制約を良い感じに伝播させていきたい、みたいな話があり、複数の子があるとそうはいかないかも？みたいな話になったが、それならギリギリの方から行けばいいはず、みたいな話をでてくる。それを使って木 DP を書けそうだが結構実装が重そうな気配があり全員が実装をシブっていたが ococo が書くことに。その木 DP を書いている途中で hato が「新しい点に行く度に行ける点が増えて木の形が変わるから N 回木 DP しないとまずそう？」的なことを言い、二乗が通る制約なのにそれをしないと O(N) で違和感があるという話があったため縮約パートを付けくわえる。何度か小さいバグらせをしたがサンプルが合ったため提出。実装には全く自信がなくて通らない可能性も結構高いと思っていたが、一発AC(1:07)。本当に嬉しかったしめちゃくちゃ安心した。

EF

ococo が E の実装をやっているときは hato に実装を見てもらったり方針を指示してもらったりしていたのだが、その間に kouty が F と G に目を通していて問題概要を聞くことに。G は幾何で見た目がヤバいため F について考えていて、その間に ococo は H を見ていた。H は ears っぽい形だから耳 DP ができそう + ある '(' について ")()" の形になっているかそうでないかで開き括弧を何回踏めるかが大きく変わる、みたいなことを考えていた。細かいところを詰めるのがしんどそうと思い F に戻って考察を聞く。なかなか良さげな考察が出てこない+パソコンが空いていたため「ある文字列から作れる文字列を全部出力する実験コードを見てみたい」と言い hato に書いてもらう。すると考察中には作れなさそうと思われていた aaaaabbbbb -> ababababab みたいな形ができることが判明し、最初は実験コードのバグか？という話になったが操作列も一緒に出力させてみたところ suffix から順に作っていけばいいと分かり、既に sort する方法は分かっていたらしいため kouty が実装。無事通してもらった(1:44)。

G

この時点で D までがかなり素早く通せたのもあり6完内でかなり上の方におり、 G は訳が分からんし H は通してるチームの少なさ的にそんな単純じゃなさそう、という話をしていた。（H はこの時点で耳 DP の遷移を考えていたが面倒が多いなあと思っていた。）とはいえ G がどんどん通されているし幾何ライブラリが必要なタイプだったらここまで通されないはずなので幾何的な考察さえできればそんなに実装で苦しむタイプじゃないんじゃないか？ということになり3人で G を考える。なかなか良さげな考察が生えなかったが、終了30分前くらいで「基本的に側面は三角形になりそうで四角形になる場合が特殊」「入力の与えられ方が点の位置とかじゃなくて角度なのがかなり変」みたいなことを話していると kouty が「対応する辺が平行になると四角形の側面ができるから平行になる辺の組を固定して全探索すればいいのでは？」的なことを言い、それを聞いた ococo が「それだ！！」となりそのコードを書くことに。kouty は大まかな方針が分かっただけで細かい実装は浮かんでいない風だったが ococo がその方針でかなり自信があったため、残り時間が少ないのもあり突っ走らせてもらった。角度を管理するにあたって360度で引き忘れていたり90度と270度を同一視するかどうかが分からなくなったりしながらもサンプルが合ったため提出。WA を出しその後細かいところのコードをすっきりさせてもう一度出したが WA。ここで入力のフォーマットが下9桁あることを hato に指摘され、さらに360度まで扱うことを考えると、今まで 1e-9 にしていた eps を 1e-13 にする必要があることに気付いた。これとほぼ同時に hato に1e9倍して整数で管理すれば良いことを指摘されたが、一旦 eps の値を変える方が時間が少なかったためそっちを提出しAC(2:47)。浮動小数点に対する態度としてあまり褒められた態度ではないが時間が少なくて焦りもあったし仕方がない。

コンテスト終了まで

H は考察を詰めて実装をし終えるまでとても10分ちょいでできそうな感じではなかったし I は問題文に目を通した程度だし、この時点で順位表を見るに通過はほぼ確実だっため順位表を見ていた。「東大・京大・科学大は全完しないと駄目だしなんなら全完しても確実ラインの10位に入れないの大変すぎる」みたいな話をしたり、学内2位の Akai_kobito の順位を見て通過条件を満たしているか確認するなどをしていた。そうこうしているうちにコンテスト終了。

 

 

D みたいな問題を素早く解くのは割と得意寄りであり、それにより G を通すまでに時間がかかった割に7完内では結構良い順位だったのは偉かったと思う。

 

https://icpc.jp/2025/sponsorship/awards-domestic/

ちなみに23位は企業賞の対象らしい。エンカレッジ・テクノロジ株式会社さんありがとうございます！

国内予選終了後

北大の他のチームと話したり使った部屋の片づけをしたりした後、希望者で焼肉屋で打ち上げに。

 

 

（他にも参加した人はいっぱいいたが、自分含めてツイートをしていない人が多い）

一部の人はそのまま二次会でボドゲをしていたらしい。自分は疲れて体力が残ってなかったため帰宅。

 

感想

普段の自分の性格には何かを頑張っている人を見ると「どうして見返りもなくそんなに頑張れるんだろう」と思ってしまうような、冷笑癖のような性格があるのだが、今年、 ICPC ラストイヤーで、もし Yokohama Regional に行けなかったらと想像するとそれが嫌で嫌で嫌で仕方がなく、なんとかしてもう一回横浜に行ってやる、そういう思いがあった。その割にはそこまで個人で過去問をやっていなかったという話がある。そして去年の .Shaco での反省と自分たちの学内での立ち位置・ICPC 参加チーム全体での立ち位置を考えた時に立ち回りを安定させることが何より重要で、逆にそれさえ実現できれば通過できると思っていたから、安定した立ち回りを意識して一問一問確実に通せるようにしよう、と何度も言ってきて本当に良かった。自分は割と問題を飛ばしたがる癖があって、模擬国内でも構文解析の E を飛ばしたがったり国内予選本番でも G を飛ばして H を解きたがったりしたが、チームメイトにそれを止めてもらえて本当にありがたかった。結果的に ADEG の実装を担当して、コンテスト後にも「ococo が偉かった」的なことを言われたが、D は自分一人だったらもっと時間がかかってたはずだし、E は一人だったら通しきれるか怪しかったし、 G は自分だけじゃ絶対に通せなかったので本当にチームメイトに感謝である。

そして、自分は今年が ICPC ラストイヤーのため、 ICPC 国内予選という問題傾向が(atcoder 等と比べて)独特でその上緊張感もめちゃくちゃあるコンテストに contestant として出ることはなく、もうやらなくていいという肩の荷が下りた気持ちと、もうできないという寂しさが同居した不思議な気持ちである。

こんなことを言ってちょっと感傷的になっているが、あくまでこれは予選の突破であってゴールではない。まだまだ一人の競技プログラミングプレイヤーとして未熟な部分は多いし、もっと力をつけてさらに強くなっていきたい。

そして最後に、ICPC を運営・開催してくださった皆さん、JAG の運営や模擬国内の運営・開催をしてくだっさ皆さん、国内予選を行うにあたって部屋やプリンター等の準備をしてくだった皆さん、コーチをやってくれた winter さん、チームメイトのはと君、kouty 君、その他何かしらの形で少しでも ICPC が良くなるよう、我々のチームが良くなるよう協力してくれた皆さん、本当にありがとうございます！！！

 

Ladies and Gentleman See you again in YOKOHAMA