NOI 2020 Finals - Arcade
概要
問題へのリンク
Author : Cyanmond
実装も楽なので若干 9 寄り。
解法
二分探索... っぽい見た目をしながら、実は全然必要ない。
小課題 1, 2, 3 については、結局キーを$ Sに依存する個数使う dp を立てればよい。それ以降を解説する。
まず、時間ごとに動ける量が決まっている問題なのでとりあえず 45 度回転してみる。すると、以下のような問題に帰着できる。
二次元平面上に$ M個の点がある。$ (\mathrm{-inf}, \mathrm{inf})から右移動と上移動を繰り返して$ (\mathrm{inf},\mathrm{inf})に移動し、経路上で通った点に印をつけることができる駒をたくさん用意できる。最小でいくつの駒があれば全ての点に印をつけられるだろうか？
$ 1 つずつ駒を追加していくことを考えると、各駒は以下の動作を繰り返すのが最適である。
今の位置より右にある点のうち、最も下にある点に向かう。ただし、そのような点が複数あれば最も左にあるものに向かう。
以上をそのような点がなくなるまで繰り返す。
何も考えずに愚直にやると$ O(M^3)時間かかるが、シミュレーションは全体で$ O(M \log M)で可能。45 度回転した後の x 座標で点をソートし、 y 座標を載せた Segment Tree を持てばよい。