はじめに
ICPC 2025 国内予選で全完6位でした。
メンバー紹介
shinchan概念化まで
悲しいことに誰もがshinchanに今年も参加権があると誤認していたため、昨年度から「来年のチームはKowerKointとshinchanと誰か」と思われていました。実は僕は去年の横浜での悲劇の後かなり自信がなくなり、また競プロがなくても十分人生を充実させられるようになったのもあり上位の成績を狙うのにふさわしい人間が他にいれば譲ってもいいくらいの気持ちでしたが、最後まで責任を持って阪大の栄誉に貢献すべきだと思って覚悟を決めました。そんな中でNachiaの阪大入学という衝撃的な噂を聞きました。僕にはトッププレイヤーのNachiaを確実にWorld Finalsに連れていくという大きな役目が課せられました。
OUPC 2024ではNachiaと(記憶上)初の顔合わせを行いました。その会場で阪大のOBなども巻き込んでチーム名「The World of kotamanegi」を決定しました。去年のチーム名「kotamanegi_world」をもととし、Osaka UniversityがThe University of Osakaに名称変更されることをネタとして取り込みました。そのままDay 2の北大セットに出ました。同時コーディングありなので、バランスの取れたチームに比べて合計実装速度に差が出てしまい、通しきれない問題もありましたが、Nachiaサポートで考察を進める感覚を少し掴みました。
Nachiaの入学後はUCなどの5hコンテストを毎週チームで走りました。そういう分担に決めているわけではないですが、僕とshinchanの2人で下位の問題に取り組んで、Nachiaが上位を進めるというスタイルが確立され始めました。 この時の練習で一番印象に残っていることは、バグが出ていてPCが空いているときに「なぜランテスを書かないのか」と言われたことです。僕はランテスを滅多に書かないのですが、詰まったときの遅延が大きい原因はそういうところにあるのだなぁと気付かされ、刺さりました。
5月25日の夜、今年度ICPCの参加資格情報がYokohama Regionalのサイトに公開されました。 なんと、昨シーズンまでのコロナ禍特例措置が廃止されており、shinchanの参加権がありません！！！ こんなことは誰も知りませんでした。国内の他のいくつかのチームも混乱に陥ったようです。 しかし国際版のサイトには1年以上前から記載があったようで、ダメ元で問い合わせを行ったものの参加権は得られませんでした。
我々としても共に戦う気満々だったチームメイトを突然失ったのは悲しかったですが、 特にshinchanは人生のモチベをかなりICPCにささげている人物だったので、突然それが無になってしまったのはとてもかわいそうでした。 shinchanから、「チーム名に入れてWFに連れて行ってほしい」という遺言を授かり、チーム名は「The Revenge of shinchan」に改められました。
新しいメンバーについては、krit3379が最近伸びていて頼もしいということでshinchanと合意し、すでにチームを組んでいたところ声をかけて交代してもらいました。 直前に騒動に巻き込まれてチーム再編を余儀なくされたhiro71687とbesukohuには申し訳ないですが、彼らも1.5Nachiaとして横浜に進出していて嬉しい限りです。
模擬国内まで
国内予選が近かったので5hの練習は一旦せずに昔の国内予選や模擬国内を数回走りました。krit3379は僕ともNachiaともチームを組んだことがないはずではじめは少しコミュニケーションを取りにくそうにしていたのを覚えています。
模擬国内・国内予選に出るための環境を整備しました。krit3379と僕はもともとUS配列の使い手で、NachiaもすでにICPCのためにUS配列で練習してくれていたのでやりやすかったです。 Windowsに競技用のローカルアカウントを作成し、WSL (Ubuntu)で構築しました。VSCode (Nachia,krit3379用)とNeovim(KowerKoint用)を用意しました。 好きなライブラリをもらって配置し、競技用情報のメールやルール、ジャッジのマニュアル、CPP Referenceをダウンロードしました。 ジャッジと同じコンパイルオプションのエイリアスも用意しました。 Nachiaはビルド・実行用のシェルスクも書いてました。
模擬国内
それまでの3h練習で後ろ3問がトップの順位を分けることがわかったので、Nachiaに「先に後ろ3問を見る」と言われました。随分思い切った戦略だと思います。我々が前の問題をつまらずに解くのが前提となるハイレベルな戦略ですが、優勝確率を上げるには悪くないと思います。 KowerKointがA、krit3379がBを起点とすることにしました。
マニュアルを呼んでいなかったせいで全問題文の一括印刷がどこにあるのかわからず、すべての問題を1つずつ開いて印刷ボタンを押して手間取りました。
Aを見ました。mexを取るだけです。
A AC (0:04)
krit3379にBを書いてもらってCを考えました。分母が小さい方からマージしていくとかのトリッキーななにかがあるかと一瞬考えましたが、通分するだけで良いことがわかり、準備が整ったところでBの実装が終わっていました。
B AC (0:06)
Cを書きました。
C AC (0:09)
krit3379がDに着手していたのでEに行きました。やることはすぐにわかるけど実装に時間がかかるタイプでした。
L1の再帰降下をやりながら即時に評価します。現在のノードにたどり着くためにい必要な変数割当をunordered_map<string, bool>で持つと、矛盾していないノードではそこにたどり着く確率が setで管理しておけばよくて、最後にその個数を使って確率から場合の数に変換します。
Dの実装がややつまり気味だった隙に代わってもらって少し実装を進めました。やがてDが終わりました。
D AC (0:31)
続けてEを書き上げました。
E AC (0:43)
Fをkrit3379と2人で考えました。
Nachiaに近況を聞くと、
- Gは考察が済んでいる(実際はコーナー処理が不足していたが)
- Hを考え中
- Iはコードまで紙面上に書けている
という話だったのでIを写経してもらいました。僕も一通り問題文に目を通し、IのNachiaの考察に納得してしまったのですが、直線を複数本引いてもいいのを忘れていたことに気づいてストップしました。
Hは
Fはkrit3379にまかせて僕がGを詰めることにしました。やがてkrit3379がFを思いつき、実装を始めました。
ペナが生えちゃったので話を聞くことにしました。
後ろからのDPで前計算するのですが、Aは他の文字に比べて真に有能なので、使うCの個数を添え字、最低限使う必要のあるAの個数を値にすることで次元削減に成功していました。賢い。
krit3379から、「
F AC (1:53)
ここでkrit3379を暇にしてしまった(Hの話をしたけど進まず)ものの、僕はGを書かねばならないので黙々とコーディングをはじめました。左上の角の中でマッチングする辺の個数を固定したとき、他の角でマッチングする辺の個数は一意に定まります。残りは1組の対辺の中でマッチングされるパターンで、何かの高速な01文字列一致判定があればよいです。
角に点があるときのことをNachiaもKowerKointも考えていませんでした。どれかの辺に押し付ければよいのですが、追加の必要条件を丁寧に洗い出すのは地味にしんどかったです。 配列のサイズチェックを間違えてREしたり辺の個数を求める式が間違っていたりしてペナもたくさん生えたしグダってしまいました。大変申し訳ない。 文字列一致判定はbitsetで十分だと思っていましたが実際にはTLEしてしまい、素早くロリハを張って書き換えました。大体いい感じに関数化したりreverseなどのユーティリティを用意してコードクローンを阻止していたのでここの修正はすぐに終わりました。
なお、コードのデバッグなどをしている間にHを書いてもらっていました。 20:9の大きなモニターを用意していたのでプリンターを使わずに目視デバッグとコーディングを同時にできて少し体験が良かったです。
G AC (2:49)
NachiaはHのランテスを書いて合わせていましたが、残り時間で合わせることができず、終了してしまいました。 本人はかなり反省しているようでしが、自分がGで多くPCを占有してしまったのも大きなはいいんだろなぁと思い、悲しいです。
結果は全体9位、有資格6位でした。流石に横浜に行くには余裕だったし、他の多くの上位チームは実装難のGではなく数式一発のHをやっていましたが、完数では負けていないので許容されます。
国内予選本番
本番こそ完数で差をつけて1位を取りたいです。同じ戦略で挑みました。
A問題は一瞬も一瞬だったので画面半分にB問題を開いて見せながら書きました。
A AC (0:01)
krit3379に交代してBを書いてもらい始めます。印刷問題文が届いてたのでCを見ます。
平日の日数m/7*5から、意味のある休日(a<=m && a%7 != 6 && a%7 != 0)をsetに押し込んでそのサイズ取り除きます。式を紙に書いて確実にしました。
B AC (0:04)
Cを書きました。紙に書いた式のnとmを間違えてたり休日をa%7 == 1 || a%7 == 2と書いてたりしててダメでした。
C AC (0:08)
Dを書いてもらってEを見ました。 プリム法みたいに1つの連結成分を大きくしながら期限順にPQに入れて近いやつを吸収していきます。
Dのサンプルが合わないようなので交代してもらって書きました。
子の期限を考慮するのを忘れてて慌てて先に木DPするフェーズを挿入しました。
E AC (0:33)
Dが本当に合わないらしく、困った。
気にかけつつもFを見てました。 Fは僕は得意じゃない傾向の問題に見えてて、とりあえずソート・逆順ソートができることとか、難しそうな「aaabbb→ababab」ができることを確認して「個数が合うならいつでもyes」を推測したりしてました。操作が前の方にしか影響しないので、後ろから合わせるという漠然としたお気持ちは持ちつつも、合わせ方がわからなくて2連の操作の意味を考えたり色々試行錯誤してましたがよくわからず… Nachiaにアドバイスを求めたら、同じ操作の繰り返しで末尾に好きな文字を持ってこれることがわかったので書きました。計算量がでかくならないようにRLEしたdequeで持ちました。きれいに書けたと思います。
F AC (1:37)
この頃にはNachiaのGHIの考察はほぼすべて済んでいて、Gについては紙面上にコードが用意されてたしIも短いのですぐかけるとのことでした。詰まってるDが心配なので僕もデバッグに参加しつつ、確実なI、Gを続けて書いてもらいました。
I AC (1:11)
G AC (1:17)
はい天才～。後で聞いてもこのあたりの順位表の動きが一番ドラマチックだったようです。西の学校らしく通し方でお笑いをしているとも言われました。
残りの時間でDのデバッグ(KowerKoint, krit3379)とHのコーディング(Nachia)を並行しました。
Dは、計算量がでかいのをkrit3379が心配していたのであり得る最小の一辺
2 2 .# .#
が2になって落ちていて、チェックのほうが落ちていると誤認してそっちばかり見てましたが、誤って
D AC (1:51)
残りはHのみ、僕とkrit3379は問題内容すら知らず、問題文を読んで「自明な事実しかわからん」みたいな話をして盛り上がってました。コーディングに明らかな不自然がないか見守るべきでした。うるさくしててごめんなさい。 さすがNachia、スッと通りました。解法後で聞いたけど僕が書いたらもっと沼ってた気がします。
H AC (1:59)
全完！！！！！ちなみに僕は一瞬コンテスト終了直前だと誤認していたので2位で終わったんだと思ってました。
Dの時間がエグいので大量に抜かされていきました。問題は簡単だったけど全完が出まくっていて恐ろしい。
余った時間でHの解法を聞いたりGIを僕とkrit3379で考えてみたりしました。GIは割とすぐに解けました。 Iが簡単なことはコンテスト終盤にバレたようでした。
観戦
Rinshan Solutionは実力構成が僕らとかなり似ていて、序盤の問題はきっとharurun4635さんとkemunikuさんが書いてたのだろうと思ってたので、彼らと実装スピードにそんなに差が出ていることを悔やんでいましたが、実はPCTProbabilityさんが全て書いていたと知って少し安心しました。それにしてもやばいが。
阪大では1.5NachiaとAC_is_all_we_needが通過しており、再び3チームで横浜に進めるようで大変嬉しく思います。彼らにも是非健闘していい思い出を作って欲しいです。
謝辞
楽しい予選になりました。チームメンバーだけでなく他のライバルチーム、コーチや監督の先生、打ち上げの準備に協力してくれた研究室の人々、応援してくれた人々に感謝しています。
今後のこと
僕は競プロに関して結構限界を感じ始めていたのですが、krit3379がかなり燃え上がっていそうで僕も頑張らなきゃと思いました。Nachiaの強さをできる限り発揮できるよう我々が全力で支えねばなりません。すでに予定をたくさん入れてしまっていて厳しくはありますが、チーム練習以外もできる限り時間作って頑張りたいと思います。
横浜では少なくともメダルを取りたいです。よろしくお願いします。
