JOI 春合宿 2023 参加記

JOI 2022/2023 春季トレーニング (IOI 2023 日本代表選抜) に参加した。

問題に関するネタバレを含むのでご注意ください

Day 0

本選の表彰式と交流会、プラクティスがあった。交流会では色んな人が話しかけてくれて嬉しかった。

ホテルに着いてからは Library Checker の問題を解いてソラ実装の練習をした。

Day 1

競技一日目。実は過去の春合宿の Day 1 はことごとく失敗しているので、今年こそはと思って競技に臨む。

currencies は読んですぐに解けた。部分問題が当日の ABC に出していた原案そのものだったので驚いた。festival2 は難易度高の数え上げ、passport は解けそうで解けない最適化だった。passoport の自明部分点を回収し、festival2 を取れるところまで伸ばした。6 乗くらいの DP をなんとか 3 乗まで落とした。

結果 100+51+54 = 205 で 2 位となり、悪くない順位。初めて良いスタートを切ることができた。

festival2 は前から見るより後ろから見た方が解きやすいらしい。どうせ対称だろ (実際は違う) と思って捨ててしまったのが良くなかった。満点がオンライン畳み込みなのはやりすぎでしょう

passport の解説を聞いてこれは解けるようにならねばと思った。1,2,...N に行ける⇔1,N に行けるの言い換え、思いつけないなあ

Day 2

競技二日目。

まず解けそうな見た目をした council に手をつける。なかなか上手にゼータ変換に落とし込めず、かなり手こずってしまったが、なんとか満点を取った。mizuyokan2 は明らかに難しい見た目をしているので飛ばす。初 Communication 課題の conveyor を見ると、なんと最後の小課題が 75 点。25 か 100 かという問題なので、これは解かなければヤバいと思って考える。かなり時間がかかったが 3 時間かけて満点を取ることができた。残りの時間で mizuyokan2 の自明部分点を回収した。

結果 100+100+28 = 228 となり、Day2 単独では 1 位タイ 。予想通り conveyor でかなり差がついていた。5 位とそれなりに差はあったものの、過去に自分は 100 点差をひっくり返して代表になったことがあるので全く安心できない。

解説: mizuyokan の谷ではなく山に注目するパートが人間的ではないと思った。これが区間スケジューリングになるのは凄い

Day 3

競技三日目。

cookies が簡単な問題設定なので手をつけるが、10 分くらい考えてこれはヤバい問題かもしれないと思って離れ、chorus に手をつけた。言い換えにかなり苦労したが、コスト関数が簡潔に表せる最短経路問題になり、どうせ Monge DP だろと踏んで WQS Binary Search を実装。O(N2 log N) が通って 61 点になったことを確認すると、遷移の高速化を考える。この時点でほぼ満点を確信していた。時間はかかったものの CHT + スライド最小値で O(N) で計算できるとわかったので実装し、満点を取った。次に tourism を見ると一瞬で Mo が降ってくる。O(Nsqrt(Q)logN) くらいなので明らかにヤバいが、TLが4秒なのでワンチャンに賭けて実装する。当然満点は得られない。その後、Mo をジグザグにしたり分割のサイズを変えたりすると TLE するケースが減っていった。思い切って std::set を BIT に置き換えたり連結リストで集合を管理したりすると、TLE がわずか 2,3 ケースになった。入出力高速化や std::vector を生配列に置き換えてなんとか 3.9 秒くらいで AC。残り一時間程度だったので cookies は部分点を回収して終わった。

Day3 単独では 1 位だった。正直 tourism が通ったのは完全に運だと思う。

解説: tourism の解法が賢かった。一度 Mo を思いついたら離れられない…

Day 4

最後の競技。5 位とかなり差があったので「〇〇点とれば代表確定」などと考えていたが、これが立ち回りの足枷になってしまうんじゃないかと色々悩んだ。

travel が自明だったので 30 分もかからず 100 点を取る。その後 40 分程度 battle を考えると 54 点を取ることができた。なんと開始 70 分で代表が確定してしまった!

とはいえ、どうせなら総合一位を取りたいのでさらに点数を伸ばすため guard を考える。問題を理解する時点でかなり難しく手こずる。思い切って大胆予想を実装することを何回か繰り返してパスグラフの場合を解いた。木はパスの延長で解けたので一般グラフの Q=0 の場合を考える。「どうせ使う辺は木、なんならMSTとかじゃないと解けないだろ」と考えてコスト関数を min(S[i], S[j]) と max(S[i], S[j]) と S[i]+S[j] の三通り実装して提出してみると、S[i]+S[j] が通って 50 点。ラッキー。その後 bitDP を実装して 8 点追加。

残り 1 時間は battle と guard の嘘解法に使ってしまい、合計 54+100+58 = 212 点。

なんとか逃げ切って総合 1 位!

解説: battle は思った通り E8 問だった。割り当て求めるのに焼きなましをするのがそれっぽい

結果

Σ870 1 位、IOI 2023 代表決定!!

感想

踏んできた場数が多いので、立ち回りにはかなり安定感があったと思う。特に、どの日についても最初に実装したのがその日で最も多く解かれた問題だったのが、難易度を見抜く力がついた証拠だと思う。

代表になれたのがとても嬉しい。最後の IOI も悔いのない結果を残せるよう頑張りたい。