AOJ0310 枠 - 足跡-sokuseki-

この高速化テクは典型らしいです。

問題

$N \times N$ のグリッドがあり、各マスに数が書かれている。
このグリッドに太さ1マス分の長方形の枠をのせ、枠が覆っているマスの数の総和を最大化する。
ただし、枠は $1 \times 1$ や $2 \times 2$ や $1 \times 10$ のように、中央に穴が空いていない場合もある。（詳しくは問題文の図を見て）

制約

$1 \le N \le 300$
$-1000 \le p_{i,j} \le 1000$

想定TLE

累積和をしてから、枠の左上と右下を全探索（ $O(N^4)$ ）して、それぞれの枠についての総和をO(1)で求め、最大値を答える。
2次元累積和＋長方形領域の総和を求めるパートくらいバグらせずに素早く書けるようにしましょう。

ちなみにこの問題を見た当初は 300^4くらいいける！w と思って書いてTLEしました（バカかな？）

解法

累積和して区間の総和を $O(1)$ で求めるのは変わりません。

しかし、枠の4辺を全探索すると $O(N^4)$ で間に合いません。 $O(N^3)$ に落としたいので、とりあえず2辺を $O(N^2)$ で全探索して、残り2辺を $O(N)$ で決めることにします。
ここで、2辺を $O(N)$ でしようとしたときに、しゃくとりを思い浮かべると、対辺をペアにするという発想ができます。
上下と左右、どっちを全探索しても本質的には同じなので、ここでは上下を全探索することにします。

$i$ 行目を上の辺、 $j$ 行目を下の辺として、総和が最大になるように右辺（ $r$ ）と左辺（ $l$ ）を決めます。
f:id:wk1080id:20190413181021p:plain
まず $i$ 行目と $j$ 行目を採用することは決まっているので、 $i$ 行目と $j$ 行目のマスの総和を計算しておきます。ここでは、枠を決めたときのその総和からの差分を最大化していきます。

右辺と左辺を一度に考えるのは難しいので、先に右辺から考えます。
右辺を $r$ 列目にすると決めたとき、

$i$ 行目の $r$ 列目以降の部分
$j$ 行目の $r$ 列目以降の部分

は、枠には関係ない部分なので、不要になります。
逆に、

$r$ 列目の $i+1$ 行目から $j-1$ 行目の部分

は枠の一部なので必要になります。
f:id:wk1080id:20190413182753p:plain
よって
（ $r$ 列目の $i+1$ 行目から $j-1$ 行目の部分） - （ $i$ 行目の $r$ 列目以降の部分） - （ $j$ 行目の $r$ 列目以降の部分）
を計算してあげればよいです。
これを $0 \le r \le n-1$ のすべての $r$ について求めてあげます。

そして、左辺の $l$ についても同様で、

$i$ 行目の $l$ 列目より前の部分
$j$ 行目の $r$ 列目より前の部分

は、枠には関係ない部分なので、不要になります。
逆に、

$l$ 列目の $i+1$ 行目から $j-1$ 行目の部分

は枠の一部なので必要になります。
f:id:wk1080id:20190413183500p:plain
よって
（ $l$ 列目の $i+1$ 行目から $j-1$ 行目の部分） - （ $i$ 行目の $l$ 列目より前の部分） - （ $j$ 行目の $l$ 列目より前の部分）
を計算してあげればよいです。
これを $0 \le l \le n-1$ のすべての $l$ について求めてあげます。

これで前計算が終わったので、あとはこれらをうまく組み合わせて右辺と左辺を最適に選びます。
たとえば、 $l$ を決めると、最大となる $r$ は、 $l < r$ をみたすもののうち、さっき計算した差分が最大となる $r$ です。これは「右端が $r$ 列目以降であるときの最大値」などを前計算してあげると $O(1)$ で求められるので、右辺と左辺を計算するのは全体で $O(N)$ でできます。（実際は $l = r$ の場合などは別で計算した方が簡単になります）

AIZU ONLINE JUDGE: Code Review