APIO 2024 参加記 - Cyanmond - 競技プログラミング

なんと 2 年連続中国ホストでの開催。決め方がよくわからないが、候補がいなかったのだろうか。IOI China 開催の布石だったりする？

問題は (去年と同じく) 微妙だった。これは別に中国が悪いわけではないが。。

A : September

特に書くことがない。shiomusubi496 とかは即満点を書いて 10 分ほどで終わらせたと言っていたが、自分は春のトラウマで全問題読んで並列に考えていた。「こういう雰囲気」の中国原産問題は解けることが本当にないという経験もあった。ただどう見てもこれが解けそうなのでとりあえず部分点を書くと普通に通り、拡張した満点も通った。30 分くらい。(この問題に使ったのは 15 分くらい)

この問題だけ部分点が豊富なのも面白い。ここで差をつけるつもりだったのだろうか？

C : Show

この問題は、終わった後に ytqm3 から聞いた解法は面白かった。(面白いので詳細は書かないが cf blog の discussion にも載っています)

ただ制約がゆるすぎて、ジャッジが hack できなさそうな雑な乱択を書けばなんでも満点がもらえる。疑心暗鬼になりながら書いて満点。90 分くらい。(この問題に使ったのは 40 分くらい)

B : Train

得意分野 + 好きな問題だが満点を取れず残念。

10 点までは雑に考えるとわかるのですぐに書いた。30 点は実装が面倒だがあまり変わらない。

5 点の解法は頂点ごとに並列にコストが Monge の DP をする形となっており、コストは rectangle sum の形で表される。並列に Larsch を進めると $O(N \log ^{2} N)$ で解けることがわかった。この時点で残り 150 分ほどあった。 $N = 100000$ で Larsch + 2d segtree の TL 1 sec が間に合う気がせず、この解法を保留にしたまま改善を考えていた。

CHT + 平方分割で $O(N \sqrt N)$ や、コストにもう少し良い性質を見つけることを目標に色々考えていたが、特に進展はなかった。(前者は sqrt log 止まりだった)

残り 1 時間くらいになってそろそろまずいと思い、 30 点確保を始めた。これは結構実装に時間がかかった。

終わった後に shiomusubi496 と話していると、自分が wavelet matrix をすっかり忘れていたことがわかった。この問題は WM で十分で、これを忘れていなければ $O(N \log N)$ 解法だったので迷わず書けたし多分速度も大丈夫。悲しい。

cf blog を見ていると実はだいぶゆるい計算量でも通ったようで、勘弁してくれとなった。

その他

解析モードで自分の提出を見ることができない。終了間際に提出した人は自分の点数すらわからないと聞いた。アピールの連絡も、 3 日後くらいに突然きて 12 時間すこしで締め切りだった。QOJ は CMS よりも操作しやすかったが、これは残念だった。

総評

100-40-100 だった。まだ点数を知らない人も多いが、これより上は事実上 300 しかあり得なさそうで代表落ちはなさそう。

正直満点を取れたセットではあったと思う。210 点を取った時点で考えることに重点を置きすぎていたのかもしれない。また、春合宿での反省から戦略をしっかり立てていたが、正直 2 問が簡単すぎて実運転をできた感覚はなかった。

追記

Gold Medal 取れました。