Project Euler Perfection達成

2026/08/03時点でのProject Eulerの問題を全て解きました。


Climbing

昔に半分弱埋めた後、2025年の頭から再開した。難問20問くらいに半年程費やしている（実際は毎週問題が追加されるのでRecent枠が30問程度かさ増しされている）。
AIの影響もあってか、直近の問題は知識ゲーが少なめの傾向にあると感じる。やはり愚直に実験結果を観察してad-hocな気付きを得られるかが重要になってきている。

印象に残っている問題

こういうのどうしても直近の難しい問題に寄りがち

#812

一番お気に入り。問題の本質部分は1行で終わるが、高度な体論の知識と競プロ地力が要求される。

#942

想定解がかなりあり得なくてこわい（知識ゲーではある）。詳細は伏せるが、この問題が出せるプラットフォームはProject Eulerだけだと思う。

#930

まだPEを埋め始めたくらいの時期に解いた。精度がシビアに設定されていて苦戦した記憶がある。泥臭い方法で解いた後、Forumでの解法に度肝を抜かれた。

#957

個人的には#983と同率でEulerで最も難しいと思っている。実際、一度挫折してから3か月後くらいに考え直してようやく通した。

#763

最後に解いた問題。どう見ても指数探索にしかならなさそうだが、観察を進めるとどんどん計算量が落ちていって不思議な感覚だった。

今後の展望

今後追加される問題ものんびり継続して解こうと思っている。あまりに難しいのが出たら放置するかもしれないが。
Eulerの作問側も興味はあるが、せっかく出すなら完成度の高いものを出したい。正直Black Algorithmやるだけみたいな問題が10個くらい存在するので、そういうのは避けたい気持ち。

ICPC Asia Pacific Championship 2026 参加記

ICPC Asia Pacific Championship 2026にチーム「DaiMonge」で参加して、8完11位(同校2位)でした。

day 1

桃園国際空港着。全員で地下鉄に乗って会場に向かう。改札では使えるクレカと使えないクレカがあるようだった。
registrationで本人確認がされなくて困惑する。プラカードや景品をもらったが、リュックが増えてしまったため収納スペースが不安になる。photo sessionに行ってから、ジェラートを食べたりJane Streetのパズルを解いたりした。

ホテルにチェックイン。今回はダブル×2の部屋に3人入ることになった。
荷物を置いてから夕飯に出かける。京大チームは半分がデパ地下のフードコートに吸い込まれて、残り半分は外の牛肉麺の店に入った。血餅を使った料理があったりして満足。
帰りにスーパーに寄って、親に頼まれていたお菓子や朝食用のパンを購入。

day 2

ホテルのバイキングは中流階級の価格だったので、平民の我々は購入したパンを頂く。

会場1Fでopening ceremony。打楽器のパフォーマンスや集合写真の撮影など。チーム紹介では今年も名前の長いチームがウケていた。
休憩をはさんでtechtalkが始まる...はずが、廊下の外でフライング立食が行われていた。とりあえずケーキとジャスミン茶だけ確保した。
昼食後にリハーサル。会場の隅の席だった。一昨日のplayoffと同じ、RBSTで殴る問題があったが、初期化ミスで1時間ほど溶かしてしまった。2年前はすんなり通せたのに幸先が悪い...

移動用のバスが来るまで時間があったため、タピオカを飲みながら日本勢と駄弁っていた。6面が青軸で出来たカチカチするおもちゃを配っており、他の人もこのおもちゃをずっと触っていた。

バスで空港近くの会場に入りGame Night。全てのアーケードゲームとスイーツが存在して、DDRの亜種みたいなものをやっている人もいた。英単語を当てるボドゲで"truck"の意味を調べ始める人を観測する。海外勢とも少し話した(listeningが壊滅的にできない)。WFにどれくらい行けそうか聞かれたので、80%くらいかな～と答えた。これが特大のフラグになるとは知らずに...

day 3

コンテスト

ucupと同様に、自分が環境構築を済ませて後ろから読む。Kが通されているので読むが、自明ではないように見える。yumaが解けたと主張したので、PCを渡して別の問題を読解する。
Hを見るとARC152-Cをすぐに思い出して解法がわかった(負けた回なので)。KのAC後yumaに引き続き書いてもらうが、REで2ペナを出してしまった。配列外参照は提出前に指摘できるべきだった...

3完の後Eを考察する。O(NQ)の解法を提示すると、Moで高速化できることを指摘される。そのままだとmaxの取得にlogがかかってしまうが、Rollback Moを使えばinsertだけなのでlogを落とすことが出来る。去年の夏合宿でやられた記憶があるのですぐに気付けた。kumaのFと並列で進めながら通す。

yumaからB(ゲーム)を渡されるが、2値化した後の問題が解けない。諦めて他の問題を読むと、木クエリのDが目に留まる。dpでO(NQ)が出来てSTTで高速化する問題。yumaのB,kumaのIが通ったあたりで残り73分あり、9完争いになることを確信する。

空書きだったため構築を思い出すところから始めたが、半開クラスタの定義を勘違いしていて結局Nyaan解説の形式で書き直すことに。構築パートを書き切ったあとは30分ほどしか残っていなかった。急いでモノイドの合成を書くがSampleの答えすら合わない。kuma,yumaもデバッグに加担してくれていたが、結局Sampleが通ることはなくコンテストが終了した。

YesNo

bogosortが4:43時点で2問提出していることを聞いて負けを悟り、深く絶望した。自チームは凍結後の提出がないため、他のチームのYesNoを待つだけの形になった。結果、bogosortにDとIを通されて京大内2位。自分たちの敗退が決定した。

タイム差は300以上あったため、Dさえ通れば逆転できただろう。STTのライブラリを持ってくるか、HLDが一瞬でも頭をよぎっていればACできたかもしれない。ucupでは木クエリを自分が毎回処理していたし、LC埋めで苦手意識はなくなったと思い込んでいたので、解法を詰める地力が敗因になったことにひどくショックを受けた。何よりチームメイトが作ってくれたWFのチャンスを自分が無碍にしてしまったことが非常に申し訳なくなった。

Closed ceremony後

会場内で夕食を済ませたのち、Lantern Festivalなるものに向かった。イルミネーションや屋台が並んでいたが、両替していなかったので特に何も買わずに帰宅した。

day 4

Excursion。石門水庫というダムで小型のクルーズに乗り込む。島で謎のゆで卵をもらった。昼食でFox is cute(2位のチーム)とチーム名の由来やコンテストの話などで少し交流する。
午後は大渓老街に向かい、周囲の公園を散策したり月光餅を頂いたりした。年季の入ったスタバに入っていくチームも存在した。

夜はコーチ2人と自分で夜市に向かう準備をする。既に北大や東大、会津大などの面々が駅前に集まっていた。しかし、平日だからか屋台の活気があまりなく、結局近くの居酒屋に押し掛けることになった。飲み会では各大学のICPCチームの組み方や大学オンサイトなどの話をした。
お開きの後で北大erとゲーセンに行く。日本にはない、縦長いjubeatみたいなゲームにcapsuleの曲が入ってて時代を感じた。数年ぶりにmaimaiをやって腕が破壊された。

day 5

ホテルのチェックアウト。空港のお土産に高めのウイスキー(KAVALAN)などを買った。

今後のこと

ここで宣言している通りだが、学生最強コンやAJOは権利があればまだ参加しようと思っている。レートを伸ばすモチベが失われてしまったのでオンラインで出ることは少なくなるが、人々との交流は学業に支障をきたさない範囲で続けたい。

最後に、3年間チームを組んでくれたyumaやラストイヤーで入ってくれたkuma、今回コーチとして諸々の手続きをしていただいたnaniwazuさんと物理好きにはとても感謝している。このメンバーでWFに行くことが叶わなかったのは残念だが、毎週のucupやバーチャルでの練習は苦しくも楽しい時間だった。同校チームのbogosortやTHSも実力的には拮抗しており、ライバルとしてこれ以上ない存在だったと思う。bogosortにはWFで存分に暴れてほしい。
来年以降はコーチとして、何らかの形でICPCのコミュニティに還元できたらと考えている。ICPC運営や懇親してくれた選手・コーチ含め、今までありがとうございました。

余談

github.com
コンテストで使用したライブラリを公開します。Static Toptreeは入れた方がよいです。

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に出られるようもう少し努力してみたいと思う。まずは精進を続けるところから。