CEOI 2024 Day 1

04:44 でギリギリのフルスコア。結構おもしろセットだった。

A – Naval battle

2 番目に簡単かと思われる。

概要

$N$ 個の船が $xy$ 平面上にあり、それぞれの船の進行方向が 4 方位で与えられる。各船は $1$ 秒で $1$ 単位進む。同じ時間に同じ位置にある船は消滅する。
${10}^{100}$ 秒後に存在する船をすべて求めよ。

制約 : $N\le 2\times {10}^5$

解法

進行方向が北か東しかないサブタスクが存在するのでまずそれを考える。ある 2 つの船が衝突するのはそれらの $x+y$ の値が等しいことが必要。この値ごとにまとめてたとき、直近で衝突する船のペアを求める、船を消去するクエリを処理できればよい。これは std::set を駆使すればできる。(遅い場合は別の方法でなんとかする必要がありそう。QOJ って速いのかな？)

衝突する可能性のある方位のペアは $6$ 通りあり、それぞれについて同じことをすれば満点が取れる。

My Submission 意識はしたがうまくモジュール化しきれていない実装。

感想

ちゃんとモジュール化してうまく実装しないと辛い。結局コンテスト開始から 110 分かかって地獄を見た。

B – COVID tests

概要

インタラクティブ問題。

長さ $N$ の 01 数列 $A$ が隠されている。$A$ の各要素は確率 $p$ で 1 である。index の集合を送り、その中に 1 である index が含まれているかを質問できる。質問回数を小さくせよ。
$p=0.01$ だったりする。

解法

エントロピーを計算すると下限が見える。インタラクティブでわずかでもこういうのが出てくることはあまりないが、これはシンプルなので見えてうれしい。別にエントロピーと認識しながら解く必要はないが、そう表記して解法を書く。

とりあえず取れる解法として、最後に 1 だった場所を持ちながら左から次の 1 を探す二分探索を続けるというものがある。これは $Np{\log }_{2}N$ 回とか $2Np{\log }_{2}Np$ 回とかが実現できて、 30 点くらい取れる。

二分探索的なアイデアはそのままに、 mid を取る位置を最適化してみる。これをどうやるか、頑張れば数式である程度最適な位置を導き出せるかもしれないが、エントロピーを値に持った DP をすればあまりそういう事は考えずに最適化できる。

これで出してみたら、 $p$ が非常に小さいケースがだめだった。ないものを探そうとするのは無駄なので、探索の最初のステップで存在判定をすることにする。この判定をするしきい値も DP で求められる。これで出したら満点。

感想

DP で分割位置を最適化するみたいな解法のインタラクティブ、 JOI の昔のやつにもあったきがする。あれは満点にするための最後の 1 ステップだったが、これはダイレクトに解法そのもの。

C – Text editor

多分一番簡単。概要は面倒なので省略。

最初クエリ処理問題だと勘違いしていたこともあって、最適な経路の性質を考えていた。どういう経路があり得るかというのを特徴づけていくと、最短経路に落とし込める。それを解けば ok 。

感想

あり得る経路が案外複雑でバグらせてしまった。手でサンプルを作り実行し、これ間違っている！と思ったらプログラムのほうが賢い、というのが何度も起こって恥だった。

どういうサンプルがあれば落ちそうか？というのをあまり考えていなかったので、いちばん重要なパートを実行できていないままサンプルは通り 30 分経過、みたいなことをしていた。反省。