POJ 2352: Stars

問題

星がN個あって、それぞれにはX,Yという二次元座標が整数で与えられている。それぞれの星にはランクがつけられており、星のランクはその星より左下にある星の数で決まる(同じX座標あるいはY座標を持つものも含む)。このとき、ランク0からランクN-1までの星の個数を答えよ。

制約条件

1 <= N <= 15000
0 <= X, Y <= 32000

解法

早とちり常習犯の僕は、問題を読んだ瞬間に「二次元BIT」でいけると思い、コードを書いてSubmitしてMLE食らいました。

二次元BITだと空間計算量O(N^2)になってしまうのでそりゃそうです。

で、冷静に考えてみると、自分より下にあるかどうかは処理順でコントロールして、X方向の合計だけを1次元BITで管理することを考えます。

もう少し具体的に言うと星をY座標が小さい順(同じY座標だったらX座標が小さい順)に処理していきます。

常にBITには自分より下にある星しかないので、X方向で自分以下の座標を持つ星の数を合計すればランクが求まるというわけです。

この問題の計算量はざっくりO(NlogN)なのですが、問題で与えられている座標が高々32000なので、そのままの座標を使えばいいです。

以下のコードでは無駄に次元圧縮をして、大きめの問題にも対応できるようにしてあります。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です