Codeforces #219 Div1. B. Counting Rectangles is Fun

部分和計算をふんだんに活かす問題。
http://codeforces.com/contest/372/problem/B

問題

N行M列のグリッドの状態に対しQ個のクエリが与えられる。
グリッド中はいくつか使用不可マスがある。

Q個のクエリは、グリッド上のある長方形領域を示す。
各クエリに対し、長方形領域内で使用不可マスを使用しない長方形をいくつ作れるか答えよ。

解法

先に前処理で各長方形領域内で作成できる長方形数を列挙してしまい、クエリではそれを答えるだけにする。

この処理は以下の３手順で行う。とにかく和の計算をしまくる。

• 各マスを左上として、どのサイズの長方形が作成可能かどうかを求める。
• 各マスを左上とする長方形内で、何個の長方形が作成可能か求める。
• 長方形領域内で、何個の長方形が作成可能か求める。

各ステップO(N^2M^2)だね。あとクエリがO(Q)。

int H,W,Q;
string S[100];
int num[42][42][42][42];
ll snum[42][42][42][42];
ll snum2[42][42][42][42];
ll res[42][42][42][42];

void solve() {
	int f,i,j,k,l,x,y,xx1,yy1,xx2,yy2;
	
	cin>>H>>W>>Q;
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W) {
		int r=100;
		FOR(i,H-y) {
			FOR(j,min(W-x,r)) {
				if(S[y+i][x+j]=='1') break;
				num[y][x][i][j]=1;
			}
			r=min(r,j);
		}
		FOR(i,H-y) {
			FOR(j,W-x) {
				snum[y][x][i][j]=num[y][x][i][j];
				if(i>0 && j>0) {
					snum[y][x][i][j]+=snum[y][x][i-1][j]+snum[y][x][i][j-1]-snum[y][x][i-1][j-1];
				}
				else if(i>0) snum[y][x][i][j]+=snum[y][x][i-1][j];
				else if(j>0) snum[y][x][i][j]+=snum[y][x][i][j-1];
			}
		}
	}
	for(y=H-1;y>=0;y--) for(x=W-1;x>=0;x--) {
		FOR(i,y+1) FOR(j,x+1) {
			snum2[y][x][i][j]=snum[y-i][x-j][i][j];
			if(i>0 && j>0) {
				snum2[y][x][i][j]+=snum2[y][x][i-1][j]+snum2[y][x][i][j-1]-snum2[y][x][i-1][j-1];
			}
			else if(i>0) snum2[y][x][i][j]+=snum2[y][x][i-1][j];
			else if(j>0) snum2[y][x][i][j]+=snum2[y][x][i][j-1];
		}
	}
	
	FOR(i,Q) {
		cin>>yy1>>xx1>>yy2>>xx2;
		cout << snum2[yy2-1][xx2-1][yy2-yy1][xx2-xx1] << endl;
	}
}

まとめ

３つ目のステップ、事前に行っていれば良かったのだが、本番はクエリ毎に行っていたせいでO(NMQ)でTLEした…もったいない。