ICPC 2026 国内予選 参加記（Today視点 / チームNordseestrasse）

この度ICPCの国内予選にチームNordseestrasseで参加し、全体17位で（おそらく）通過することができました。 その参加記を書きます。

チームメンバー

Today03 AtCoder青。この記事の著者。実装＋典型担当。今年がラストイヤー。

tardigrade AtCoder青。一緒に組むのは3年目。これまでの国内予選をすべて通過している。オールラウンダー。考察、実装両方の手助けをしてもらう。同じくラストイヤー。

参加記：ICPC 2026 国内予選参加記 | akTAR.'s Blog

RWD ICPC初参加。競プロを初めて1年ほどだが成長が凄まじく、参加時点でAtCoder青。キーボード配列や環境の違いもあり今回は考察に注力してもらう。

事前練習

1週間に1~2回チーム練習しました。私とtardigradeくんはこれまでの国内予選の練習を通して過去問をだいぶ解いてしまっていたので、台湾やインド、アメリカの国内予選などで練習しました。

実装はほとんど私がする予定だったので、テスト環境やライブラリなどの整備もしました。 この機会にマクロとテンプレートもかなりガチガチに作りました。1ヶ月ほどですっかり新しい環境にも慣れました。（横浜では結局テンプレ無しでコーディングしなければいけないのですが。。。）

練習途中でありえないバグも発覚し、肝が冷えました。

コンテスト

16:30コンテストスタート。

A問題

どう処理するか少し悩んだが、 C_i=1, 2 があるなら場合分け、ないなら \max を出力でOK。AC（0:02）。

B問題

左から見ていってできるだけ右においていく貪欲。AC（0:05）。

終わった後考えると区間スケジューリング問題の双対問題になっていた。（参考： https://drken1215.hatenablog.com/entry/2018/07/21/224200 ）

C問題

ちょっと迷った。最初は最終的な水たまりの縁となる点に着目して考えていたが色々と場合分けが必要そう。tardigradeくんに、底を固定すると左と右にそれぞれ自分より高い地点があればよいと言われて、たしかにとなる。そのまま実装してAC（0:11）。

D問題

問題文を読んでかなり嫌な気持ちになる。

とりあえず愚直を書いて実験してみると法則がありそう。これをそのまま実装するのもちょっと面倒なのでうまいこと解けないか考えたが、厳しそうなので法則をそのままコードに落とし込む方針でいくことに。とりあえずRWDくんにE,Fに行ってもらってtardigradeくんと詳細を詰める。 S=1 か否かと {K}\lt{S}^{2} であるか否かで場合分け、さらにその中でも色々と場合分けが必要で、頭を壊しながら実装。しかし細かいところが違うのかサンプルが合わず。

しばらくしてRWDくんにEの進捗を聞くと解けていそうとのことだったので私はEに行き、残りをtardigradeくんに任せる。Eから戻ってきてtardigradeくんに詰めてもらったとおりに実装する。私の実装と齟齬があったのか一部合わないケースがあったが、ランダムテストとにらめっこしてなんとかAC（1:06）。

苦しかった…

E問題

RWDくんに考察してもらった。

ジェム付きの瓶を一個購入すれば残りのジェムは無料ですべて手に入る。残りのジェムなしの瓶についても考えるが、ジェム付きのよりも安いものは適宜入れ替えて考えれば良い。結局一番安いジェム付きの瓶を買って残ったものは高いものから貪欲にジェムで購入、残りは自前で購入すれば良い。実装は簡単で割とすぐにAC（0:47）。RWDくんにはFに行ってもらい私はDに戻る。

F問題

これも考察の大枠はRWDくんにしてもらった。

M が小さいので、長方形の端（＋スタート点）になっている座標でグリッドを全部区切ってしまって良い。そうすると \mathcal{O}({M}^{2}) 個の長方形になるのでその4隅に代表となる頂点をおいてダイクストラをすれば解ける。

方針は簡単なのだがとにかく実装がヤバそう。手元にグラフライブラリとグリッドを扱うライブラリ（2次元座標↔1次元座標の変換をしてくれたり4近傍を取ってくれたりするライブラリ）があったので総動員して実装する。なぜか処理途中でreturnしてしまっていたりクエリのxy座標を逆にしてしまっていたりと実装ミスはあったが、なんとかサンプルが通ったので投げたら一発でAC（1:58）。これはかなり嬉しかった。

G問題

3人でああでもないこうでもないと言いながら考察。

途中でRWDくんが、初めて衝突する点を固定すると上左か上下か左下の3通りしかなくて、重複もなく数え上げられそうという考察をしてくれる。

かなり正しそうなので私はとりあえず純粋な経路を数え上げるDPパートだけ書き始めて2人に詳細を詰めてもらう。ちょうど書き終わったあたりで詳細まで詰め終わっていそうだったのでそのまま最後まで実装。サンプルを試すと H=2 のケースだけ合わない。残り時間も少なかったのでそれだけ場合分けしてお祈りしながら提出してみるとAC（2:43）。 H=2 がサンプルにおかれていたことに感謝。

H問題

Gと並行しながら考察していた。とりあえず最終形と作る順番をそれぞれ順列全探索したい。なんとなくそれぞれのパートを順列全探索からbit DPに改善するんだろうな〜と思っていたが詳細までは詰めきれずに終了。

感想

ここ最近、個人的に競プロの調子が悪く、AtCoderのレーティングもモチベーションも下がり調子だったので、予選突破できるかかなり不安でしたが、蓋を開けてみれば好成績で通過できてかなり嬉しいです。しっかり役割分担ができ、それぞれの得意領域がうまく噛み合った結果だと思っています。

横浜大会までにチームだけでなく個人の地力も高めて、今度は悔いなく自信を持って臨めればいいなと思います。

余談：Playoffについて

本題とはそれてしまうのですが、この機会に供養しておきます。

去年組んだチームAkai_Koibitoで、Taichung RegionalからPlayoffに進出できたのですが、私は参加できずに終わってしまっていました。

これはPlayoffの日程と国際学会の予定が被ってしまった結果、かなり無理なスケジュールになってしったことが原因です。

Playoffは場所が台湾、日程が03/06~03/09（08日競技）だったのに対し、学会の日程が03/04〜06、場所がなんとイタリアで、両方に参加するためには以下の条件をクリアすることが必要でした。

  • 私の発表日程を事前発表されていたプログラムの03/06から03/05以前にずらしてもらう
  • （時差も含めて）03/06〜07中にイタリア→台湾に渡航する

運営の方の取り計らいもあり、1つ目の条件はクリアできたのですが、2つ目が満たせませんでした。。。

もともとのスケジュールに無理があったのもあり、途中オランダのアムステルダムで50分で乗り換えるルートしかありませんでした。

それだけでも相当やばいのですが、なんと1便目のイタリア→オランダ便が遅延し、オランダについた時点で残り20分くらいしか残りませんでした。しかもEU圏内から出る都合上、一旦ここで出国審査を挟む必要があります。

係の人に協力してもらったりして爆速で出国審査を通過して全速力で出発ゲートに走ったのですが、あと一歩で飛行機出発に間に合いませんでした。無念。。。一応翌朝出発して競技当日の朝に台湾に到着する便も残されていたので、カウンターで掛け合ってみたのですが、無理とのこと。ここで参加が不可能なことが確定。

結局翌日の昼に出発して競技当日の夕方に到着する便に振り返られました。合わせて取ってもらったホテルは清潔かつ広々としていてとても良かったです。

この振替便が上海での乗り換えが必要な便だったのですが、なぜか上海で一旦入国・出国審査させられ今度もまた乗り換えがぎりぎりになったのと、ここでバゲージロストが発生して、泣きっ面に蜂といった様相で台湾に到着し、チームメンバーと合流することに。バゲージロストに関しては台湾の空港の方がかなり親身に対応してくれて、台湾出発までに再会できました。感謝。

チームメンバーだったtardigradeくんとtitanくんには、2人で戦ってくれたことへの感謝と申し訳なさに堪えません。

今年こそはこの回のリベンジが果たせたら嬉しいです。

ICPC 2025 Asia Taichung Regional 参加記（Today視点 / 競技）

こんにちは。Today03です。今回はチームAkai_KoibitoとしてICPC 2025 Asia Taichung Regional Contestに参加したので、その参加記を書きます。競技に関すること以外についてはこちら。

today-or-yesterday.hatenablog.com

ICPCに参加するチームは（国内予選→）Regional Contest→Championship→決勝という流れでコマを進めることになります。Regional Contestは世界各地域で行われる大会で、1チーム2大会まで出場することができます。Akai_Koibitoは国内予選で進出の決まったYokohama Regionalと今回参加したTaichung Regionalの2大会に参加することになりました。

今回わざわざTaichung Regionalに参加したのは、去年チームHokkaidoDekkaidoとして出場した2024 Asia Yokohama Regionalで次のステージであるAsia Pacific Championshipにあと一歩のところで届かず悔しい思いをしたから、というのが大きいです。去年同じチームで戦ったtardigradeくん、今回がラストイヤーのtitanさんとも合意し、今回の出場を決意しました。

メンバー

  • tardigrade(ta) 考察要員。ICPC経験が豊富。Todayの知らない・詳しくないことを多く知っており頼りになる
  • titan23(ti) 実装要員。データ構造に詳しい。ヒュが強い。愚直解・ランダムテストやライブラリ写経を嫌な顔せずやってくれる。
  • Today03(to) 考察・実装要員。フローや畳み込みの問題が好き。筆者。

競技記録

序盤

9:35、選手の入場に時間がかかり、5分遅れで競技がスタート。ひとまずtoがvimrcとtemplate等を書き、tiとtaに問題を読んでもらう。Aがすぐ解けていそうだったのでtiにPCをパス。AC。

実装してもらっている間に問題文を読み漁っていると、Mにグラフの図があってとっつきやすそうだったので読んでみると書かれていることをやるだけだったのでtoが実装、AC。

そうこうしている間にtaがEを読解してくれて簡単そうだったのでtoがtaから概要を聞き実装、AC。

その間にtiがFを読解してくれていて、区間の片方を固定したときの区間GCDの値の大きさは長さに対して単調なので両端点のどちらかをとればいいですねとなりtoが実装してAC。

続いてtoとtaでBを考察し、その間tiに他の問題の読解をしてもらう。バスに乗る回数は1回でよく、バスのスタート位置とクエリで与えられるスタート位置をまとめてイベントソートすれば良さそうとなりtoが実装してAC。

この時点で5完43分全体7位。ここまでは絶好調だった。

中盤

その次にI,Kを読む。Iはtaが問題を読んだ瞬間に「これは凸包の辺で切ればよいですね」と言ったので、ひとまず幾何ライブラリの写経をtiに任せる。

その傍らでto,taで可能そうな見た目をしているLを考察する。

最初、高さをNから降ろしていって仕切りがぶつかったときに問題を仕切りの左右で分けてそれぞれO(問題の幅)で解く分割統治もどきを思いつく、が最悪ケースでΘ(N2)かかりそうなのでまだダメそう。その後、このようにして問題を分けた場合、問題の個数はO(N)個に収まり、なおかつ問題を長方形に分けたときに縦の長さと横の長さの短い方の合計なら抑えられそうということに着目し、この方針で進めることにする。

方針が定まった以降はtaにはIの方に行ってもらい、toがLの細かい部分を詰める。横の長さが短い時は長方形内でソートするだけでOK。縦の長さが短いときは、区間[l,r)に高さh以上の要素がいくつあるか、をそれぞれ取得して、右に寄せてimosで処理できる。区間の情報取得にはマージソート木が必要なので書く。それとは別に、問題を再帰的に分割していく際、[l,r)における最大高さを求める必要があるのでそのためにセグ木も写経。

実装を終えてサンプルを試してみるが一向に合わない。まずセグ木で区間maxではなく区間minを取得してしまっていた。さらに分割統治や実際に縦横の長さごとに処理するパートで添字のoff-by-oneでバグっていた。ここまでを修正するのにもだいぶ時間がかかった。

さらにtiに作ってもらった最大ケースでテストをしてみたところ一向に実行が終わらない。なんとマージソート木の構築がボトルネックになっていた。ノードのマージを線形じゃなくてソートでログをつけると死ぬほど遅くなるらしい。*1ここまでをネチネチ修正してようやくAC。

toがKに苦しんでいる間に、PCをちまちま交換しながらtiとtaにIに取り組んでいてもらっていた。こちらもこちらで写経ミス等があり色々と苦しんでいたらしい。KのACの少し前に通っていた。

終盤

ここまでで7完。この時点で次に解かれていて、なおかつ北大勢の片割れであるy_1も通していたLに突撃する。

最初、操作による答えへの寄与は+2,0,-2のどれかだから+2だけを貪欲にやればOKです！ｗと叫んで投げてみたらWA。この解かれ具合でそんなに簡単なわけがなかった。その後ちゃんと考えると、A[i]=(S[i]≠S[i+1]?1:0)という長さN-1の配列Aを添え字modKごとの配列に分割し、その後、「長さ2の連続部分列を選び01flipする。1の個数を最大化しろ。」という課題を全体の操作回数上限Mでやる問題に言い換えられるところまで考察できた。ちなみに、雑に計算量を見積もるとΘ(N3)かかってTLEしそうだが、ちゃんと丁寧に詰めると実はO(N2)になっていることがわかる。

早速実装してみるが、tiに書いてもらったランダムテストと合わない。実はこれだけだと不十分で、先頭と末尾だけ特別扱いしなければならない。細かい添字をtaと相談して詰めてなんとかAC。だいぶ辛かった。

この時点で残り30分くらいだろうか。皆でKを考えるもののなかなか進まない。「こんなの愚直以外で解けたらやばいだろ。。。」と思いつつ（実際そうでした）、なんとかそれっぽい解法を捻り出そうとするが当然出てこず、そのまま終了。

最終結果と所感

YesNoの結果、最終結果は8完20位でした。現時点ではAPACは厳しそう。*2Kが解けていればだいぶ違っていたでしょう。

中盤以降で失速してしまったのが悔やまれます。あとLでTodayが投げた嘘解法が後から考えるとあり得なすぎる。せっかくランダムテストを爆速で書いてくれる人員がいるのだから、このあたりは丁寧にやるべきでした。ただ、序盤に上々な滑り出しでスタートできたのはこれまでの練習の成果と言えるかもしれません。

Akai_KoibitoはYokohama Regionalにも出る予定です。簡単枠の早解きはもちろん、勝負枠（AtCoder青〜黄diffレベル）を素早く確実に通して上位、欲を言えば10位代前半に食い込みたいです。

*1:実は原因はソートではなく、配列外参照検出用のコンパイルオプション -D_GLIBCXX_DEBUG でした。遅くなることがあるのは聞いたことがあったのに完全に頭から抜けてた。

*2:Asia Jakarta RegionalでNational Taiwan Universityのチームstd_absが優勝したおかげで、Taichung Regional上位のNational Taiwan University勢がごっそり抜け、APACに参加できる確率がかなり上がりました。

ICPC 2025 Asia Taichung Regional 参加記（Today視点 / 競技以外）

ICPC 2025 Asia Taichung Regional参加に伴う台湾渡航記です。渡航期間中の日記を抜粋・加筆したものになります。

競技については殆ど触れません。競技パートの参加記はこちら。

today-or-yesterday.hatenablog.com

金曜

ほとんど眠れなくて、明け方頃に目が覚めてしまったので起きておくことにした。台湾荷物最終確認、水抜きなどをして8時頃に自宅を出発した。

札幌駅始発の快速エアポートを狙って席を確保してそのまま気絶。9時半頃に空港についたが、外貨両替（17000JPY→3000NTD）をした後そのまま集合の11時半まで気絶していた。

なお、新千歳空港はこれまで何回も利用したことがあるが、国際線側に来るのは初めてでなんだか異世界に来たような気分になった。

11時頃北大台湾勢で集合し、新千歳空港の味噌キッチンというレストランで昼食を食べた。1500円。

その後手荷物預けや出国審査等の手続きを済ませ、国際線ゲートを観光した。

予定より遅れて15時すぎから搭乗開始。飛行機内でも基本的に爆睡していたのだが、途中で機内食が出た。「Chiken or Beef?」と聞かれて「チキンとビーフっていった？」って意味で「Chiken or Beef?」と聞き返したらChikenと受け取られてそのままチキンパスタを渡された。味は普通に美味しかった。

台湾到着。

到着後は入国審査、手荷物受取を済ませた後、直結の地下鉄に行くまでの道中にあるフードコートで謎のご飯を食べた。ラムレッグのスープらしい。店員さんの前であたふたしていたら日本語で話しかけてくださったのが印象的だった。290NTD。（約1500円弱）

このスープ、ラムの膝肉部分が丸ごとスープに入っていたのだが、可食体積が見た目に反して非常に小さく、食べる難易度が異常に高かった。付属の素麺がなにげに美味しかった。

その後、空港から新幹線駅に移動するために地下鉄に乗ろうとしたのだが、ここでもアクシデント発生。なんと、自動券売機が200NTD以下の紙幣しか受け付けておらず、1000NTD札しか持ち合わせていないメンバーたちが切符やカードを変えないという事態に。傍にあった売店で崩して事なきを得た。（ちなみに、地下鉄はクレジットも使えるらしい）

その後、高鉄桃園駅に移動し、新幹線に乗り込んだ。直前だったため自由席券しか買えず、自由席も埋まっていたため最初は立つ羽目になった。幸い、次の新竹駅で側にいた座り客が降りたのでなんとか座れたが、そのまま立ったままのメンツは辛そうだった。

高鉄台中駅に到着後は、直結の台鉄新日鳥駅に移動し、台鉄台中駅に移動。高鉄台中駅（=新烏日駅）はすき家、ミスド、モスバーガー、一風堂など、かなり日本発祥のチェーン店が多く並んでいたのが印象的だった。

台鉄台中駅前の様子。高鉄台中駅（=新烏日駅）ではなくこちらが昔からの中心街っぽい。

そのままホテルへ行った。ホテルは2人部屋でコンセントが合計2つしかなく、延長コードなどを持ってこなかったことを若干後悔した。あとアメニティがタオル類しかおいておらず、スリッパは飛行機用に持ってきておいたのが役に立った。

23時直前、Akai_Koibitoのメンバーで集まって横浜用のチーム紹介スライドを大急ぎで作成して提出した。

この日はセブンで夜食と次の日の朝食を購入した後、シャワーを浴びて就寝。

土曜

起床。天気は快晴。

眠気なまこをこすりながら準備して台中駅でy_1と集合した。その後新烏日駅に行って朝食を探すものの、時間的にやっているところがなかったため、急遽地下鉄で隣の烏日駅に行って散策した。

良さげな中華料理屋があったのでひとまず入って魯肉飯と総合麺（牛肉・大腸）を食べた。美味しかった。ただ、個人的には魯肉飯はちょっと脂っこく、野菜のトッピングをつけたほうが良かったかもと感じた。店員さんが僕らが日本人だとわかるとそれぞれのメニューについて英語混じりで解説してくれてとても良かった。100NTD。

烏日は新烏日と違って昔ながらの町並みといった感じでかなり異国情緒あふれており旅行体験としてよかった。

その後再び高速台中駅に向かってシャトルバスに乗り亜洲大学に向かった。

亜洲大学ではregistarとシャツ等の受取を済ませたあと、記念撮影をしてpracticeに臨んだ。

事前に配布されていたルールブックには、使えるエディタ一覧にVSCodeの名前がなかった。我々のチームは僕とtardigradeくんはVim勢なので問題なかったがtitanくんがVSCode使いなので懸念点だった。なぜかマシンにインストールはされていたので使えるのか使えないのか分からないまま、ひとまず使えないことを想定してVSCodeライクな代替エディタを探そうということになった。あと、キーボードの爪（少し傾斜をつけるためのスタンド）が片方取れており、スタッフに相談したところtrivial issueと言われてしまった。ちなみに結局VSCodeは使えたらしい。

practice後、そのまま行きのシャトルバスに1時間弱ほど乗って再び新烏日駅に向かい、少々電車の待ち時間を潰した後台鉄台中駅に帰ってフードコート（鐵鹿大街）で夕食を食べた。台湾ライクな鍋屋を適当に選んで海鮮鍋を頼んだ。200NTD。

夕食後、当初宮原眼科に行くという話が出ていたが予想以上に皆疲れていたのと少し遅くなったので今日は見送ることになった。なんとかABC前にホテルに着いたので強引にABCに出たら暖まった。

この日はABC後すぐにシャワーを浴びてさっさと寝た。

日曜

今日は早い時間に目覚ましをかけたが、15分ほど二度寝をしてしまった。急いで支度をして台鉄台中駅へ。ファミマでコーヒーを買った。コーヒーは日本と全く同じ味で安心した。

その後新烏日駅へ行きシャトルバスで亜洲大学に向かう。早々に荷物を預け、1時間ほど会場の外で待たされる。会場を散策したり展示物を眺めるなどした。

選手入場時刻になって、入場する。デカいティッシュとウェットティッシュを持ち込もうとしたら没収されてしまった。こういうのは前日においておかないとダメらしい。

競技開始〜終了

競技終了後、軽食コーナーでaizu_3の面々と話した。Iの幾何を解く際外積ライブラリが抜けていて困ったが気合でどうにかしたらしい。どちらが勝ったかは順位表解凍後のお楽しみですね〜みたいな話をして解散。

その後ホールみたいな場所に移動してスポンサーの方々のお話と問題の解説を聞いた後、YesNoに臨む。YesNoでは、一度再生したアニメーションが停止できないという不具合が発生したらしく、司会が超早口でチーム名を連呼していた。途中とんでもない長さのチーム名がいくつかあり、会場が盛り上がっていた。司会は大変そうだった。

順位確定後、表彰式が行われる。Akai_Koibitoは20位で銀メダルをもらうことができた。これまで競プロをやっていて、このように形で残るものをもらえたことがあまりなかったので嬉しい。

終了後は昨日同様、バスで新烏日駅に向かった後、電車で台鉄台中駅に移動し解散。ARCに出るというおここさんと、他の日本勢と夜市に行くというwinterさんとはとくんを除いたメンツで大魯閣新世界というショッピングモールのフードコートで夕食を食べた。

この日はワンタン（水餃子？）と牛肉麺を食べた。300NTD。うっかり2人前分頼んでしまったが、お腹がぺこぺこだったのもありあっさり食べれてしまった。

ホテルに戻りtitanくんとkotatsugameさんのICPCミラーの実況を観戦していた。

適当な時間で切り上げて就寝。

月曜

7:30頃起床。荷物のまとめと身支度をして出発。9:00頃新烏日駅からバスに乗りExcursionに参加した。

1地点目は文化部文化資産園区という公園のような場所。日本統治時代に建てられたワイナリーらしい。

2地点目は宮原眼科。本当に宮原先生という医師が作った病院だったらしい。アイスクリームショップになっている。アイスクリームはかなりボリュームがあって満足感◎。

建物の中身もハリー・ポッターさながらの内装がなされていて壮観。店員さんが流暢な日本語を話されていたのが印象的だった。

3地点目は昼食。ガッツリ台湾料理だった。

個人的には魚丸ごとののムニエルっぽいやつとエビの蒸し焼き？とホタルイカの唐揚げが好みだった。

4地点目は台中国家歌劇院というオペラハウス。このあたりは台中市の行政の中心地区らしくて、周りに高いビルが立ち並んでいてこれもまた壮観だった。

最後、5地点目はレインボービレッジ（虹彩眷村）という公園のような場所。ガイドの方の説明が全然わからずただの変わった公園だと思っていたが、後から調べるともともとは国共内戦で行き場をなくした大陸出身の兵士のための施設だったらしい。取り壊される計画が上がったが、このように一面に壁画を描くことで注目を集めて保存活動につながったとのこと。実は深い背景があった。

Excursionはこれで終了。かなり満足度した。ツアーガイドの人の説明を全て理解しきれなかった自分の英語力の低さが悔やまれる。

その後、高速台中駅から新幹線で高速桃園駅に移動し、桃園空港の隣駅のホテルへ移動。チェックインを済ませ、桃園空港の散策に出かけた。おここさんが飛行機に忘れたタブレットの受け取りを済ませた後、全員で夕食を探索した。迷った結果、ちょっとしたフードコートで食べることになった。僕はバーガーキングを頼んだ。

台湾でも「直火は美味い！」と書かれているらしい

その後、みんなで空港探索。空港展望台みたいなところがあり、雨風がすごかったが、新千歳や羽田のそれと比べると飛行機との距離が近くて迫力がありよかった。

お土産屋を探したが、この時間になるとどこも閉まってしまっており、かろうじて空いていた店でなんとか調達した。

その後ホテルに戻り、Akai_Koibitoの面々で軽く飲み会をした後（といっても酒を飲んでいたのは僕だけだったが）、シャワーを浴びて就寝。nmyさんとtitanくんはジムに行っていたらしい。シャワーを浴びて翌日の支度をすませて就寝。シャワールームにドアがなくて洗面所のほうがびちゃびちゃになってた。

火曜 18

5:45頃起床。この4日間でもっとも早起き。ホテル手配のバスに乗って空港に向かう。

まだ6時半だというのに空港にはそこそこ人がおり混雑していた。早めに保安検査を済ませた後、軽食を食べられる場所を探しつつおここさんと搭乗ゲートを目指した。nmyさんはいつも通り（？）単独行動、他の面子は空港探索にいったっぽい？搭乗ゲートに着いた後もお腹が空いて仕方なかったので途中見かけたマックでこっそり一人だけ朝マックを嗜んだ。60NTD。

搭乗後、早々に気絶してしまった。しばらくして目が覚めてふと周りを見渡すと、人がスッカスカな上、まだ飛行機は動いていない模様。かと思ったら急にぬるっと離陸した。異世界に迷い込んだか？と思ったが、どうやらこの時間込みでフライト時間が設定されていたらしい？（ならもう1時間搭乗時間を遅らせてほしかった）人がスッカスカなのは単純に需要の問題そう。一安心。

飛行機内ではチャットで遊んだり、winterさんnmyさんとミニゲームの麻雀をしたりした。

コンピュータが弱すぎてゲームバランスが崩壊していた

機内食はビーフの方を選択。美味しかった。

新千歳空港に到着。手荷物受取ロビーに麻薬探知犬がいて思わず視線を奪われてしまった。

その後空港のフードコートで遅めの昼食を取った。僕は吟しゃりでthe日本食を食べた。1200円。

帰ったら即洗濯するぞと決心しながら帰宅してそのまま気絶した。

台湾渡航に関する所感

コンテスト関係なく、とても楽しかった。看板や各種施設のホームページには日本語の説明が付いていることも多く、日本語で話してくれる店員さんも少なくなかったので、海外に行ったことがないや語学に自信がない人でも行きやすい国だと感じた。食事も美味しかったしExcursionも面白かった。これまで海外旅行に行ったことが少なかったので学生のうちにこういった体験をできて良かったと思う。

ただ一点、トイレ事情には注意。台湾のトイレには紙が常備されていないところも多く、しかもトイレに紙を流してはダメという制約がある。僕はかなり不安だったので箱ティッシュとウェットティッシュを常に持ち歩いていたのと、渡航1週間前から渡航中にかけて毎食事後にビオフェルミンを飲んでいた（そのおかげでお腹の調子はすこぶるよかった）。お腹を壊しやすい人は注意。

ICPC 2024 Asia Yokohama Regional 参加記 (Today / HokkaidoDekkaido)

記録（競技）

Today です。今回 ICPC 2024 Asia Yokohama Regional に、チーム HokkaidoDekkaido として参加したので、その参加記を書こうと思います。

チームメンバー

HokkaidoDekkaido

  • Today

    筆者。特筆すべきことのない一般青コーダー。ARC強くなりたい。以下to。

  • kouty

    期待の新人。数え上げ強い。考察強い。もうすぐ黄色になりそう。以下ko。

  • tardigrade

    チーム唯一のYokohama複数回経験者。知識豊富。めっちゃ頼りになる。以下ta。

結果

7完17位、Playoffにはあと一歩届かず。。。悔しい！！

国内予選後から競技前日まで

国内予選が終わってからチーム会議をして、去年からPlayoffってのがあってめっちゃ頑張れば行ける可能性があること、本気で頑張ること、週に1回はチームで5h走ること、等々を確認しあった。

5hの練習は基本UCup、有志コンが生えたら有志コン、直前期は過去問から適当に見繕ってバチャを作るなどしていた。 毎週研究室を開けて3人で集まり、本番と同じUbuntu+Vim*1+Lenovoのキーボードの環境を用意して取り組んだ。

私個人の実力が上がった実感はあまりなかったし、特にUCupに関しては青コーダーの私には荷が重すぎるように感じていたが、それでも着実にチームとしての実力は上がっていたらしい。 お互い何が得意かは大まかに把握できていたし、チームの動きも回を追うごとに洗練されていった。 本番での3人のコミュニケーションで不都合を感じることは、私としてはほとんどなかった。

競技前日

オープニングと競技リハーサル、チーム紹介があった。

オープニングでは競技に関する説明が英語でなされていた。手元にもルールブックが3種類ほど配られ、ざっと目を通したが特に変わったことは書かれていなかった。英語の説明をちゃんと聞いておけば大丈夫だと思う。

リハーサルは4問で、Aは数列の総和を取るだけ、Bはインタラクティブ練習、Cは普通に過去問、Dも過去問で浮動小数点数で答える問題だった。

確認したこと

  • ログインの方法
  • PCのセットアップの流れ
  • ジャッジの速さ（最大何回のsetへのinsertができるか、やQCFium流pragmaがどのくらい有効かなど）
  • インタラクティブ問題用に配布されるデバッグツールの使い方
  • インタラクティブ問題での不正なクエリや制限回数越え、assert(false)をした際のジャッジ挙動など（過去問でAC以外が全てREになるあり得ない問題に遭遇したため、一応念入りに）
  • 浮動小数点数の出力の仕様

諸々終えてホテルにチェックインして長めの風呂に入るなどしていたらだいたい21時だった。ABC385があったけど、断腸の思いで見送ってぐっすり9時間くらい寝た。

競技当日

6:30ごろ起床してシャワーと軽食を済ませた。

前日リハのときにデバッグ用のコンパイルコマンドをつけた方がいいかもと感じていたので、この記事の内容をChatGPTにまとめさせたものを急遽印刷してライブラリに加えた。これは結果的に大正解だった。

競技開始~2完

9:15 唐突に競技が始まった。toがパソコンにログインし、bashrc(alias 'g++'='g++ -std=c++20 -O2 -D_GRIBCXX_DEBUG -Wall -Wextra')とvimrcを編集する。その間にkoとtaがAを読む。

設定、Aの読解が終わり、ざっくりと解法を説明してもらう。toとtaが実装担当し、koにはBを読んでもらう。

toが簡単な尺取りを実装し、サンプルを試しながら微修正して投げる。WA。to、かなり焦る。toとtaでハックケースを探すが全然見つからない。

このあたりでkoがBの解法を生やしたのでtaと一緒に実装してもらい、toは引き続きAの穴を探す。

Aの穴が見つかった。koからパソコンを奪って修正し提出。AC(A: 0:26)。 すぐにBの実装も終わり提出。AC(B: 0:29)。 ここまでで30分くらい。想定よりだいぶ時間がかかってしまった。

~3完

順位表を見て解かれているE、Iから読み始める。 toはEを読解。有理数を持ちながらDFSやるだけに見える。解法は簡単だが実装が面倒。他2人に「そっちの解法が生えたらすぐ代わるのでとりあえず実装します」と伝えて実装開始。 有理数構造体の演算周りでコンパイルエラーを出しながらも何とか実装を終えてサンプルを試すがなんか合わない。このあたりでIのそれらしき解法が生えたので実装してもらい、toはコードを印刷してどこが間違っているかを探す。Iの方も詰まっているっぽい？この辺で英和辞典片手にEの問題文を注意深く読み直すと、なんか「割り算は小数部分切り捨て」って書いてある。有理数構造体を書く必要なんて1mmもなかった。バカすぎ！！！！！

心の中で盛大なため息をつきながらEを実装して提出。AC(E: 1:20)。誤読で2~30分浪費してしょうもねーーーと思うも、ここからだと切り替える。

~4完

Iが行き詰まってたようなのでkoにはCに行ってもらうことにして、toとtaでIを見る。先ほどセグ木に区間の答えと約数全部を乗せる感じの解法を投げてTLEを喰らったらしい。 計算量を改善できないか考える。

この辺りでkoがCの解法を思いつく。Σを入れ替えると最短経路を考えれば良くなるとわかるらしい。天才。toが監視しながらkoに実装してもらう。AC(C: 1:51)。

~5完

IとKが解かれているようなのでIをメインにして並列で考察する。 taとtoで要らない情報を切り落とす枝刈りやセグ木からスパテに変更することによる定数倍改善を試すも、本質的な計算量改善には至らず苦戦する。

この辺りでtoがそれっぽい方針を思いつく。

koとtaに簡単な説明だけしてtoが実装する。添字のoff-by-oneがちょっと怖かったが、一発でサンプルが通ったので提出。AC(I: 2:20)。

~6完

Iの実装をしている間にkoとtaがKの考察を進めてくれていて、程なくしてkoが実装を開始する。途中で高速ゼータ変換を要求された。もともとライブラリにはなかったが、急遽追加したのがここで役に立った。

全日程Yの人がいるコーナーケースで1ペナを消費するもAC(K: 2:35)。

~7完

ここまでで6完。

順位表的にはDの数え上げが若干通されてて、あとはポツポツと言った感じだった気がする。

Dを3人で考察するも、なかなか進まない。数え上げはkoの担当なのでkoに引き続き考察を進めてもらい、toとtaで残りの問題の読解をする。

toが他のLの考察や他の問題の読解に苦労していると、koにDの入力から木を構築する関数の実装を頼まれる。考察も読解も全然進まず苦しくなっていたので水を得た魚のように実装をする。謎にバグらせるも-D_GLIBCXX_DEBUGのおかげでことなきを得る。

どうやらここまででkoとtaの間でそれらしき解法が生えていて、手計算でサンプルが合うことを確認できていたようだったので、すぐに解法部分をkoに実装してもらう。

程なくして提出。AC(D: 3:39)。これに関してはほとんど何もできていない。チームメイトに感謝。

~競技終了まで

7完。この時点での順位は15位で、程なくして順位表が凍結される。

物理好きさんのポストによるとこの時点でPlayoff当落線上。あと1完すればPlayoff濃厚といった状況。なんとしてでももう1完するぞと心に決めて次の問題に臨む。

F,G,Lあたりを並列で考察する。合間を縫ってtaがGの考察を進めてくれていて、入る矢印の数と出る矢印の数の比較による二分探索ができそうとなるも、細かいところが詰めきれず、行き詰まってしまう。

これ以上Gの考察は進まないだろうと判断してLに切り替える。

このあたりでtoがLの誤読をしていたことが判明！（この人、何回目？）それなら区間DP以外ないだろうとなるが、なかなか \mathcal{O}(N^{4}) から落ちない。

とりあえずtaに現時点で思いついている区間DPを実装してもらいながら、koとtoで計算量を落とせないか考察する。ラスト30分くらいでtoがそれっぽい方針を思いつく。taからPCを奪って大急ぎで実装をするも、細かいところを全然詰めていなかったのでサンプルが全然合わない。そのうちコンテスト終了のカウントダウンが始まって、修正したものをサンプルを試さずに投げてみるも当然WA。サンプルが全部合ったのはコンテストが終了してすぐのことだった*2。

閉会式

スポンサーの方々のスピーチと作問陣による解説のあと、YesNoが始まった。

会場の空気に合わせて一応の歓声や拍手を送りつつ、凍結時点で自分たちより下位だったチームに対しては内心で「通っていないでくれ！」と願いながら、YesNoを眺める。結果は2つ順位を下げての17位だった。

大会を終えて

国内予選終了時には「あわよくば」程度の目標だったPlayoffに、こんなに近づけるとは思わなかった。でも、ここまで来るとやはり悔しい気持ちの方が強い。

「あのときこうしておけば。。。！」と思う点は挙げると尽きない。でも、全体としてかなり調子良かったし、Lに歯が立たなかった時点で、この辺りが今の私たちの限界だったのだろう。もしまた来年同じチームで横浜に来れたら、今度こそ次のステージに進みたい。

結果に関係なく、本当に素晴らしいイベントでした。参加できてよかったです。ここまで一緒に練習してくれたチームメイトのkoutyくん、tardigradeくんに多大なる感謝を表して、この参加記を締めようと思います。 読んでくださってありがとうございました。

記録（競技以外）

色々ありました。長いので気が向いたら別記事にするかも。楽しかった。

*1:設定が楽だし、どんな場所でも同じ競プロ環境を簡単に再現できるのでとてもよかったです。

*2:後で聞いた解説とは全然違う方針だったのでサンプルがたまたまあっただけだと思います。ACが得られるかどうかは怖くて未検証です。 WAでした。はい

セグメント木上の二分探索の実装

この度、長年ブラックボックスとして利用していたセグ木上の二分探索を理解したので。

前提

  • 非再帰
  • 内部実装は 1-indexed
    • あるノード i の左の子ノードは i << 1, 右の子ノードは i << 1 | 1 で取得できる。
    • 元の配列の i の位置の値はノード i + n に入っている。

https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf

解きたい問題

（セグ木に乗った）数列 A と インデックス i と値 x が与えられる。 [i, r) における最大値が x 以下であるような最大の r を求めよ。

解き方

[l,N) の最大値を取得する際に参照するノードを並べます。これらのノードを、値をマージしながら左から見て行ったとき、条件を満たさなくなるノードがどこかしらに存在します。（存在しないなら答えは N です。）このノードを p とします。

p の子孫に r は存在するはずです。

今のマージした最大値（モノイド積）に、さらに p の左の子の値をマージした値が条件を満たすなら r は p の右の子の子孫なので p = p << 1 | 1 とします。

満たさないなら p の左の子の子孫なので p = p << 1 とします。

これを p が葉っぱになるまで繰り返します。

参照するノード数、木の高さ（ = p が葉っぱになるまでのステップ数）ともに O(\log{N}) なので、 O(\log{N}) で解けました。

実装例

一般のモノイドと判定関数に対応させています。

最初に fold(l, N) する際に参照するノードを cand に追加し、その後 cand で p を線形探索します。

p が見つかったらあとは葉っぱまで潜っていきます。

template <typename F>
int find_right(int l, F f) {
    assert(f(Monoid::id()));
    if (l == n) return n;
    // f(fold[l, x)) == true を満たす一番右の x を見つける
    l += n;
    int r = n + n;
    vector<int> cand_l, cand_r;
    while (l < r) {
        if (l & 1) cand_l.push_back(l++);
        if (r & 1) cand_r.push_back(--r);
        l >>= 1, r >>= 1;
    }
    vector<int> cand = cand_l;
    reverse(cand_r.begin(), cand_r.end());
    // 列挙したノードがセグ木上で左から右に並ぶようにする
    cand.insert(cand.end(), cand_r.begin(), cand_r.end());
    Type val = Monoid::id();
    for (int i : cand) {
        if (f(Monoid::op(val, dat[i]))) {
            // f(fold[l, x)) == true を保ったまま右方向へ伸ばせるだけ伸ばす
            val = Monoid::op(val, dat[i]);
        } else {
            // 伸ばせなくなったら、x はノード i の子孫なので、潜る
            while (i < n) {
                i <<= 1;
                if (f(Monoid::op(val, dat[i]))) {
                    // 左の子をマージしても条件を満たすなら、x は右の子供の方なので、1 つ右に行く
                    val = Monoid::op(val, dat[i]);
                    i |= 1;
                }
            }
            return i - n;
        }
    }
    return n;
}

その他

  • 二分探索の条件として、判定関数 f には単調性が必要です。

  • 左に伸ばす方の二分探索（f(fold[x, r))) を満たす一番左の x を見つけるやつ）はこれの逆をします。

template <typename F>
int find_left(int r, F f) {
    assert(f(Monoid::id()));
    if (r == 0) return 0;
    r += n;
    int l = n;
    vector<int> cand_l, cand_r;
    while (l < r) {
        if (l & 1) cand_l.push_back(l++);
        if (r & 1) cand_r.push_back(--r);
        l >>= 1, r >>= 1;
    }
    vector<int> cand = cand_r;
    reverse(cand_l.begin(), cand_l.end());
    cand.insert(cand.end(), cand_l.begin(), cand_l.end());
    Type val = Monoid::id();
    for (int i : cand) {
        if (f(Monoid::op(dat[i], val))) {
            val = Monoid::op(dat[i], val);
        } else {
            while (i < n) {
                i = (i << 1) | 1;
                if (f(Monoid::op(dat[i], val))) {
                    val = Monoid::op(dat[i], val);
                    i ^= 1;
                }
            }
            return i - n + 1;
        }
    }
    return 0;
}
  • 遅延セグ木の場合は、適切に遅延伝播しながら同様の処理をします。

atcoder.jp

template <typename F>
int find_right(int l, F f) {
    assert(f(Monoid::id()));
    if (l == n) return n;
    // fold[l, n) をする際と同様に遅延伝播処理
    generate_indices(l, n);
    pushdown();
    l += n;
    int r = n + n;
    vector<int> cand_l, cand_r;
    while (l < r) {
        if (l & 1) cand_l.push_back(l++);
        if (r & 1) cand_r.push_back(--r);
        l >>= 1, r >>= 1;
    }
    vector<int> cand = cand_l;
    reverse(cand_r.begin(), cand_r.end());
    cand.insert(cand.end(), cand_r.begin(), cand_r.end());
    MonoidType val = Monoid::id();
    for (int i : cand) {
        if (f(Monoid::op(val, dat[i]))) {
            val = Monoid::op(val, dat[i]);
        } else {
            while (i < n) {
                // 遅延伝播処理
                propagate(i);
                i <<= 1;
                if (f(Monoid::op(val, dat[i]))) {
                    val = Monoid::op(val, dat[i]);
                    i |= 1;
                }
            }
            return i - n;
        }
    }
    return n;
}
  • いちいち vector を生成している分、少し重いかも。

まとめ

長年の謎が解決して嬉しい