kmjp's blog

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

dwangoプログラミングコンテスト予選 2016 : D - 庭園

その他コンテスト

実装はバグらせて手間取ったけど、解法はすぐ浮かんだ。
http://dwango2016-prelims.contest.atcoder.jp/tasks/dwango2016qual_d

問題

H*Wの２次元グリッドの各セルに、整数が書かれている。
これらのセル群から、重複しない２つの矩形領域を選択し、内部のセル群の値の総和の最大値を求めよ。

解法

２つの長方形を選ぶと聞いて、これが思い浮かんだ。
TopCoder SRM 552 Div1 Medium FoxAndFlowerShopDivOne - kmjp's blog

愚直に２つ長方形を選ぶと、O(H^4*W^4)かかりとても間に合わない。
２つの長方形を選ぶ場合、その２つが占める領域は、最低でも左右に分かれるか上下の分かれるかのどちらかを取る。
そこで、たとえばH*Wの領域を左L列と右(W-L)列に分けることを考える。
そうすると左側右側それぞれ、内部で１つセルの値の総和を最大化出来る長方形を選べばいいので、計算量が落ちる。
とはいえ、１個長方形を選ぶだけでも愚直に行うとO(H^2*W^2)かかるし、Lの取り方も考慮するとO(H^2*W^3)かかりまだまだ足りない。

そこで、左L列内の総和最大の長方形が分かっているとき、そこから左(L+1)列の総和最大の長方形を求めることを考えよう。

左L列において、上端がT、下端がB、右端がR列であるような長方形のうち、総和が最大のものをDP[L][T][B]とする。
するとDP[L+1][T][B] = ((L+1)列目のT～B行目の総和) + max(0, DP[L][T][B])となる。
また、左L列における総和最大の長方形の面積の最大値をM[L]とすると、M[L+1]=max(M[L], DP[L+1][T][B])となる。

この計算法だと、((L+1)列目のT～B行目の総和)を前処理でO(1)で求められるようにしておくと全体がO(H^2*W)で収まる。
右(W-L)列における総和最大値の長方形も同様に求め、各Lにおける左右領域それぞれの総和の最大値を求めればよい。

上下の場合も同様に行う。
以下のコードでは90度長方形を回転させ、左右に分ける処理を再利用した。

int H,W;
ll B[500][500],B2[500][500];
ll S[500][500];

ll L[400],R[400];
ll from[400][400],to[400][400];
ll ma;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>B[y][x],B2[y][x]=B[y][x];
	ma=-1LL<<60;
	
	FOR(i,2) {
		FOR(x,W) FOR(y,H) S[x][y+1]=S[x][y]+B[y][x];
		
		memset(L,0xcf,sizeof(L));
		memset(R,0xcf,sizeof(R));
		
		ZERO(from);
		FOR(x,W-1) {
			int y1,y2;
			FOR(y2,H) FOR(y1,y2+1) {
				to[y1][y2]=max(0LL,from[y1][y2])+S[x][y2+1]-S[x][y1];
				L[x]=max(L[x],to[y1][y2]);
			}
			if(x) L[x]=max(L[x],L[x-1]);
			swap(from,to);
		}
		ZERO(from);
		for(x=W-1;x>=1;x--) {
			int y1,y2;
			FOR(y2,H) FOR(y1,y2+1) {
				to[y1][y2]=max(0LL,from[y1][y2])+S[x][y2+1]-S[x][y1];
				R[x]=max(R[x],to[y1][y2]);
			}
			if(x<W-1) R[x]=max(R[x],R[x+1]);
			ma=max(ma,L[x-1]+R[x]);
			swap(from,to);
		}
		
		FOR(y,300) FOR(x,300) B[y][x]=B2[x][y];
		swap(H,W);
	}
	cout<<ma<<endl;
}

まとめ

SRMの問題覚えてなかったら解けなかったかも。