JOI 春季トレーニング 2023/2024 に参加しました。
出題された問題のネタバレを含みます。注意してください。
〜3 月中旬
JOI の過去問をちまちま埋めていた。思ったよりも時間が取れなくてかなり中途半端になった。もっと計画的にやるべきだと思う。
本番 3 日前になって諸々のライブラリの確認もした。今年は意識的に幅広くやった。
https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum がすぐ書けるくらいにはなった。
立ち回り（共通）
次の方針で競技に取り組んだ。
- 最初に各問題 30 分ずつ考える時間を取る、このときコーディングはしない
- デバッグ用の環境を整える時間を惜しまない、具体的には
DBG(a, b, c, d);のように書いたら int でも pair でも vector でもすぐ出力できて、コンパイルオプションですぐ消せるマクロを書く
1 つめは一長一短だと思う。2 つめはデバッグが楽になる効用が大きいので手間を惜しまずやるべきだと感じた。
1 日目
fish3 を考える。R が固定なら素直な貪欲でよくて、一般の場合も分割統治で適当にやれば全て処理できる。実際は分割統治なんていらなくて無駄に面倒な方針だったが、程なくして通った。
ski2 を考える。H を決めるとコストが見通しの良い形で書ける。H の上限が小さいとき、素直に DP にすると 4 乗で、遷移の形を工夫すればすぐ 3 乗になる。これで 86 点。H の上限が大きい場合を考えて、とりあえず 4 乗を投げると通ってしまった。（実際には 3 乗になっていそうな雰囲気はするが真面目な計算量解析ができなかった。）
spy3 でとりあえず自明部分点を取る。最短路木をとったあとそれなりに頑張れば 1800bit くらいにはなったが、実装が終わらず 8 点のまま。
合計 208 点で、2 位だった。
2 日目
tricolor が難易度 12 だと主張してくるので身構える。隣接 2 つの組で 0,1,2 が表現できるが、復元の際に 2 択が生じて困る。適当な 012 の列を乱択で作って二人で共有し、これを送ることにすると、確率は解析できないが少なくとも手元では良い感じの挙動を示す。送ると 40 点が返ってくるので、ここで切り上げて他の問題に行く。
boardgame は他 K-1 人のコストが大体プレイヤー 1 の停止回数に関する上凸な関数になるのは良くて、ここで少し止まった。よく考えると K 個の線分を全て直線として扱っても良いので、 になる。一旦ここで実装しようとするが、大量にバグを埋める。結局特殊な制約でたまたま通る部分点しかもらえなかった。
さすがにまずいので vegetable5 をやる。とはいっても部分点 67 点分はそこまで難しくなかったので考察はもう終わっていて、あとは実装するだけだった。こっちもかなりバグらせたが、一応通って事なきを得た。
2 日目の点数は 124 点で、ここで 1 位になった。どうやた vegetable5 の満点の時間制限が厳しいらしく、こっちに行っていた人が大変なことになったらしい。
3 日目
3 問とも一読した感じでは可能枠に見えてしまうので悩む。とりあえず collection を考える。すぐに 3 乗にはなって、そこからが進まない。紙の上でしばらく考察するが、ちょっと考察を進めるたびにすぐに嘘が紛れるので全然進まない。結局最初の小課題より後の点は取れなかった。
joitour を考える。いろいろな情報を載せて大きなモノイドを作って、気合いで更新を速くする問題にしか見えない。HLD と segtree もどきで頑張ればできそうではあるが突っ込むのはまずいと思い一旦次へ。
tower で大変なことになる。最初に区間を set で管理する例のテクの方針が見えてしまう。これがとんでもない外れ方針。制約が小さくても実装が簡単になるタイプではないので、最初から満点を見据えて実装するが、やることが多すぎて心が折れる。（一応解けるとは思っているが結局実装できなかったのでわからない。）ここに時間を大量に吸われたのがよくなかった。
最後 1.5 時間くらいは joitour につぎ込むことにした。書ける小課題を全て書きながら、モノイドの構造を考えた。ただ結局満点の実装は終わらなかった。
3 日目の点数は 68 点で、ここで 2 位に落ち下との点差も詰まった。tower を多くの人が通していて辛かった。JOI 春季トレーニングに参加するのはこれが 3 回目だが、3 日目で良い成績を取れた覚えがない。
4 日目
問題を読むと、escape2 はまあなんとかなりそうだが island と tabletennis が ad-hoc なパズルにしか見えず嫌な感じになる。特に island は 2 年前の Super Dango Maker と同じ匂いがして、周りが大量に通すのに自分は満点を取れないタイプの問題に見えた。
ひとまず escape2 からやる。ダブリングで自然に小課題 4 までは解ける。満点は M の値を sqrt で分けてやれば良さそうに見える。実装すると満点の一個手前の若干制約が小さいケースまでが通った。ここで満点に粘着しても 10 点しか増えないことを思い出し、きっぱりと escape2 から離れた。
island を考える。最初は直径を取ることを考えていたが、しばらくしてあまり見通しがよくないように感じ始める。タイブレークが頂点番号の大小で決まることを使うことを考え出した。頂点 1 に隣接する頂点の列挙は確かに簡単にできて、うまく使えば 4N 回の質問で木を特定できることに気づく。ただ 4N には部分点がついておらず、先に進むには 3N 回に改善する必要がある。しばらく考えたがわからなかったので、大量の枝刈りを入れて改善する方向に進んだ。手元でランダムケースを作って試すと多くても 2.9N 回くらいで特定できていそうだったので投げると、1 ケースだけ通らない。あれこれ頑張ってみたが結局通らなかった。厳しい。
tabletennis は少し考えたが全く解ける見た目をしていなかったので 9 点だけ取ってすぐに撤退した。完全に結果論だが island の時間をもう少しこっちに割くべきだったかもしれない。後で聞くと上界をエスパーして山登りをするとそれなりに点が入るらしい。そんな...
昼休みのときにどこかからうっすらと island が満点みたいな話が聞こえてきたので、上位 4 人に入れていないことを確信して落ち込んでいた。蓋を開けてみるとギリギリ 4 位で、5 位との点差は 9 点だった。本当に危なかった。
IOI までにもっと時間の使い方を考えます
