kmjp's blog

競技プログラミング参加記です

CODE THANKS FESTIVAL 2015 : H - 穴あきケーキ

無理に穴開けなくてもいいんじゃないですかね…。
http://code-thanks-festival-2015-open.contest.atcoder.jp/tasks/code_thanks_festival_2015_h

問題

H*Wの大きさのグリッドが与えられる。
各セルには1~9の数値が振られている。

このグリッドから3*3以上のサイズの長方形領域を抽出し、かつ抽出後周辺部以外の1マスをくり抜いた形状を作ったとき、残ったセルの数値の総和がKとなるようにしたい。
そのような形状の作り方の組み合わせを求めよ。

解法

まずは2次元の累積和を求め、矩形の範囲における数値の総和をO(1)で計算できるようにしておこう。
同様に、矩形の範囲に1~9がそれぞれ何個登場するかも、2次元の累積和を求めておく。

仮に矩形の位置を総当たりする場合を考える。
矩形の面積がK+p (1≦p≦9)の場合、矩形内部におけるpの数値を持つマスの数を数え上げればいいことになる。
面積の計算もpの数値のマスの数も、前処理によりO(1)で計算できるので、あとは矩形の位置の総当たりを頑張ればよい。

単純に総当たりすると上端下端左端右端を総当たりするのでO(R^2*C^2)かかり間に合わない。
上端y1、左端x1を総当たりすることにする。
下端y2を下げていくと、数値の和が最初にKを超える右端x2が単調増加することがわかる。
よって、y2の変化に対し尺取法の要領で対応するx2を求めていこう。
後は右端をx2~(x2+3)程度の範囲で探索して、数値の和がK+9以下のケースを求めればよい。
こうするとO(R*C*(R+C))になる。

上端・左端・下端を決めた後、右端を二分探索する手もある。この場合O(R^2*C*logC)になるがなんとか間に合うようだ。

int H,W,K;
string S[400];
int tot[11][400][400];
ll ret;

ll sum(int top,int left,int bot,int right,int n) {
	return tot[n][bot+1][right+1]-tot[n][top][right+1]-tot[n][bot+1][left]+tot[n][top][left];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) tot[S[y][x]-'0'][y+1][x+1]++, tot[10][y+1][x+1]+=S[y][x]-'0';
	}
	FOR(i,11) FOR(y,H) FOR(x,W) tot[i][y+1][x+1] += tot[i][y+1][x]+tot[i][y][x+1]-tot[i][y][x];
	
	int top,left,right,bottom;
	FOR(top,H-2) FOR(left,W-2) {
		int right=left+2;
		for(bottom=H-1;bottom>=top+2;bottom--) {
			while(right<W && sum(top,left,bottom,right,10)<=K) right++;
			for(r=right;r<W;r++) {
				ll ts=sum(top,left,bottom,r,10);
				if(ts>=K+10) break;
				ret += sum(top+1,left+1,bottom-1,r-1,ts-K);
			}
		}
		
	}
	
	cout<<ret<<endl;
}

まとめ

これはすんなり解けて良かった。
むしろ二分探索は思いつかなかった。