Dragon(ドラゴン) - joi2011-day1 解説

筆者: qnighy

ドラゴンが上下左右に火炎を放射し、M理事長がそれを止めることができるとき、火炎が放射されていない範囲の最大値を求める問題である。

O(N+WH)解法

…

…

まず、M理事長がいない場合にどの範囲が利用できるかを数えておく。これは(W-ドラゴンのいる列)×(H-ドラゴンのいる行)で計算できる。

そこで、M理事長がある位置に配置されたときに、新たにどれくらいのマスが使えるようになるか考える。

まず、水平方向あるいは垂直方向のいずれかにのみ2.であるような状況を考えよう。

このとき、できるだけドラゴンに近いほうが、より多くのマスが使えるようになる。

(なお、使えるようになるマスは、M理事長が塞いだ先のマス目の個数から、その列に垂直に横切る炎の個数を引いた数になる。)

次に、水平方向と垂直方向の両方に2.であるような状況を考える。つまり、M理事長は炎の交わる点にいる。これは、右上、右下、左上、左下のそれぞれについて分けて考えるのが良い。

例えば、右下向きの炎を塞ぐことを考えよう。このとき、上から下に走査するとすると、そのx座標に交差する縦向きの炎はRMQや平衡二分木などで管理すればよい。とにかくこれは実装が重いだけである。

この方法でO(NlogN)で計算することができる。

x座標が縦、y座標が横である。