はじめに

ICPC 2023/2024 国内予選はnoya2、shobon、ebi_flyの3人でAMATSUKAZEというチームで参加しました。

模擬国内の参加記はこちら

当日まで

毎週火曜と金曜日に国内予選と模擬国内のセットを走っていました。バチャのナンバリングが21なので、21回セットを走ったらしいです（頑張った）。

昔にさかのぼるにつれて、今では典型みたいな問題もありますが非常に学びがあるので走るのがおすすめです。実装交代とか印刷とかのチームの動きは、ソロでやるのとかなり違うのでチームで何回かバチャやるといいと思います。

ngng628さんが開いてくれた（？？）構文解析バチャというのを走って、構文解析自信オタクになりました。ngng628さんありがとうございます！

当日（コンテスト前）

12時くらいまで家でダラダラAtCoderの問題解いたりシャワー浴びたりしました。

サイゼに行きイタリアンハンバーグを食べて、会場である演習室に行きます。

リハに参加して「構文解析でないかな～」とか、「D 構文解析、E 幾何、F 天才フローゲーでないかな～」とかいろいろ言いながら時間をつぶしました。

当日（コンテスト中）

初動はebi_flyがいろいろ設定をする担当なのでこれをする。

templateタイピングが終わったのでshobonくんにPCを渡す。

Aが通る。(0:06)

印刷された問題文が届く。

Bをnoya2くんが通す。(0:17)

Cをshobonくんが解けたと主張したので、聞きまあ良さそうとなったので実装してもらう。

実装が終わりできたと主張するので、assertを書こうということを言うがshobonくんが頭壊れてて書けないと言うので出してもらう。noya2くんがそれを聞いて渋い顔をしていたが出しちゃってWAが返ってくる。

お通夜みたいな雰囲気が流れるが、僕がassertを書くと言ってPCを奪い書く。書き終わったので動かしてみるとサンプルでassertが落ちる（え？）。

まじでやっちゃったという気持ちになり、コードを印刷してnoya2くんがD解けたと主張するのでPCを譲る。

shobonくんと2人で嘘主張しては、撃墜をしまともな解法が生える。

Dがほどなくして通り、shobonくんにCを実装してもらう。(1:10)

assertで落ちまくるので苦い顔をしながら2人であーだこーだ言っているとバグが直り通る。(1:22)

順位表を見ると、東工大内3位だったのでちょっとほっとする。CとDが通るまでは、かなりお通夜でこの世の終わりのような雰囲気だったが、和やかになりいつものバチャと同じような感じになる。

Eが謎で、Fが幾何だったのでnoya2くんにFに行ってもらいshobonくんとebi_flyでEに行く。

僕が、

$$dp[i][j][k]:=i個目まで見て、(x,y)=(j,k)となるときの操作回数の最小$$

というdpで一応 $O(N^3)$ で解けるということを主張する。
shobonくんが「これはエスパーなんですが、$(x,y)$ のペアとして考えられる個数は少ない可能性があります」

といい、根拠はなかったがもうエスパーでもなんでも通したら正義ということで書いてもらう。

遷移がぐちゃぐちゃになり困っているとnoya2くんがF解けたと主張したので聞きに行く。こっちもエスパーだったが正当性もありそうで「良さそう」と言う。shobonくんが沼っていたので、noya2くんに実装してもらう。

その間に遷移を詰めて、遷移は

1. 何もしない
2. y を操作する
3. x を操作する
4. x, y を操作する

の 4 つのみ考えれば良さそうと言う。なんか頭が終わっていたのでうだうだ状態の個数を見積もっていたら東工大の他チームが5完していて焦りまくる。5完したらペナ差で突破できるなという気持ちになる。

noya2くんが頭破壊したらしく、印刷してPCを空ける。shobonくんにEを書いてもらい、自分は状態数の見積もりをする。よくわからなかったが、noya2くんがわかったと主張し、PCを貸せと言ったので貸す。いろいろ直して通る（偉すぎ）。（2:25）

shobonくんが書けたというので、サンプルをダウンロードして実行する。

めっちゃ遅くて絶望し、どうにか小手先テクでできないか考えていると、値を変更する回数は $2N$ 回で抑えられていることに気づく（実際は、 少なくとも $N$ 回の操作で達成できる）。各変更回数に対して $(x,y)$ を問題文の順序で最大のものを採用するのが最適だな～となり僕が書けると主張して、PCを奪い実装する。
今書いてある実装が

$$dp[i][j][k]:=i個目まで見て、(x,y)=(j,k)となるときの操作回数の最小$$

でvector<map<pair<int,int>,int>> dp(n+1)として、map -> mapでdp更新をしていた。各変更回数に対して最大の $(x,y)$ を求めた後にその $(x,y)$ のみ使ってdp更新をするようにする。これによって $O(N^2\log N)$ くらいになる。元のコードを何も変更することなくできたので一瞬で実装が終わる。

実行をすると、改善前よりは劇的に早いが結構もっさりした感じで出力がされる。実行中に $O(N^2)$ でできることがわかったが 5分くらい待つと実行が終わったので提出すると1ケース目が通る。また5分くらい待つと実行が終わりだすとACになる。(2:54)

ガッツポーズとともに思わず声が出る。

その後、もうできることもなくなったのでチームメイトと雑談をする。順位表を見ると10位で東工大内2位であることがわかり目標にしていた10位以内と東工大内2位以上が達成されていた。

当日（コンテスト後）

コンテスト後いろいろ競プロerと雑談をし、ナンカレーを食べました。

チームメイトとも、アジア頑張りましょうみたいな話をしました。

感想

ICPC運営の方々、監督の先生やコーチの方々ありがとうございます。

ラストyearでアジアに行ったことがなかったので国内予選に通れて嬉しいです。練習したことが報われてほっとしています。構文解析がでなかったのはちょっと寂しいです。

貢献度があまり高くなかったので、アジアでは活躍できるように頑張ります。

予選突破した方、横浜大会ではよろしくお願いします。