NOI 2019 Finals - Lasers
概要
問題へのリンク
Author : Cyanmond
解法
まず、答えは$ R行それぞれに対してその行で絶対にブロックされるレーザーを考えたときのそれらの和集合となる。
これは各行について独立に考えることができるので、まず各行について独立にこれを求めることを考えてみる。
長さ$ W_1, W_2, \cdots , W_Xの壁があるとき、左から$ i番目のレーザーが必ず止められる条件について考える。
これは、$ \displaystyle \sum_{k=1}^{m} W_k < iであるような最大の$ mを考えたとき、$ \displaystyle \sum_{k=m+1}^{X} W_k < L - i + 1であることと同値である。
より直感的には、可能な限り壁を左側に詰めたときレーザー$ iより右側に残った壁を詰め切れるか？ということ。
これを二分探索を用いて実装すると$ Lの小さい部分点を取れるが、$ L \leq 10^9の制約があるので、各行について$ L回これを判定していては間に合わない。
壁の置き方は、明らかに左にいくつか詰めて右にいくつか詰めるのが最適である。なので、逆に壁の詰め方を全探索して、どの詰め方でも止まってしまうようなレーザーを求めることにする。これは座標圧縮と imos 法を用いると$ O(X \log X)で求めることができる。
もちろん必ず止まってしまうようなレーザーは最大で$ L個あるが、そのようなレーザーの集合は$ O(X)個の区間で表せる。これらの区間を$ O(X \log X)で求めている。
各行についてこれが求まれば、また先ほどと同じように imos 法を用いて区間の和集合を求めることができる。全体での計算量は$ \displaystyle \sum_{k=1}^{R} X_k = Sとして$ O(R + S \log S)となる。