JOI Open Contest 2024

まず全問題を見る。見た瞬間にExamination2の解法を完全に理解したが、木に対する高度なデータ構造と構文解析が必要になり、絶望する。とはいえほかの問題はよくわからないので実装することにした。

構文解析もうまく計算量を落とすのが難しかった。結果的にNlogNになったが、線形時間の方法はあるのだろうか。実装するうちに、セグ木とHL分解でやればよさそうに感じたが、これだとlogが2つになる。TLが2秒で怖かったが、C++を信じて実装すると少しバグったが通った。ここでHL分解を空書きできたのは偉かったと思う。ここまでで2時間ほど。

Library3を見る。クエリで得れるのはFunctional Graphの連結成分の数っぽい。そう考えるとN<=100は自明で、すぐにとることができた。N<=500はわからずHeatに移る。

C=1がそこそこおいしそうなので考えると、区間DPが思いついた。実装もそんなに重くなく、割と簡単に通すことができた。その勢いで小課題1もゲット。

ここで私は選択を迫られる。HeatのCが大きい解法を考えるか、Library3のN<=500を考えるか。私はLibrary3の方を選んだ。

NlogN回程度のクエリを要求していて、いろいろ考えたらクイックソートの要領で分けていけばよさそうであった。ランダム要素がまぎれるが余裕はあるだろうということで実装する。そして提出しようとするが、このタイミングで「採点プログラムのサンプルは適応的 (adaptive) ではない。実際の採点プログラムが適応的であるかは答えられない。」というアナウンスが来て怖かった。提出すると、通らない。これが原因か調べようとするが、この問題のadaptiveってどうやるんだという気分になる。手元で調べてみると嫌な予感は的中。普通に結構な確率で5000回オーバーしていたのだ。このあとは乱数のseedを変えたり質を上げて祈ることに集中してしまうが、一向に満点は取れない。結局Library3が満点になるときは来ず、コンテストが終了した。

正直最悪な気分だったが、結果は100-45-21ということで最悪ではないと思う。しかし、あのときの選択でHeatに行っていれば結果は違ったかもしれないなと、後悔の残る回だった。

このあと、Library3の乱択を改善する方法を教えてもらった。分割していく過程で連結成分2つに対して同時に分割を質問する。すると、1/2の確率で両方確定して残りの1/2で再度質問するからクエリの期待値が1*1/2+2*1/2=3/4倍になるらしい。これは盲点だったが、もう少し真面目に考えればできそうな解法でもあった。乱数をいくら変えても通らなかったのだから、途中であきらめて改善する方法を考えるべきだった。