Banner(横断幕) - joi2011-day1 解説

筆者: qnighy

4頂点に3色全てを含むような矩形の数え上げである。

O(W^2H)解法

…

O(WH)解法

次のような部品の個数を数え上げることを考えてみよう。

つまり、互いに異なる色をもつL字型の部品である。

ここで、求めたい長方形は2種類(同じ色が対角線上にあるものと、同じ色が同一辺上にあるもの)に分けられるが、以下の図のように、どちらもこの部品の2個と対応する。

したがって、これらの部品の個数を求めて、2で割ればすぐに答えが得られる。

ところで、これらの部品は以下の計算の総和を求めるだけで求まる。

全ての(x,y)について、(x,y)の色を黒とすると、(縦にある白の個数)×(横にある灰色の個数)+(縦にある灰色の個数)×(横にある白の個数)の総和。

この計算は、それぞれの色の縦または横に並んだ個数をあらかじめ数えておくことで、O(WH)で終了する。

注意

符号付き32bit整数(int)で計算するとオーバーフローする。