TopCoder SRM 636 Div2 Hard ChocolateDividingHard

こういう制限の緩め方で来たか。
http://community.topcoder.com/stat?c=problem_statement&pm=13388

問題

基本的な設定はDiv1 Easyと同じ。
TopCoder SRM 636 Div1 Easy ChocolateDividingEasy - kmjp's blog
ただし、Div1 easyは縦横2本ずつ切込みを入れて3*3に分割したが、今回は縦横3本ずつ切込みを入れて4*4に分割せよ。

解法

今度は切込みを総当たりするとO(H^3*W^3)かかりTLEする。
生憎、SRM終了時「Div1Easyを二分探索で解いた」というtweetを見てしまい、こちらも二分探索で解けることに気づいてしまった。

答えとなる領域のおいしさの総和の値を二分探索し、各領域がそれ以上のサイズとなるような分割が可能か判定する。
領域のおいしさの総和をVとする。

まず、横の切込みは3か所総当たりする。
後は縦の切込みを入れていくわけだが、左端から順に切込みを入れられるかチェックし、横の切込みで分割される4つの段がいずれもV以上になるならその隣に縦の切込みを入れる。
このようにして3つ切込みを入れ、4段4列がいずれも総和がV以上になるなら、最小値をVとする分割が可能になる。

計算量は二分探索がO(log(NM))通り、1回の探索は横の切込みをO(N^3)通りで毎回左端から切込みを入れるかチェックするのにO(M)。
全部合わせてO(N^3*M*log(NM))なので元のO(H^3*W^3)よりだいぶ小さくなり、間に合う。

class ChocolateDividingHard {
	public:
	int S[80][80];
	int H,W;
	int sum(int x1,int y1,int x2,int y2) {
		return S[y2][x2]-S[y1][x2]-S[y2][x1]+S[y1][x1];
	}
	
	int okok(int val) {
		int y[3];
		for(y[0]=1;y[0]<=H;y[0]++)
			for(y[1]=y[0]+1;y[1]<=H;y[1]++)
				for(y[2]=y[1]+1;y[2]<=H;y[2]++) {
					int bx=0,num=0,x;
					FOR(x,W) {
						int ok=1;
						if(sum(bx,0,x+1,y[0])<val) ok=0;
						if(sum(bx,y[0],x+1,y[1])<val) ok=0;
						if(sum(bx,y[1],x+1,y[2])<val) ok=0;
						if(sum(bx,y[2],x+1,H)<val) ok=0;
						if(ok) num++, bx=x+1;
					}
					if(num>=4) return 1;
				}
		return 0;
	}
	
	int findBest(vector <string> C) {
		int x,y,mi=0;
		H=C.size(), W=C[0].size();
		ZERO(S);
		FOR(y,H) {
			FOR(x,W) S[y+1][x+1]=S[y+1][x]+C[y][x]-'0';
			FOR(x,W) S[y+1][x+1]+=S[y][x+1];
		}
		
		int ok=0;
		for(x=20;x>=0;x--) if(okok(ok+(1<<x))) ok+=1<<x;
		return ok;
	}
}

まとめ

Div1 easyは累積和以外特に工夫もなかったけど、こちらは結構面白かった。