Starry Sky(星空) - joi2009-day4 解説

筆者: snuke

「StarrySkyTree」の由来となった問題。

前処理

各星の x, y 座標の値の範囲は 0 ~ 10^9 とかなり広いので、「座標の小さい順になめる」ということが難しい。

これを解決するためには、x, y 座標の値をあらかじめソートしておくと良いことが分かる。

このような手法を「座標圧縮」という。

Lの値に関しても同様な処理をしておくと良い。

写真の正方形の一辺の長さと右上の座標の組み合わせを固定し、各星が写真に写るかどうかを調べることを繰り返せば良い。

一辺の長さと座標には座標圧縮後の値を用いる。

「各星が写真に写るかどうかを調べる」の部分をO(1)で出来ればよい。

そのためには「ある正方形の中に星がいくつあるか」というクエリをO(1)で処理できる「２次元累積和」の手法を用いると良い。

満点解法にはあまり関係がないので詳しくは書かないが、「写真の正方形の一辺の長さ」を大きい順に走査すれば十分な光度の星が１つずつ増えていくことになるので、累積和テーブルの更新回数が N 回になる。

上の解法と同様の理由により「写真の正方形の一辺の長さ」を大きい順に走査する。

これで、「一辺 L_{i} の正方形に収まる星の数の最大値」をO(N log N)で求めれば良いことになった。

x 座標と y 座標を同時に走査するのは難しいので、片方を固定することを考える。

具体的には「x 座標が L_{i} の幅に収まる星のリストから y 座標が L_{i} の幅に収まる星の数の最大値を求める」となる。

「x 座標が L_{i} の幅に収まる星のリストの作り方」と「そのリストから y 座標が L_{i} の幅に収まる星の数の最大値を求める方法」の２点について説明しよう。

前者は、上図のように帯を移動させていき、境界付近の星についてリストへの追加・削除を行えば良い。
追加・削除は各星につき一回ずつなので、高々 N 回ずつしか行われないことが分かる。

後者は、「星のリスト」に適切なデータ構造を用いることで O(1) でできるようになる。

まずは下図のような、一番下のノードには「y_{j} から y_{j}+L_{i} までにある星の数」を、それ以上のノードには子ノードの最大値を記録する二分木を考える。

しかしこの木では、最大値の参照は出来るが星の追加・削除が効率良く行えない。

そこで、各ノードから親ノードの値を引いてみると下図のようになる。

これが「StarrySkyTree」である。

この木の仕組みについて説明しよう。

まず、全体の最大値は根ノードに格納されている。

それ以外のノードの元の木(差を取る前の木)での値は根から累積和を取ると復元できる。(この問題においては求める必要はない。)

次に、区間に１を加える(減らす)方法だが、基本的には普通の区間木と同じように(蟻本等参照)すれば良い。

ただしそのとき「子ノードのうち一方が 0 で、もう一方が 0 以下」という性質を保つように調整しつつ更新しなければならない。

例えば、ノード A の子ノードの値が (1, -1) になった場合は、
ノード A に 1 を足し、両方の子ノードから 1 を引けば (0, -2) となり上記の性質を満たす。

しかし、この解法を実装しただけでは１部ケースでTLEを起こしてしまい満点には届かないだろう。
満点を取るためには以下の枝刈りなどが必要になる。

写真の正方形の一辺の長さを小さくすることによって写真に写るようになった星を写真に収められるような範囲だけを走査すれば十分である。
なぜなら、増えた星を使わないような場合はすでに調べているはずであるからだ。

この枝刈りを行うと計算時間が大幅に減り、満点を期待できる。