The 2024 ICPC Asia Pacific Championship 参加記（Shobon視点, コンテスト編）

2/29～3/3 にベトナム・ハノイに行き、The 2024 Asia Pacific Championship にチーム AMATSUKAZE で参加しました。

この記事を見ている人はこの記事も見ています

コーチ

AMATSUKAZE

Bocchi The Tech

メンバー

ebi_fly

M1。得意分野：木、構文解析、重実装

shobonvip

B3。得意分野：フロー、タイピング、誤読、ぬいぐるみなでなで

noya2

B2。得意分野：幾何、天才、パズル、数学

この大会は何？

Yokohama などの5つの Regional の上位層が集結し、世界大会(WF)進出を決める大会です。今年から導入されました。Regional の大会の 1 位は WF 確定なのですが、WF確定してないチームはこの大会で WF 出場権を争います。

東工大は Yokohama の 1 位を獲得できなかったのでWF争いに参加、そして yokohama で上位を取った3チーム(tonosama, AMATSUKAZE, Bocchi The Tech)がこの大会に参加しました。tonosama はガチプロが3人集結した印象、 Bocchi The Tech は数学の天才が3人集結した印象です。東工大3チームはコンテストでWFを争うものの、仲悪いことはなく、むしろベトナム中は頻繁に固まっていました。

Day -998244353

毎週 Universal Cup (UC) に参加してました。UC はほぼ毎週 ICPC のような形式でコンテストを行っているサイトです。自分は UC のおかげで実装力が結構ついた気がします。知識面をあまり鍛えていなかったことは後悔しています。

Day 1: Practice

Practice の前に写真撮影が入り、その後リハーサルが行われました。リハーサルは 12 問ありましたが、問題番号が mod 4 で合同な問題は同じであったため、実質 4 問でした。

「shobonは前から、noya2は後ろから」という感じでずっとやってきています。A, B を担当することになりました。Aは典型らしいですがパッと見では簡単な解法が思い浮かびませんでした。Bは少し考察したら解けました。ebiさんがCを通した後、Bを通しました。

Aは平衡二分探索木があれば達成できますが、平衡二分探索木を書けなかった（or 書きたくなかった）ため、妥協して平方分割を実装しました。これでも100行以上の重実装なので大変でした。しかし、TLEが出ました。

「PBDSがあれば行けるのではないか？」と思ったのでPBDSのドキュメントを探しますが、何も進展がなくて諦めます。そんなこんなで3完で Practice は終了。

「ランダムアクセス・任意箇所への要素の挿入・任意箇所の要素の削除」がやりたかったのですが、どうやら ext/rope を使えば簡単に書けたようです。PBDSの説明記事も確認しました。ちなみに practice の A 問題は平方分割で通したチームもあったようで、定数倍で失敗していたようです。

Day 2: 本番

コンテスト前

7時くらいに起床、8時にバスに乗りました。9時前くらいに入場しましたが、入場したときにはすでに30分こどふぉっていました。（注：「こどふぉ」とは、開始時刻が遅れることを言う。）

その後、トイレから戻ってくる途中、なぜかカウントダウンが1秒あたり1分で進み始め、9時20分コンテスト開始になっていました。逆こどふぉ。

コンテストは14問あるようだったので、作戦として「shobonは最初の7問、noya2は最後の7問を1問あたり10秒程度でジャンル分けし、問題文を読む担当を決める」ということにしました。

H, J

このとき、shobonは緊張で動揺しています。いつものように本番に弱いです。コンテスト開始後、A～G にさっと目を通します。どれもパッと見では難易度が分からず、しかし C, D, G は簡単そうだと思いました。

担当決めは：「A:noya2, B:noya2, C:ebi, D:noya2, E:shobon, F:ebi, G:shobon」としました。G は簡単に見えるので問題文を見ました。

noyaさんから後半の担当決めが送られます。どうやら14問ではなく、13問だったらしいです。担当は：「H:ebi, I:noya2, J:shobon, K:ebi, L:shobon, M:noya2」。自分の見る問題は E, G, J, L となりました。

G の考察を進めると、鳩ノ巣原理を用いれば適当に1つ見つけられることが判明しました。辞書順最小の制約を読んだにもかかわらず、鳩ノ巣原理を思いついたときにその記憶がなくなっており、Gの実装を始めてしまいました。しかし、4行書いたところで思い出しebiさんのHに交代します。

Gはやはり難しそうということで、問題文が短いLを見ます。操作は線形代数で表せますが、 $(i, j)$ のペアは非常に多いため、愚直は不可能です。そして、性質もよく分かりませんでした。簡単枠に見えて実は難問枠だった場合が危険なので、L問題は諦めて、ACが出つつあるJ問題を見ます。

J問題は難問枠に見えましたが、少し考察すると、「2つの経路のうち、1つが最短経路ではなかった場合、矛盾が起こる」ことが判明します。「最短経路を1個取り、その経路の通っていない各頂点について、その頂点を通る経路を見る」（嘘）というものを思いつき、ebiさんがH問題が通した後に実装を始めました。

前からと後ろからダイクストラを行います。実装が完成したかと思いきや、反例を思いつき、考え直します。少し考えると、「通っていない各頂点」ではなく「通っていない各辺」について見なければならないことが分かりました。実装はほぼ変わらないので「助かった」と思いながら実装し、J問題のACが出ました。

このセットは Regional よりもかなり難しめだと思いました。(0:54)

G, C

noyaさんがCを解く間、ebiさんに通されつつあったG問題を投げます。ebiさんに鳩ノ巣原理がだめだったこと言うと、文字列の行列を左からではなく「上から見る」と、同じく鳩ノ巣原理によって辞書順最小も特定できる、と言われて「確かに、なぜ自分は思いつかなかったのか」と思いました。「その解法でいいと思います」と言うと、ebiさんがC問題に取り組んでいたnoya2さんに「Gはすぐ書けます」と言い交代し、しばらくすると通りました。

その間、自分はE問題を見ています。E問題は自明な下界があり、必ずそれが達成可能だと思いますが、どのように操作するかが難しいです。「横・縦にまだ残っている」「横（or縦）だけに残っている」の場合分けをして、前者は最大流、後者は貪欲で解けたと思い、 FordFulkerson を書きました。しかし、最大流では解けていなかったです。

そのうち、noyaさんがC問題を通しました。(1:58)

E, F

裏ではF問題・K問題の考察も進行しています。「横・縦にまだ残っている」場合も結局貪欲でした。この問題はすべて貪欲で解けます。

E問題の貪欲を丁寧に書いていくと、かなりバグらせながらも実装が完成しました。サンプルと、自分が用意したラテン方格のパターンを試すと通りました。提出すると、REが出て絶望しました。assertをたくさん書いたので、どこかしらで落ちているようです。

印刷を頼み、F問題と交代します。しかし、印刷が全く来ません。かなりの行数のコードを書いたので、どこかしらでバグっていると思いました。一体何がだめだったのかコードを見て確認したいですが印刷が来ません。コンテスト全体で印刷が来ない不具合が発生しているようです。

Eで落ちた理由は、「そのマスの値をどのような違う値に変更しても条件を満たす」パターンを見逃していたことでした。PCはF問題の実装をしていますが、TLEになりそうで少し詰まったようなので自分とPCを交代します。1行目に「1 1 1」2行目に「2 2 2」3行目に「3 3 3」というようなケースで落ちることを確認し、コードの修正を開始します。実装後、1行目に「1 2 3」2行目に「1 2 3」3行目に「1 2 3」だと今度はこっちでも落ちました。まだバグっていたようです。

その間にバインミーが来ました。バインミーはベトナムで食べたかった物なので嬉しいですが、それはそれとしてバグっています。そのうち、そのバグの原因が分かりました。どうやらもう1つバグがあったようです。修正して提出するとACが出て「よし」と叫びました。

その後、バインミーを食べながらF問題の実装を見ていると、解法ではなくランダム入力がバグっていたらしく、提出するとF問題のACもすぐに出ました。東工大最強チーム tonosama とはペナ差で勝っており、コンテスト全体でも8位です。

tonosama はかなりのペナルティを持っていたので、同じ正解数ではこっちが有利です。上位の様子、さらに Bocchi the Tech が数学の難問を通してくる可能性が高いことから、ここからさらに2完くらいする必要があると感じました。(3:07)

K, 他

K の問題文を見ます。並列二分探索で解けるらしく、ebiさんに「 $i$ の部分木に属する頂点であって、値が $a$ 以下のものの個数は何個か？というクエリをオフラインで答えたい」と言われました。平衡二分探索木＋マージテク、はやりたくなく、「PBDS＋マージテクでいいのでは？」となりました。

K 問題の実装に移ります。通されている問題は、K,B,L問題です。ここから2問通すことが重要だと思いました。PBDSのtreeがうまく動かないのでドキュメントを確認。その後も order_of_key 関数が働きません。noyaさんが「binary trie＋マージテクでいけます」と言い、PBDSは諦めて binary trie をライブラリタイピング。

その間、B問題を見ます。B問題は辺の本数が高々 $2 n - 3$ 本（嘘）なので、見るべき集合の頂点数は少ないのではないか、という話になりました。しかし、後で $3 n - 6$ 本であることが分かります。こうなると、 $n \leq 6$ まで見る必要があると思っていました。しかしいい考察は出来ているのでしばらく粘ります。

通さなければならない K 問題がバグっていてピンチです。まずは K を通さなければならないと思い、自分も binary trie の確認などのデバッグに参加します。自分は K の解法を全て理解してなかったので余計な指摘をしており、やや逆効果だったと反省します。

K問題のサンプルが合ったので提出するとREが出ました。REが最もありえないと思っていたのでびっくりでした。自分はオーバーフローを疑い、確認します。答えの出力のときにオーバーフローするチャンスがあることを確認しましたが、REではなくWAが出るはずです。そうこうしているうちにコンテストが終わりそうなので自分は「#define int long long」を書いて提出するとCEが出ました。後で分かったことですが「int main()」の int が long long に書き換えられてコンパイルエラーを起こしていたようです…（普段これをしないので気づかなかった）

結局K問題を通せず、悔しい結果でコンテストが終わりました。その後、tonosamaのところに行くと、tonosamaが8完していることが判明しました。途中までtonosamaを上回っていたが、最終的にはKを通しても通していなくてもtonosamaには勝てていなかった、ということで悔しさがやや軽減されました。

競プロの強さとは、難問を難なく通す力であると――来年のICPCまでにはもっと精進すると決意しました。すぐの5月、tonosamaがWFに行くので応援します。

感想

コンテストの調子は、序盤はいつもどおり、中盤はかなり良く、終盤はあまり良くない、という感じでした。shobonの調子は平均以下、noyaさんの調子は平均以上だったと思います。自分は、結果的に正しい方向に行っているが細かい部分を間違えていたり少し焦っていた、という感じでした。全体的なチームの調子はいつものUCの平均以上でした。コンテスト全体では65チーム中18位、日本では12チーム中5位で、ペナが少ないのが救われました。

途中まで tonosama が破滅していて、WFがかなり目指せる、という感じだったので状況は面白かったです。ebiさんはICPC引退なので、来年は新しいチームで参加することになります。その時までにはもっと精進し強くなりたいです。

ベトナムの ICPC playoff は楽しかったです。ICPC playoff イベントにかかわった全ての人、ありがとうございます。