ICPC 2025 Asia Yokohama Regional 参加記

ICPC 2025 Asia Yokohama Regionalにチーム「DaiMonge」で参加して、9完3位でした。

day -10

Seoul Regionalのときにぶち壊れたキャリーケースの買い替えと、前に予約したぬいぐるみ(「アクアリウムは踊らない」のスーズ)が届いた。

day 1

12時くらいに新横浜でkumaと合流。昼食を取ったあとyumaとも待ち合わせて会場に向かった。エントランスで他の京大勢(コーチ含む)と出会い、registrationを済ませる。

2時過ぎにopeningとリハーサルが行われた。4完最速で優勝。暇になったのでkumaがbrainf*ckのインタプリタを実装していた。K1NTOKIのintroのコードを写して実行すると見事メッセージが表示された(kumaすげー)。
リハーサルの後でtech talkとteam intro。チーム名の由来を紹介したら、コンテスト実況の時に言及してもらえた。

1日目の後東大勢と合流したので、半々に分かれて中華街に向かった。Kite_kumaさんとKumaTachiRenの邂逅。
ホテルに帰宅してABCに出る。Eから見て「はいはい最小値countのセグ木ですね」と意気揚々に実装する。WA？？　とりあえず代わりにDを見る。BFSやるだけだなあと思い書く。TLE？？？
よく見るとBFSのusedが壊れていたので直すと通った。Eもminが非ゼロのときに0にするのを修正するとAC。結局6完3ペナというカスみたいな成績を取り1時間で撤退。

気を取り直してEuler 973を読む。およそ整数になるとは思えないもののmod 10^9+7が取られていてビビる。
実験を30分くらいで書くとX(10)が合って、かなり良さそうな性質を見つけた。シンプルな問題に言い換えられ解法がすぐに生える。順位表を見るとまだ誰も解いていない！マジ？と思って実装すると30秒くらいで答えが出た。WA。よく見るとmod 998244353を取っていた(?)。再度提出するとAC！！！

まさかGold Medalが獲れる日が来ると思わなかったので本当にびっくり。チームメンバーが一緒に喜んでくれた。yumaも解法には気付いていたようだが、PCを持ってきておらず泣く泣く撤退していた(後日AC)。

day 2

前日のFAで睡眠デバフがかかっていたが、ある程度は寝ることができた。8時半くらいに会場に向かう。

コンテスト本番

いつもと違ってyumaとkumaが両端から読むことに。
環境構築の後yumaがDを通す。解かれているEを考えていると、kumaが解法に気付いたので書いてもらう。にぶたんの境界を指摘するとそのまま通った。
kumaがHのGreedyを実装し投げるが通らない。printデバッグしてみると判定条件が壊れていたので、指摘すると今度は通った。

yumaがCでハマっているのをkumaがヘルプに回っている間、Jの考察が生えたので実装する。3通り以上の場合分けを経て提出。WA。この80分間で中盤枠が1問も通らない非常にまずい状態になった。去年のKUB1と似たような状況でかなり焦る。
少し経った後kumaがJのコーナーに気付き、そのまま書き直してもらい通った(すみません)。直後にCのバグが判明しようやくAC。この2問が通る前は13位とかだったらしい。本当に助けて欲しい。

kumaがAの気合dpを実装している間にIをyumaと考える。Eulerのpartizan game問っぽさを感じたのでsurreal numberを計算してみる。既に決まっているマスで分割すると端の様子のみが本質的であることが分かる。実験で予想値を得たのでAの合間に書いてみることに。WA。困ったのでトイレに行って考えているとS=“.”で壊れることに気付き急いで戻る。5秒で直すとACした。

Aがある程度動いたようなので投げるとRE。L=10^18で試しに実行するとCLionが落ちた(?!)。どうやら座圧のところでミスっていそうだったので、そこを直してもらうとAC。
現時点で7完5位だがbogosortに捲られている。切り替えて解かれているG(数え上げ)を考える。yumaが条件の言い換えをしてくれたので、各maxでO(sum/max)時間をかける調和級数系のやつだろうと予想する。いろいろな言い換えを挟むとなんとか包除で数えられる形になったのでPCを奪って実装。凍結4分後にサンプルが合ったので投げると通った。Project Eulerありがとう(数ヶ月前に類題を解いていた)。

残りはLを頑張るしかない。Gを粘っている間にkumaが方針を立てたようなので実装を見守る。平行なペアのあるケースで細かい場合分けがあるようでかなり苦しそう。残り20分ほどでSample 2が修正され、意を決してkumaが投げる。

AC!!!　kumaさんありがとう2　余った時間でBを少し考えたが、本質的な考察は出なかったので弁当を食べていた。コンテスト終了。

YesNo,懇親会

SSQSやThe Revenge of shinchanなどに抜かされて終わりそうだなあと思っていたが、凍結が解除されるとLを通したのが自分たちとStrong Zeroだけだった。結果、9完で銅メダルを獲得できた。ICPC初入賞やったーーー

表彰を受けたあと急にコメントを求められたので(?!)、京大英語4割の英語力で乗り切った。次回から予告だけして頂けると被害者が減ると思います。
懇親会で他チームの立ち回りや昨日のABC-F既出事件の全容を聞くなどをした。ブース巡りをサボった結果、キーボード配布イベントに気付かず終了…

総括

kumaのLのおかげで奇跡的にメダルを取れたが、中盤のムーブはかなり問題点が残る形になった。playoffまでになんとか事故率を下げたいところである。
THS,bogosortも十分な実力を既に持っているはずなので、台湾で倒されないように精進したいと思う。

ICPC 2025 Asia Seoul Regional 参加記

ICPC 2025 Asia Seoul Regionalにチーム「DaiMonge」で参加して、10完4位でした。

Day 0

Registerに使う書類の印刷などをする。在学証明書が英語である必要があるらしく1ペナ。
院に入ると海外渡航届がオンラインで提出できなくなる謎の仕様で、事務に一度問い合わせる羽目になった。

Day 1

15時頃に韓国に入国。
空港近くのコンビニでWOWPASSを購入したが、結局最終日まで使うことはなかった。本来は地下鉄での移動などにも使えるらしい。
会場近くのホテルを取ったため、そこまではUber(タクシー)で移動した。睡眠不足のせいで多少酔ってしまった。

コーチのnaniwazuさんの伝手で、Huaweiの担当者の人から夕食会(ビュッフェ形式)に招待してもらった。東大チームのMagical Fishも一緒に同行していた。
英語で将来の進路や競プロ歴などについて聞かれたが、あまりちゃんと答えられなかった気がする。

Day 2

Registerまでは時間があったので、昼食は近くのデパート内で探すことにした。どうやら世界一大きいデパートと称されているらしい。
4階の冷麵の店に入って餃子とのセットを頼んだ。ハサミの使い方が分からず困惑していると隣の客が親切に教えてくれた。
そのあと地下で怪しげな飲み物を買って会場に向かう。

opening ceremonyの後でpracticeに入る。どうやら去年のセットから出しているようだが、Bの定数倍が厳しい問題でyumaが苦戦していた(結局通らず)。
Colorful Quadrants - Problem - QOJ.ac

実はRegisterの前にhyperbolicさんにSeoul Regionalに参加する旨をTwitterで伝えると、韓国チームも複数連れて焼肉に連れて行ってもらえることになった。まさかあそこまでの大所帯になるとは思わず驚いた。
両国のICPC事情やアカデミア(高校・大学)の様子などについて会話するなどした。相手方の日本語が流暢で感心してしまった(アニメ文化の影響で覚える人が多いらしい？)。

Uberでそのまま帰宅。

Day 3

ホテル1階のコンビニで朝食を買って会場に向かう。

コンテスト本番

環境構築を済ませて(UCupと同様に)後ろから読む。L,Mはさすがに自明だが、先に解いたkumaのGに実装を譲る。
DGLMが終わった後でkumaからK(幾何)の解法の概要を聞く。正しそうだったので書いてみるがサンプルがなかなか合わない。結局kumaに尺取りの部分を修正して通してもらった。yumaはCの実装で苦労していたので、そっちのヘルプに回るべきだったかもしれない。
Iは読解が済んでシミュやるだけであることが分かったので、Eが通ったあとすぐに実装する。nとmをtypoして1ペナを踏みながら通す。

ここから難易度の崖が大きいらしく順位表がなかなか動かない。可能そうなH(数え上げ)の実験を書いてしばらくすると、yumaが閉じた式を導出してくれた。O(N^2)で実装すると確かに合っているので、面倒くせ～と思いながら任意mod畳み込みを写経する。数々のコンパイルエラーを修正して提出すると一発で通った。なお凍結時間が90分前とは知らず、順位表を見て少し焦ってしまった。

残りの時間でsubmitが出ているF,Jを考えるが何も出てこない。ここで、kumaがFの多項式解(6乗だったかも)を整理できたようなので書いてもらう。

なかなかサンプルが合わない中、残り10分でようやくサンプルが全て通るコードが出来た。提出するとなんとAC！　kumaさんありがとう　ところでこの一部始終を後ろのチームがずっと観測していたらしい。10分ではさすがにやることが無いので3人で配られた弁当を食べていた。

コンテストが終わってtechtalk。韓国語がメインでお笑いポイントが分からず涙
各問題の軽い解説を挟んでYesNo。最終的にAMATSUKAZEに55分ほど差をつけて捲られてしまった。C,D,Eあたりの中盤枠にあまり貢献できなかったのは反省ポイント。

夕食は他の日本勢とデパ地下のフードコートで食べることになった。食事の後kumaとお土産を物色して帰ろうとする途中、デパート全体の閉店時間が来てしまい閉じ込められてしまった。幸い店員とDeepLによる会話を通じて脱出することが出来た。

Day 4

せっかくなので、帰りの空港までは地下鉄で移動することになった。途中で乗った無人のモノレールが印象的だった。

帰りの空港で荷物を預け入れる最中に、キャリーケースの取っ手が片方外れて使えなくなってしまった。仕方なくエレベーターでホーム移動する事態に...

総括

優勝の目もかなりあると思っていたので、下馬評通りの結果になったのが少し悔しい。
横浜ではさらなる強豪が集まるので厳しい戦いになるだろうが、引き続きUCupなどで練習を積みたいと思う。

JAG 夏合宿 2025 参加記

9/13-15に開かれたJAG主催の夏合宿に参加しました。

チーム

DaiMonge (TKO,yuma220284,KumaTachiRen)
3日とも現状のICPCチームで参加した。詳しくはICPC2025 国内予選 参加記 - TKOの雑記帳 。

Day 1

コンテスト1：有志セット(5h)

開幕は自分はテンプレ写経とABをやり、他の2人が両端から読んでいく流れ。ここでBを考察している間にkumaがLを解いたと主張したので(?!)PCを譲る。余裕でFAだった。

Bまで終わったあとG~Iを読む。yumaがFを実装している間にGを考える。対角線のparityだけが本質的で、range flip range sumが出来ればよいことに気付く。遅延セグ木の写経が面倒なので別の実装が無いか2人に聞いたが、無さそうなのでそのまま書くことにした。

5完した後yumaがD、自分とkumaがE,Hを考える。Dの実装でyumaがSA-ISを写していたが(https://tko919.github.io/library/を参照していた)、紙の方のライブラリは軽いO(N log^2 N)を持参していたのでそっちを書いてもらうべきだった。

Hはtupleの比較が出来ればよいのでhashを取れば可能なことが分かる。Dが終わった後でHLD,BITを写経して投げる。WA。おかしいと思って手元で適当にケースを作ると全然合っていない。BITのリセット忘れを直すと今度は通った。

順位表を見ると3D幾何のEが思ったより通されていて焦る。どうやらTKTYIのFAが早すぎて多くのチームが取り組んだ結果のようだ。平面に射影すれば木の直径に落ちることは既に分かっていたので、包含の判定以外の部分を書き切る。しかし、肝心の判定に手こずっている間に順位表が凍結されてしまった。

ここで、yumaから判定問題の解き方が提示されたので試しに書いてみると、自作ケースも含めてサンプルが合った。これで落ちたら厳しいなあと思いつつ投げるとAC。とりあえず5位以内には入れそうで安心。

残りの可能枠がKだけだと認識していたので考えていると、yumaがIをLPの形まで変形して渡してくれた。双対をとった後の解法を提示すると同じ結論に達していたようで、yumaがそのまま実装に移る。コーディングも大変なんだろうなあと思っていたら20分くらいで完了していた。投げてみるとなんとAC！　初のunique ACで本当に凄い。
後の時間でJ,Kを考察するが、有益なものが出てこないまま終了。

最終順位は9完2位。かなり好位置につけたが、AMATSUKAZEに1完差をつけられており悔しかった。

解説を聞く。Kは言われてみると典型だったので反省。Cも有名事実で、ライブラリの端に残していたので解けるべきだった。Jはシンプルに地雷だった。

コンテスト後、keymoonさんによるお楽しみコンテストなるものが開催されることがアナウンスされた。風呂に入ったあと自分も適当に参加する。LLMjudgeでAIにキレながら通すなどをした。

ACコード

Day 2

コンテスト2：JAGセット(5h)

序盤でA,Bを実装する。Aは読んだ瞬間にICPC2023 Yokohama-Iを思い出しすぐ解法が分かった。6分差をつけてのFA。

yumaがF、kumaがLに取り組んでいたのでFに合流する。愚直を書いて丁寧に式変形し、自分が丁寧にコードに起こしていった。落ち着いて投げるとAC。次にkumaがKを書いてそのまま通る。

yumaがGを考えている間に自分とkumaでLを考察。いつもの2部グラフを作るとaugment pathを取ってくださいと言っているだけのように見える。実装をkumaに任せて自分は解かれているJに移る。

LをACした辺りでJが2 SATで解けることが分かったので、yumaのGが終わった段階で実装を始める。実装量が想定より多くて不安になったが、submitするとすんなり通ってくれた。

他の2人はDを考えていたが、yumaが壁のXORを取れば解けることに気付いて実装に移る。自分はHを考察する。「hoge以下の要素について総和を取ってもhoge以下」という性質がかなり強くて、必要条件だろうという気持ちになる。証明できたつもりになったのでkumaに2乗DPまで落としてもらった。

凍結する前にD,Hが通り、2完差をつけて1位になっている。さすがに勝ったかな～と思いつつIを考える。2つの木をつないだ状態で01 on Treeをすると、有理数列をマージソートしてくださいという問題に帰着される。とりあえず時間もないので実装するが、01 on Treeの綺麗な実装を覚えておらずサンプルも全く合わない。終了5分前にサンプルが合って、緊張しながら投げる。

結果はWA。バグが判明しないままコンテストが終了した。解法はそこそこ確証があったので出来れば通したかった。

最終順位は10完1位！　序中盤の早解きが功を奏して逃げ切ることができた。


FAバルーンに囲まれるおさげちゃん

解説を聞く。結局Iの考察は合っていて、実装のどこかにバグが残っている感じだった。

理解していませんでした...
01 on TreeはKUPC2024で自分も出したことがあったので通し切りたかったなあ

少し間を置いて懇親会の会場に行く。実は余興として「3日目のwriter陣予想コンテスト」なるものが開かれていて、懇親会の途中に全員の結果がフィードバックされた形で第二ラウンドが告知された。上げられたシートに提出が反映されるようになった途端、主催のrianさんがめちゃくちゃ忙しそうにしていてウケてしまった。
結局、正解が1人出た段階でコンテストが終了し、明日のwriterがDispersionさんただ1人であることが開示された。正解者の話を聞いてみると、DailyAkariばりの理詰めで答えにたどり着いていてさすがに参ってしまった。

宿泊棟に戻った後、談話室でABCに参加する集団に遭遇。自分も参加するとC,D,Gで沼ってしまいギリギリの全完になってしまった。potatoさんの全完が本当に早くて驚いた。

Day 3

コンテスト3：Dispersionセット(5h)

前と同様に自分がABを解く...　はずだったのだが、Bをいくら考えても解けない。10分くらい経って2人にヘルプを求めて解法を教えてもらった。kumaにそのまま実装してもらいAC。

yumaがHを書いている間にJが解けたつもりになる。max(flux,0)の総和が答えになるギャグだと思いsubmitするがWA。kumaに聞くとループのみでバグることを指摘される。再度投げるがWA。コードを見直すと孤立点があるときに壊れている。さらに修正してAC。何をやっているんだ。

調子が明らかに悪いままkumaのEの考察を聞く。確かに合っていそう。二部マッチングが必要だったので写経して丁寧に実装し投げる。WA。やばいよ～と思いながら、とりあえずPCは空いていたのでランテスを回す。全然落ちない。困り果てて印刷したコードを眺めていると、kumaがUFを使ったマージのバグを発見する。これを直してなんとかACできた。ところでEが炎上している間にyumaがD,Kを通してくれていた。

yumaがCで苦戦している間、kumaがIを解けたと主張したので解法を聞く。手でケースをいくつか作って合っていそうだったので実装に移る。しかし、実装が絶不調なので幾何が正確に書けるはずもなく2ペナを食らってしまう。kumaから「凸包上の辺の向きが1通りしかない」コーナーケースをもらって実装ミスを修正。これでC,Iが通った直後に順位表が凍結。

2人がLを詰めている間に、既に考察が終わっていたGを書く。投げるとRE。浮動小数点数を使っていたのでmonotoneのチェックを外すと今度はWAが返ってきた。困ったのでkumaに聞くと、傾きが全部long longで済むことを指摘してもらう。直すとACが返ってきて思わず叫んでしまった。Lで2人がTLに苦しむ中、残り9分で全完！順位表を見つつコンテストが終了した。

最終順位は12完2位。最後はNya Revenge of shinchanにペナで捲られてしまった。

この多彩な問題のセットを1人が作り上げたのは素直に脱帽した。どの問題も適切な量の考察があって、特にC,Iの結論はかなり非自明で面白かった。

お楽しみコンの解説も終わってクロージング。阪大や東科大のチームと会話して会場を後にした。

総括

総合順位は2,1,2位とかなり安定していたので良かった。しかし、3日目の実装の正確性が本当にひどかったので、Regionalまでの課題にしたいと思う。

最後にスタッフの皆さん、参加者の方々ありがとうございました。ICPCへのモチベーションがかなり高まったので、悔いのないように頑張ろうと思います。

ICPC2025 国内予選 参加記

ICPC2025 国内予選にチーム「DaiMonge」で参加して、9完3位(同校1位)で通過しました。


チーム編成

  • TKO

チームの命名者かつ筆者　7/5時点でhighest -200

  • yuma220284

最近ARCで覚醒している　全ての場合分けを押し付けられがち
(e.g. 模擬国内-G)

  • KumaTachiRen

普段はC#erだが、考察やペアコーディングのデバッガとして非常に優秀

コンテスト立ち回り

ICPC 攻略法：国内予選編 - クマーの競プロ精進日記を参考にしたところ、模擬国内で現役2位につけたので同じ方針を採用することにした。

開始直後自分がA,Bを通す。Cを3回くらい読み直したが題意が正確に読み取れなかったのでyumaに交代する。

Dを見るといかにも「簡単な実装を見つけてください」という問題だったのですこし長考する。yumaが正規化した形に帰着してくれたのでkumaに監視してもらいながら周期性をチェックする。AC。

Eを読む。最初根から区間スケジューリングのGreedyを実装するが、Sample 1に弾かれてしまう。よく考えるとタイブレークでまずいことが分かるのでkumaと考察したところ、逆から見ると良いことに気付く。off-by-oneに手間取ったが投げると一発で通ってくれた。

Eでまごついている間にyumaがFを解いたようなのでPCを譲る。kumaからGの解法を聞いているうちにFが通る。Gの実装を書いて投げるがWA。コードを見直しているとkumaがm→nのtypoを発見する。直すと今度はACが返ってきた。

Gでまごついている間にyumaがHを解いたようなのでPCを譲る(デジャヴ)。残った2人でIを考察する。各1~nが2つずつへの帰着はすぐに出来る。Sampleを眺めていると「各x=1~nの間の(円環上の)距離をdとしてmax(d,2n-d)-nの総和」という予想が立つが、これはa={1,2,3,3,2,1}などで成り立たない。そこで予想を修正して「2つのxでsplitした2つの集合S,T間で1要素をやり取りするのにコスト1かかるとして、S=Tとなる最小コストの総和」とすると上の反例でも成り立つ。o(N^2)で行うには区間種類数クエリが欲しくなり、Moでとりあえず実装。ところがREが返ってきてしまい焦る。

kumaがtypoを発見して再度投げるがRE。さすがにランテスを書くべきということになり、テストを回すとなんと「各1~nが2つずつへの帰着」のパートがバグっていた。直後、より簡潔な実装を思いついたので書き直してみると少し経ってからACが得られた。2時間3分で全完。3位の企業賞がデカかったのでそのためのペナ調整だったということで…

残りの時間で順位表観戦。bogosortがFより先にIから通していたり、AMATSUKAZE,THSが窮地に立たされた後残り1分で全完するなど、思ったより見どころが多く楽しめた。

総括

10位以内を終始キープできていたのでとても良かった。終わってみるといつもの大学群がちゃんと激戦区になっていて、ある意味難しいコンテストだなあと感じた。

YokohamaまでにAtCのレートを戻しておきたいところではある。とりあえずARCで無限場合分けを出すのをやめてもらって...

ICPC Asia Pacific Championship 2025 参加記

ICPC Asia Pacific Championship 2025にチーム「Red Phobia」で参加して、7完15位でした。

旅行中の日記をそのまま貼ったので文章が不自然かも

day1

Changi空港着。外が思ったより湿気ている。
ホテルまでGrabで移動するが、一般道を120kmでかっ飛ばしていてヒヤヒヤ。
ホテルにチェックインして部屋割りをトランプで決める。部屋に入りベッドに突き刺さる。

day2

朝食のあとシャワーを浴びて着替えていると、4,5人でデカい植物園に行くらしいので付いていく。外出して5秒で蒸し暑さに後悔することになる。

植物園はかなり広く内部にランの庭園もあった。ダメ元で学生証を提示すると$12浮いたのでラッキー。
Grabでショッピングモールに移動する。梅田の中心地くらい栄えていてすごい。地下のフードコートがあるフロアで豚と兎の肉まんを購入。

せっかくなので地下鉄で帰ってみる。改札もクレカで通ってクレカ社会を体感する(キャッシュレス派なので助かる)。
ホテルに帰って肉まんを頂く。小さい方はデザートに近かったが豚まんは胡椒がかなり効いていた。

会場にRegistrationをしに行く。タクシー降車時のリスニングに失敗していたが、物理好きが「five star(タクシーの評価)」だと解読していた。

コンテストレジ・写真を済ませて学食(?)に向かうが、どうやらクレカが使えないらしい。
仕方なくスーパーマーケット+subwayで食糧を調達する。ビールケースを持ちながら15分ほど徒歩で帰る。
ホテルでビールを5本ほど買い取る。食事を摂ったらかなり眠気が来たので寝る。

day3

シャワーを浴びて朝食を食べる。KAISTのチームと少し会話する。もうバスが出ているらしいので、ギリギリで乗り込む。
デカめのホールでopening ceremony。

tech talkの後チーム名紹介。筑波のクソ長い名前のチームが笑いを巻き起こしていた。
昼食。奥のブースのパイが美味しかった。日本勢数チームと交流する(海外勢があまり分からず…)。
企業ブースをある程度回って、カフェモカやスイーツ、水筒などを貰う。個人的には海外用のアダプタが有り難かった(買うのが億劫で持っていなかった)。
貴重品を預けてpractice。フォルダを作ろうとすると権限が無いと言われ、15分ほど悪戦苦闘する。home直下に作るのが正着らしい。
A,Cを書いてもらう間にDの解法の復元をする(去年のplayoff-K)。2問通してもらった後でライブラリを写経するがhashが合わない。2人に間違い探しをしてもらうが見つからず、試しにrandom generatorを書いてhashを取るとなんとbashファイルが壊れている。後でtatyamに聞いてみるとプラスでオプションを指定しないとダメらしい。とりあえずライブラリ自体は正しい挙動をしていたので残りの本質部分を書いて通した。

バスで移動して夕食。ここのメニューはどれも美味しかった(特に鮭のムニエル的なの)。座席に配られていたペンシルパズルに囚われている人を複数目撃。食事終わりにマーライオンを見に行く。大したことないという暗示をかけられていたので、そこそこサイズが大きくて驚き。

ホテルに戻ってそのまま就寝。

day4

いつもの通りシャワー→朝食を済ませる。他チームと少し話してから会場に入る。

コンテスト

環境構築を済ませて後ろから見る。二人が簡単枠を見つけたようなので書いてもらうが、なにわづさんのGが燃えている。代わりに通されているLを書くが1WA2TLEで序盤からかなり最悪の滑り出しに。自分のLは入出力が遅くて落ちていた。yumaのAと合わせてAC。
Gのランチェを回している間に自分は典型っぽい見た目のKを考える。実はかなり難しい問題なのだが、見た目の簡潔さからかなりタイムロスしてしまった。
J(区間dp)とGが通り、簡単枠が無くなった頃。yumaからDを渡されて少し考えるとO(NQ)が生え、平方分割ableであることに気付く。平方分割は定数倍バトルになりがちで今まで敬遠してきたが、書くと素直に通ってくれた。程なくしてyumaのIが通る(自分はimos法のアイデア出しをしたが、場合分けには干渉しなかった)。
残っている可能枠はHで、なにわづさんがかなり苦戦していた。自分も考察に参加するが、方針の段階で三分探索などかなり迷走してしまいあまり貢献できなかった。そのまま順位表が凍結。
自分がRLの隣接するところをにぶたんできることを指摘すると、yumaがそこから答えが2回で特定できることに気付く。実装してもらう間にCとFを並列で考える。HはそのままACしたが、残りの問題は有益な考察ができずコンテストが終了した。

コンテスト後

移動してclosing ceremony。最終は7完15位で今年も景品はなかった(同校制限)(いつもの)。来年は1つくらい欲しいなあ
ScreenwalkersとJägermeisterのラストバトルは流石に激アツだった。
夕食会。今年のplayoffで引退する人もそこそこいるので悲しみ。AtCオンサイトもっと大規模にして欲しいという話をした。

ホテルに休憩していると他の人がバーに集まっているらしい。今後のICPCの参加や学業について喋る。帰ってホテルのロビーでnoyaさん、こたつがめさんとKUPC、ucupの話などをした。

day5

チェックアウト。ひらきちが荷物整理に時間をかけていたので、残りのメンバーでバスに乗る。移動中にProject Eulerの最新問をAC。

USS着。いつもの地球儀で写真を撮る。午前に来たためか人気のトランスフォーマーも空いていた。続けてhumanとmummyにもライド。室内だからと高をくくっていたら、初見殺しが多くてかなり楽しかった。
昼食をフードコートでとる。食べ終わった後に「Go to heavenで結果を当てたらCylonに乗る」という闇のゲームが始まった。自分はWAと予想して結果は...　AC。本番コンテスト中のどのACよりも嬉しかった。
ジュラシックパークを乗ろうとしたらメンテ中？だったらしく、仕方なく隣のfryerに乗る。結構早くてびっくり。
Cylon確定勢が帰ってきたらジュラシックパークが開いていたので、乗ってずぶ濡れになる(自分は前から落ちたので耐えたがyumaが後ろから突っ込んでいったのでかなり濡れていた)。フードコートで暇していたが、XでCylonがすごい賞賛されていたので流石に乗りたくなる。shkiiと一緒に乗りに行ったら20分待ちだったので並ぶ。humanよりは浮遊要素が少なく意外に面白い。ただトルネードスピンくらい振り回されたので少し酔う。
レートが高すぎたのでカジノは諦めて、お土産を見に行くがあまり目ぼしいものが無かった。休憩がてら最後のアトラクションにミニオンを選択する。アニメーションもアトラクションパートもちゃんと作り込まれていて、かなり正解だった。
他の人と合流して場外に出てから、セブンで飲み物を買う。普通にハズレで悲しくなる。

夕食を求めて市街地に移動。水が$1.5で売ってて後悔する。食事を買いに行くと1種類しか頼めないらしく、それを注文する。普通の海外の食事という感じだった。
ホテルで荷物を受け取る。そのまま空港に向かうが、主要なお土産店はもう閉まっていた。やむなく出国審査入った後の店で購入する。手続きは特に滞りなく日本に帰還した。

所感

コンテストの出来は序盤こそ酷かったものの、取らないといけない問題は落とさなかったので総合的には悪くなかったと思う。あそこからC,F,Kの難問を1つ以上通そうとするなら、やはりAtC橙以上のパフォーマンスは必須だろうと感じた。
運営に特に不満はなく観光パートも十分に楽しめたので、かなり実のある経験になった。2年間共にしたチームの解散は寂しいが、来年は新生Red PhobiaとしてWFに出られるようもう少し努力してみたいと思う。まずは精進を続けるところから。

ICPC 2024 Asia Yokohama Regional 参加記

ICPC2024 Asia Yokohama Regionalにチーム「Red Phobia」で参加して、9完6位でした。

Day 0

ライブラリを作り直したので再度印刷した。今年は燃やす埋めるもちゃんと対策済み。

Day 1

9時半くらいに京都駅で合流し、新幹線で横浜に向かう。来年は10時集合でもいいかな。

昼食をとって時間が余ったのでカフェでコーヒーをシバき、関内から歩きで会場に向かった。

Registration、開会式のあとすぐにリハーサルがあった。インタラクティブの実行ファイルの使い方が変わっていて困る。チーム紹介は語尾に「にょ」を付けているチームが印象だったにょ。

京大チームで四川料理の店に行った。値段もリーズナブルでちゃんと辛かったので満足。

ABC-A lotteryに応募し就寝。

Day 2

朝食+シャワーを済ませて会場に向かう。カフェインのせいか動悸がすごい。

コンテスト本番

環境構築が終わった後yumaにAを書いてもらう。なにわづさんからBの解法を聞いて通す。

yumaがIを詰めている間に自分も後ろから読み、Kが高速ゼータ変換で出来ることを確認する(AnonymsがFAを取ったあたりで確信)。写経が必要なIとswapしてもらうが通らない。なにわづさんが先にEを通し、Cの主客転倒まで終わらせていたが、最短経路木が下界になっていることがなかなか見えなかった。実装特にバグることなくAC。ここでKの初期化ミスに気付き修正をする。yumaに並列二分探索に書き直した方が良いと提案し、そのまま通る。

次に通されているDを見るが、サンプルで遊んでもなかなか構造が見えなくて焦る。するとなにわづさんから想定解とほぼ同様のアルゴリズムを提案される。自分も手で試して正しそうだったので書くと通る。これがAtC ratedだったらと寒気がするが、想定の難易度順でも難しい部類だったようだ。

この辺りからyumaがずっとGと格闘していたと思う。残りの2人はLと向き合っていたが、またしてもなにわづさんから想定解とほぼ同様の区間DPを提示される。話を聞いて確かに正しそうだったのでPCを強奪して書く。通る。このチームが黄色だけなのおかしくないか？

残り時間も少なくなりyumaのインタラクティブのhackを手伝う。200行近いソースコードの中から、ふと「ここ違いますね」と言い"-1"を書き足す。提出してみるとCORRECTの文字列。勝利を確信して各問題の振り返りをし、コンテストが終わった。

懇親会

知り合いの他校erといろいろ話す。ネッコアラが双子の思考を完全にトレースしてて凄かった(進出権の件)。

感想

自分の貢献値がεだった代わりに2人の頭が冴えていて本当に良かった。いつもありがとうございます。
とりあえずまだチーム戦は続けられそうなのでucupも積極的に出ようと思う。

あとKUPC2024もよろしくね。

JAG 夏合宿 2024 参加記

9/14-9/16 に開かれたJAG主催の夏合宿に参加しました。

Day 1

チーム

Red_harurun (TKO,yuma220284,harurun)

コンテスト1：2021 ICPC Asia Seoul Regional (3h)

セッティングを済ませた後AがほぼLCそのままだったので書く。しかしTLが短い+Moの定数倍が悪くペナを積んでしまう。
その間に2人がI,Jを解けたと主張したので、PCを渡して自分はEを考える。
式を書き下ろすと自然なDPが生えたのでIのAC後に通す。Hは最初2次元BITが必要だと思っていたが、yumaにPを予めソートすれば普通のBITで十分であることを指摘される。そのまま書いてもらいAC。

Bはやるべきことをyumaに整理してもらっていたので自分がコードを書くがWA。書き直してもらっている間にKを考察するとDilworthの定理からただのLDSに帰着できることが分かる。適当なGreedyの高速化に悩んでしまって時間をロスしてしまった...
残りの問題でまだ自分が読んでいない問題に目を通すと、LがLibrary Checkerで既出なことに気付く。1ペナを出しながらもAC。
Aの高速化でnoshiさんの記事に則り既存のコードを書き換えるがタイムアップ。この方針でも最頻値のmaxは求められるようだ。

結果は7完9位。結局Aが通せなかったのはひどい。Rollback Moの別解は確かにになった。
Dの解法がかなりシンプルで面白かった。+1h残してても解けるかは怪しいが...

談話室ではコヨーテやMirarisなどを遊んだ。ハプニング系のボードゲームも一個持っておいて損はないかもしれない。

Day 2

チーム

suzukaze_Akabayama (TKO,toam,karinohito)
Dispersionさんがwriter枠で空いていたのでお邪魔させてもらった。存在しない地名の例。

コンテスト2：有志セット (5h)

初動でkarinohitoさんがAを通す。toamさんがGを考察している間に自分はK,Nを考える。
Nが解けたので2完した後に実装するが通らない。問題をちゃんと読むとadjacentを読み飛ばしていた(おい)。
toamさんがMを解いたらしいのでPCを渡し通してもらう(FA)。どうやら自身の作問ストックにあったらしい。凄い。
Fで初めHLDと遅延セグ木が要るのでは？と思ったが、よく考えると頂点とその親しかflipする必要がないことが分かる。toamさんに書いてもらいAC。

今度こそNの方針が見えたが、DAG上の最長pathの数え上げが分からなかったのでkarinohitoさんに聞く。pairで持ってマージできることを指摘してもらう。
この辺りからずっとLを粘っていた気がする。LDS<=2と同値であることは知っていたのでRSK対応の式を書き起こすが、カタラン数と一致することになかなか気付けなかった。しかもDyck pathとの対応を知らないのでかなり詰んだ気持ちになる。
その間に二人がB,I,Kを倒していた。強い。Kは自分も考えていたがfloor_sum典型がずっと見えていなかった。弱い。

JでO(Nlog^2 N)状態のDPを提案すると、二人が1つ目のkeyの状態数も落ちることに気付く。
Jを実装してもらっている間にLの続きをやる。残すパートで、ある数列の三角形(Catalan's triangleという名前らしい)の導出が分からず、結局3人でエスパーすることに。
するとkarinohitoさんから一般項が伝えられてきた。off-by-oneを直すと確かに一致しており、提出するとAC。この瞬間が一番アツかった。

余った時間で感想戦をして終了。10完4位とかなりいい位置につけたが上3チームの壁は厚かった。

Lの解説でDyck pathとの対応を知りかなり感動した。Cの3/4乗DPは解けても良かったかもしれない。(+1完でも速度差で負けているが)

夜は東大勢によるタッグ将棋の観戦などをしていた。かなり見応えのある場面が多く面白かった。

Day 3

チーム

KUB234 (TKO,yuma220284,TKTYI)
ちょうど京大勢が3人いたので結成。

コンテスト3：JAGセット (5h)

序盤でA,B,D(FA)が通る。BはUFでやるだけだと思ったが、同じ連結成分を見るときの処理をミスって1ペナを踏んでしまった。
Iでyumaが読解に苦戦していたが、問題自体はただの木DPで難しくはなかった。自分が書いて通す。
TKTYIがF、2人でGをやるが、何故かGがなかなか通らない。制約を読むと出力する文字列は1000文字以下らしい。キレながら修正してAC。問題文は細部まで読みましょう。

Fでbitsetのtopbitの計算が出来ないか聞かれて、long long intで愚直に実装することを提案する。程なくしてFが通る。
Kが解けたらしいのでそのまま書いてもらうがWA。コードを読むと "Unknown" が "Unkown" になっているのを発見する(??)。
しかし、そこ含めて2,3か所を直してもまだ通らない。デバッグに苦しんでいる間にTKTYIがCを解けたと主張したのでPCを譲る。2,30分くらいでCの実装が終わり提出するとAC(!)。いよいよ本格的にKを通す必要性が出てきた。
いろいろなケースでデバッグしているとsetの管理がマージテクのswapで壊れているのを発見する。どうやって解消するか少し悩んだが、UFのマージする際の比較関数にsetのサイズを参照すれば直ることに気付く。
恐る恐る提出するとCORRECTが返ってきた。やっぱり普段からLCでデータ構造書いている甲斐があるなあ。
残り40分くらいは3人でずっとEを考えていた。Hallの定理でM=2の帰着までは出来るがパズルパートがどうしても解けない。WFにいるネッコアラを召喚したい気分だった。

コンテストが終わって結果は8完2位。格上のチームを複数倒せて嬉しかった。
SPJ with コーチはズルなので実質優勝です(いいえ)。

終わりに

JAGスタッフの皆さん、絡んでくれた方々ありがとうございました。Yokohama Regionalでも会えるのを楽しみにしています。
また来年も夏合宿に参加しようと思います。まずは学業をどうにかしなければ...