0. はじめに
JOI2024/2025の本選までの参加記です。
1. 1次予選
1回目に参加して通りました。
デバッグ禁止縛りをしたら見事に1ペナしました。
2. 2次予選
満点に固執した結果E問題0点でした。
これが本選じゃなくて良かった...
3. 本選
難易度9と10をそれなりに埋めたので、まあ普通にやれば通るだろうと思っていました。
しかし、前回は問題3以降で自明部分点しか取れなくて余裕で落ちたので、最後まで不安でした。
3-1. 問題1
累積maxを考えて行/列ごとに二分探索をします。
普通に実装してAC(9:06)
3-2. 問題2
jを全探索することを考えると、Bの累積和とA_iの差を見ればいい感じに解けます。
これも実装してAC(15:00)
3-3. 問題3(小課題6まで)
木構造でよくある「頂点iの親はP_i(P_i < i)」を考えると条件が分かり、各lごとにrの最小値を尺取り法で求められるので、全体でO((M+Q)log(M+Q))で答えが求まると分かります。あとはいい感じに実装...しようとしましたが、座標圧縮の定数倍が重く小課題6までしか取れません。しばらく粘りましたがどうしても小課題7が取れないので一旦スルーします。(2:05:42)
3-4. 問題4(小課題6まで）
とりあえず愚直bitDPで小課題4までを確保します。その実装中に、状態数2^AのDPで解けないか考えると、O(2^A A^2logN)で割といい感じに行けると分かります。実装し、小課題5まで取ります。その後、どうにか定数倍高速化を加えることで小課題6まで通します。(3:26:06)
3-5. 問題3(満点)
どうにか高速化できないか考えると、endlが動作を重くしていることに気づき、\nに変更すると満点が取れました。(3:39:59)
3-6. 問題5(小課題1まで)
時間がないので、とりあえず自明な小課題1を取ります。しかし、小課題2の実装は間に合わず、結局3点で終わってしまいます。(4:00:00)
3-7. 結果
100-100-100-82-3で、385点でした。見た限り自分より高い人が3人ほどしかいなかったので、通過を確信しました。そしてボーダーは306点だったので、正式に通過が確定しました。
4. 終わりに
多分全体5位ぐらいでした。この順位だとまだ日本代表にはなれないのでもっと精進します。