ICPC 2023 Yokohama Regional の参加記です。
2023 年 11月 25, 26 日に開催された ICPC 2023 Yokohama Regional にチーム Algorithmical で ryu150 と makaserori と参加し、 7 / 11 完で 21 / 58 位でした。
一日目
この日はリハーサルがありました。
A を makaserori に、 B を ryu150 に解いてもらい、その間に C と D を解いていました。
makaserori と私が US 配列自体初めてで悲鳴をあげていました。
ところで D ですが、 $15!!$ がおよそ $2\times 10^6$ なので頂点のペアの列挙は $N=16$ 程度なら間に合うことを初めて知りました。この計算量の見積もりができておらずそこそこ悩んでしまっていました。リハーサルはいい感じに全完できました。
二日目
リハーサルの際に配られた Do not touch until we say so. と書かれた封筒にチーム紹介や日程の書かれた冊子を入れて管理していたのですが、コンテスト前の準備でそれを取り出して確認していたところ運営に問題文を勝手に開けていると勘違いされ大事になりかけました。
コンテスト
A を makaserori が、B を ryu150 が、 C 以降で解けそうな問題を探してそれを私が解いていくという作戦で臨みました。
以下はコンテスト中の時系列情報です：
- 開始 20 分ほどで D が区間 DP だと分かり、実装も紙にまとめられました。この時 A が詰まっていたので、印刷してもらい実装を譲ってもらいました。D を実装したところ復元部分がバグっていたので、 A のバグが分かったという makaserori に実装を譲りました。
- A が通りました (0:47)。通った時には D のバグが分かったので、すぐに実装を代わってもらいました。
- D を通しました (0:58)。この時 B を考えている ryu150 から SOS が出ていたので一緒に B を考えることにしました。
- B を通しました (1:27)。 $C$ の制約をどう活かすかが全く分からなかったので、式変形大好きマンとして式を変形してみたところ $O(N)$ 解が見えたのでそれを実装しました。
この時順位表をみたところ F が異様に解かれていたのでそちらの考察に回ります。 - F を通しました (1:47)。最初黒マスの個数を出力すると勘違いしていましたが、 ryu150 にサンプルが合わないことを指摘され我に帰りました。逆に連結成分の方が難しくないか？と悩んでいましたが、各連結成分が必ず長方形になることに気付いてからはすぐでした。
F を通した後に順位表を見てみると K がそこそこ解かれていたので K を解くことにします。 - K を通しました (2:52)。幾何なのでかなり避けたかったですが、気合を入れて図を睨むとギャグであることに気づきました。しかしクエリの上限が $1024$ のところ $1030$ 回程度クエリを飛ばしてしまう解法から中々考察が進まず、しかし乱択なら高確率で正解できる解法ではあったため「円の位置はテストケース毎に固定か？」という clar を投げてしまいました (当然 No Comment と帰ってきました…)。昼食を食べながら考えていたら直径が実はクエリ $1$ 回で突き止められることに気づき、それを実装することで AC しました。
このタイミングで残り解けそうな問題は E と G のみでした。問題の見た目は G の方が解きやすそうでしたが、順位表を見たところ E の方が多く解かれていたので先に E を考えることにします (これは結果的にあまり良くなかったです)。 - E を通しました (4:28)。 $b$ を固定するといい感じに計算量が落ちることに気付くのに $30$ 分ほどかかってしまい、またそれを実装しても計算量が $O(N^22^N)$ となってしまい TL8s に間に合わずに頭を抱えてしまいました。ボトルネックとなっているのは各 $b$ のループ内で bit 全探索をしている部分でしたが、ここで FF のツイートを思い出します。
bit全列挙、for文でやるよりdfsの方が速いときあるよね
— ゆうっうっうき🌙🌙🌙🏴☠️👾😈👑✝️🫐🗼🎠 (@yuuki_n_n) 2023年10月29日これを元に bit 全探索を dfs に書き換えたところ、 TL8s にギリギリ間に合うか間に合わないかのラインまで高速化することができました。 $N=24,M=1$ の場合の答えは常に一定なのでそこだけ埋め込んで提出したところ AC と帰ってきたのでびっくりしました。
- G を通しました (4:49)。すぐに解法は浮かび、なんだかんだこれが $O(N \log N)$ です！みたいなオチじゃないのかな〜などと言いながら諦め半分で実装を始めました。適当にメモ化再帰を書いて少しデバッグしたら答えが合い、最大ケースを試してみたところ 1 秒程度で動いたのでこれは通るのでは？と思いつつ提出したら本当に通ってウケていました。順位表に囚われずに最初に考えておくべきでした。
A 以外の全てを私が実装することになり、特に ryu150 はどの問題も解けていない状態でした。仕事分担をミスったことは反省ポイントです。
コンテスト後の Buffet Party では何人かと交流しました。豊田高専の人たちとまだしっかり話せていなかったので、高専プロコンの話や編入の話をしました。 stoq さんともトヨタコン振りにお会いしました。
スポンサー巡りをしていたところ、 Y.Y. さんに遭遇しました。遭難者ですと自己紹介したところ隣にいた hitonanode さんにも認知されていることが分かりびっくりしました。過去に私が作問した No.2362 Inversion Number of Mod of Linear - yukicoder の話になり嬉しかったです。是非解いてください。
今回が初の ICPC でしたが、かなり楽しい体験をすることができました。特に食料が大量に配られていたところが感動ポイントです。来年も同じメンバーか後輩を混ぜたチームで出たいです。
追記：どうやら 1 分差で playoff 行きを逃したらしいです。そんな……
