概要

2025/02/27 ~ 2025/03/02 の間にシンガポールで行われた The 2025 ICPC Asia Pacific Championship に東工大(現 東京科学大学)からチーム WADATSUMI として参加し、33位でした。

この大会はWorld Finalsの1つ前、準決勝に当たる大会です。
東工大からは他に AMATSUKAZE と Bocchi The Tech の2チームも参加していて、高順位で熾烈な争いを繰り広げていました。

Asia Regional以前について

国内予選 → Asia Regional → Asia Pacific Championship (今回の大会) という階層になっています。
国内予選、Asia Regionalについて参加記を書いています。

ICPC 2024 Asia Yokohama Regional 参加記(Nzt3 視点)

これは アドベントカレンダー2024 23日目の記事です。 概要 2024/12/21-2024/12/22に横浜産貿ホール マリネリアで行われた ICPC 2024 Asia Yokohama Regional Contest に チーム WADATSUMI として参加し、8完9位でした。 Asia Pacific Championship に参加できそうです。嬉しいですね。 チーム紹介 traPでガッとレーティング順に組んだ3人です。 * のつじさん(Nzt3): 私です B2 C++を使う 環境構築・問題文読解担当 * そたつ(Sotatsu): B3 Pythonを使う 全担当 * こめだわら(Rice_tawara459): B3 Pythonを使う 考察担当 使用言語が統一されていないので言語特化エディタを使うと複数エディタ同時起動になって設定が面倒です。今回はVSCodiumを使うことにしました。 今年のCodiumは拡張機能が入っていて補完が効くのでコーディング速度の向上が見込めます。

東京科学大学デジタル創作同好会traPNzt3

チーム紹介

traPでガッとレーティング順に組んだメンバーですが、組んだ後に変動があり現在はレーティングに差があります。

• Nzt3 筆者 B2
  • ライブラリ、PC担当
• Sotatsu B3
  • 知識担当
• Rice_tawara459 B3
  • AtCoder担当

大会準備

チーム練習

Asia Regional以前と変わらず、Universal Cup に参加したり、平日に対面練習をしたりしていました。
AMATSUKAZE(3人揃っている)、Bocchi The Tech(1人しか来てない)との合同対面練習もありました。
AMATSUKAZEがめちゃくちゃ強くて、全然勝てません。ほとんどの回で完数差をつけられています。

ライブラリ

Asia Pacific Championship では Team Notebook として紙25枚(A4,片面印刷)を持ち込むことが許可されています。
Contest Rule ではなく Contest Environment のページの方に書かれています。

Printed Team Reference Document (Team Notebook)

• This document may contain up to 25 pages of reference materials, single-sided, letter or A4 size, with pages numbered in the upper right-hand corner and your university name and team name printed in the upper left-hand corner.
• Text and illustrations must be readable by a person with correctable eyesight without magnification from a distance of 1/2 meter.
• It may include hand-written comments and corrections on the fronts of pages only.
• Each team will be permitted to bring three copies of the Team Reference Document described above.

文字の大きさに「50cm離れたところから読むことができる」という制限があり、謎です。
ページ数、大学名、チーム名の記入が必要ですが、これは ICPC notebook を用いれば問題ありません。
私のチームでは Speed Star からSimplex、block-cut-Treeなどを取り除いて双対セグ木、Binary Trieを入れ、Relaxed Convolutionを差し替えたものを用意しました。
行ハッシュを入れたかったのですが、ICPC notebookの設定をいじるのは面倒くさそうだったので関数ハッシュ(人力)を入れました。

マスコット

Contest Environment のページに書かれています。

Mascots.

• Plush animals or figures.
• Loud and distracting mascots are prohibited.

音が出るやつ、動くやつ、光るやつはだめそうです。

今回私が用意したのはこちらの周央サンゴ(にじぱぺっと)です。

ところで、この記事を公開した前日3月6日は周央サンゴの誕生日です。周央サンゴは年齢を固定するタイプのキャラクターなので一般の誕生日ほど重要な役割はありませんが、年1回の特別なイベントとして特別仕様の商品を販売してくれたり、特別なコラボ配信があったりと、そこそこ嬉しさに貢献してくれるのでいいですね。
今年は誕生日逆凸にかなり多くの人が来ていて楽しかったですし、HPの開設という非常に大きな変化もありました。今後の周央さんの活動もしっかりと見て、聞いていきたいですね。ンゴちゃんはどこに向かっていくのでしょうか。ANNAのパーソナリティとして選ばれたときも驚きましたが、今後も幅広くなり続ける活動が楽しみです。 #ンゴンゴ今日もかわいいンゴ #周央サンゴ生まれたンゴねぇ2025

~Day0

海外の電源プラグの形は日本と異なります。シンガポールのプラグはBF型だったので変換プラグを買いました。
(スポンサーブースで万能変換プラグをいただいたので結果的に自分での持ち込みは不要でしたが、これを予測することは不可能です。)

パスポートを取得してシンガポール入国の準備をします。日本→シンガポールはビザ不要で、オンライン入国申請を事前にやっておけば良いらしいです。姓と名の順番がわからず順番だけ変えたものを2つ送ってしまいましたが、問題なく入国できました。

それ以外は国内と大した違いはありません。

Day1 (02/27)

日本(成田空港)を出発し、7時間飛行機に乗っているとシンガポール(Changi空港)に到着します。国際線あるあるの「英語と日本語でアナウンス内容が違う」があり、感動します。

シンガポールは暑い！といっても日本の7月上旬くらいの気温です。半袖で快適に過ごせます。

Changi空港で両替して現地通貨を入手し、Grab(タクシー、今回は競技会場などの行き先について運営からチケットが支給されている)で競技会場であるCOM3(シンガポール国立大学COM3棟)に向かい受付します。コンテスト参加者用のポロシャツを着てチーム写真を撮りました。

スポンサーのJump tradingのブースで水筒をいただいたり、2023,2024のWF出場選手の話を聞いたりしました。日本で活動していないクオンツ系企業何もわからない……

Day2 (02/28)

NUS UCC(シンガポール国立大学 University Cultural Centre)で開会式がありました。会場は強い冷房がついており寒く、上着が必要です。スポンサーであるHUAWEIとJane Street、Jump tradingのお話(Jane Streetは去年と同じだったらしい？)を聞いて、IOI運営代表?の先生の話を聞きました。
会場の椅子は振動が伝わりやすいのかよく揺れました。どういう構造になっているのでしょうか。

リハーサルがありました。私のチームはYokohama大会と同様に次のことを行いました。

• 実行用スクリプトの動作確認
• ジャッジステータスコンプリート
• 質問を投げる
• 普通に問題を解く

今回はエディタとしてVSCodeを使用します。拡張機能は入っていませんでした。
CLionだとcopilot(弱い)が使えたらしいです。このことについて「PCに入っている全てのソフトウェアを用いて良い(つまり、copilot補完も使用して良いし、表計算ソフトも使用可能)」という連絡がありました。

問題は謎の埋め込み問題が1問、去年のAsia Pacific Championshipの問題が2問(可能枠最難関と不可能枠)、インタラクティブの例題が1問でした。不可能枠を実装しきっているチームは何？

1チームに割り当てられている机が小さい、PCが机の中央にあり実装・考察分担がやりにくい(PCを移動することは許可されていた)、チームを仕切る壁が小さく対面のチームの手元が見える、キーボードがノートパソコンのもので打ちにくい、意図せずinsertキーに触れて入力ができなくなるなどちょっとした不満はありました。

リハーサル終了のタイミングでライブラリとマスコットの回収がありました。

リハーサル後はスポンサーのブースを回ります。
HUAWEIのブースにはチェス、オセロ、UNOなどの頭を使うゲームと、サッカー盤がありました。
Jane Streetのブースにはパズルがありました。パズルを解いて秘密の番号を特定し、鍵を開けてバッジを獲得！という楽しいブースでした。
ミルクパズルもありました。面白いパズルの中にただの苦行を混ぜないでください。

夕食はICPC APAC 2025 dinner courtesy of Jane Streetということでめちゃくちゃ良いホテルでめちゃくちゃ良い飯を食べました。マーライオンの近くだったので途中で抜け出してマーライオンとマリーナベイ・サンズを見に行くこともありました。
スネ夫が自慢話をするときに流れている曲とマリオカートでしか見たことがない景色がありました。

Day3 (03/01)

コンテスト当日です。

大学ごとにチームが呼ばれ、会場に入場していきます。荷物はコーチに預けました。荷物番をするコーチは5時間身動きが取れなくて辛そうです。

コンテスト

コンテスト中の話を書きます。

初動

問題が難易度ランダムに並んでいるため、最初のACが出るまで難易度情報が皆無。
自力で自明枠を見つけられれば良いけど、順位表監視を怠らない。

Nzt3がエディタを設定し実行用スクリプトを書いている間にRice_tawara459,Sotatsuが問題を読む。

Nzt3がテンプレを書き終わり問題を読む段階に入ってもまだ順位表は動かない。

L

Lに最初のACが出る。
すぐに問題を読むと隣接マスの差分関係が保持されるからそれを数えれば良いとわかる。
Nzt3が実装するがミスがありWA すぐに修正して L-AC(0:35 + 1)

AJG

順位表情報ではGが通されまくっている。
問題を読むと

01列B,Cがある。
01->0,10->0,11->1 という3種類の変換をうまく用いてB->Cに変換できるか？

という問題に見える。これは1を自由に消しているだけなので0で区切ればやるだけ、ということでNzt3が実装→ WA
すぐにはミスが見つからなかったので印刷してPCを空ける。

その間に Sotatsu が J を実装するもサンプルが合わない。方針を確認すると、正しそうな区間DPだった。
これも印刷してPCを空ける。

Rice_tawara459がAの考察に詰まっている。3人が3問に詰まっている嫌な状況。

Rice_tawara459が解法を生やし実装して A-AC(1:13)

Sotatsuが区間DPの添字を間違えていたことに気づいて修正。 J-AC(1:21)

Nzt3が00->0という4つ目の操作の存在に気づいて修正し G-AC(1:24 + 1)

この時点で 5完(AGJL+1問)が6チームいたけどどのチームも5問目が違う。4完(AGJL)は大量。

解かれている問題は全て共有する。

とりあえず3問を3並列で考えることになる。
Nzt3がK、Rice_tawara459がH、SotatsuがIを考える。

H

Rice_tawara459がHの方針を立て実装する。H-AC(2:12)

DI

順位表を見るとDが結構解かれている。
Iの考察がRice_tawara459に引き継がれ、Nzt3,Sotatsuの2人がDに移る。

Dは 区間についての演算 + 1点更新 のクエリなのでSegment Treeに乗らないか考える。
一度どこかに揃えると残りは2冪の簡単な式になる。一度どこかに揃えるコストを高速に計算したい。
どこかに揃えるってどこに？←これが全然わからない。1つ下のブロックと同じロッドじゃない？
Sotatsuが実装するが、サンプルが合わない。
これ上のブロックを先に揃えれば2冪になるんじゃ？ Nzt3が実装するがサンプルが合わない。
サンプル1をうまく説明する方法が生えない。

Rice_tawara459がIの方針を生やし実装するが、無限の場合分けになり炎上している。

コンテスト終了

順位表凍結後に一切の提出をしていないので YesNoで順位が下がるしかない。嫌だ。

^{絶望し全方位攻撃をする私}

昼食

荷物がコーチルームに移送されていたので回収に行くと、ほぼ最後の回収だったらしいです。

荷物を持って適当にサンドイッチや小人用エクレアを食べます。
スポンサーのいちご屋さん(いちご屋さんではなく、セキュリティ関係の会社らしい？)でイチゴをもらい、謎の抽選会に応募します。

スポンサーは個人情報を収集しに来ているはずなのですが、Jane Streetの個人情報収集ブースが見つかりませんでした。直感に頼った未証明のGreedyの反例を示しておもしろパズルと豪華な夕食を提供してくれただけに見えるのですが、どうしてスポンサーを？

ICPC Resolver

順位表凍結が徐々に解凍されていくICPCで最も面白いイベント「ICPC Resolver^[1][2]」があります。
私のチームは凍結後に提出をしていないので結果が確定していますが、東工大の残り2チーム AMATSUKAZE と Bocchi The Tech は共に凍結前6完+凍結後2提出でWF進出権を巡ったバトルが見られそうです。
凍結時に9完で1位のScreenwalkersが凍結後1提出して10完の可能性があること、凍結時2位のJägermeisterが凍結前8完+凍結後3提出でこれを上回る可能性があるのもアツいポイントです。

Bocchi The Tech が2提出をどちらも通し完数差をつけて東工大内1位でWF進出を決める、Jägermeisterの10完が確定しScreenwalkersの最終提出の結果によって優勝チームが確定するなど非常に面白い展開がありました。

ところで、メダル圏のResolverという激アツポイントの直前にジャズバンドの演奏を挟んだのはどういう意図があったのですか？

表彰式

銅メダル4+4チーム、銀メダル4チーム、金メダル4チームが表彰されました。

来年の Asia Pacific Championship が台湾で行われるという告知がありました。

Day4 (03/02)

エクスカーションです。Universal Studios Singaporeを観光します。
スヌーピーはいませんが、ミニオンがいます。ミニオンの素晴らしいアトラクションが面白かったです。Cylon(CLionではない)というジェットコースターに乗りまくる集団がいて怖くなっていました。

日本に帰ります。

Day5 (03/03)

日本着 (06:00 JST)
めちゃくちゃ寒いです。この気候はなんですか？
昨日まで常夏の楽園にいたはずなのですが……

日本が寒いだけならまだ許せたのですが、「前日まで暖かかったのに急に冷えた」という人を馬鹿にしているとしか思えない気候でかなり不快になりました。

感想

コンテスト設備を除いて全てが良い大会でした。気候まで完璧。
キーボードだけどうにかなりませんでしたか。

結果について

東工大内3位は順当なのですが、全体33位は下振れた感じがして嫌です。問題選択が悪かったわけでもなく、重大なミスがあったわけでもなく、可能な問題を長時間使っても通せずにこの位置になっており、苦しいです。

競プロの時間を増やして個人の実力を上げて来シーズン新チームで頑張ります。