TopCoder SRM 552 Div1 Medium FoxAndFlowerShopDivOne

この回は不参加。
http://community.topcoder.com/stat?c=problem_statement&pm=11387

問題

N*Mの2次元グリッドがある。
各セルは空白・L・Pのいずれかである。

このグリッドにおいて、交差しない2つの長方形を選択すると、内部のL,Pをすべて獲得できる。
この時、LとPの数の差はmaxDiff以内でなければならない。
この条件の元で獲得できるLとPの数の和を最大化せよ。

解法

2つの長方形の選択方法はO(N^4*M^4)。
N,M<=30なのでこの計算量ではTLEする。

2つの長方形が交差しないなら、2つの長方形はX座標またはY座標の少なくとも片方は交差しないはずである。
よって、まずグリッドを縦線または横線を1本引き、2つに分ける。
そして2つの領域それぞれにおいて、長方形を1個置いたときLとPの差ごとにL+Pの最大値を求めておく。

後は半分全列挙の容量で、2つの領域におけるLとPの差の和がmaxDiff如何になる範囲で、L+Pの最大値の和を最大化すればよい。

グリッドの分け方がO(N+M)で、2つの領域で長方形を1個置く処理にそれぞれO(N^2*M^2)かかるので全体でO((N+M)*N^2*M^2)であり、何とか間に合う。
なお、事前に累積和と取って長方形内のLとPの数はO(1)で計算できるようにしておく必要がある。

class FoxAndFlowerShopDivOne {
	public:
	char str[40][40];
	int fl[40][40][2];
	int* lp,*pp;
	
	int W,H;
	
	void rect(int x1,int y1,int x2,int y2,int* l,int* p) {
		*l = fl[y2][x2][0]-fl[y1][x2][0]-fl[y2][x1][0]+fl[y1][x1][0];
		*p = fl[y2][x2][1]-fl[y1][x2][1]-fl[y2][x1][1]+fl[y1][x1][1];
	}
	
	int theMaxFlowers(vector <string> flowers, int maxDiff) {
		H = flowers.size();
		W = strlen(flowers[0].c_str());
		int i;
		FOR(i,H) strcpy(str[i],flowers[i].c_str());
		
		int x,y,tx,ty,l,p;
		l=p=0;
		ZERO(fl);
		FOR(y,H+1) FOR(x,W+1) {
			FOR(ty,y) FOR(tx,x) {
				if(str[ty][tx]=='L'){ fl[y][x][0]++; l++;}
				if(str[ty][tx]=='P'){ fl[y][x][1]++; p++;}
			}
		}
		lp=new int[1024*1024];
		pp=new int[1024*1024];
		
		FOR(y,H) FOR(x,W) {
			for(ty=y+1;ty<H+1;ty++) {
				for(tx=x+1;tx<W+1;tx++) {
					rect(x,y,tx,ty,&l,&p);
					lp[(x+y*32)*1024+tx+ty*32]=l;
					pp[(x+y*32)*1024+tx+ty*32]=p;
				}
			}
		}
		int best=-1;
		
		//縦分割
		int sp;
		int li[2000][2];
		for(sp=1;sp<H;sp++) {
			FOR(i,2000) li[i][0]=li[i][1]=-1;
			//上
			FOR(y,sp) FOR(x,W) {
				for(ty=y+1;ty<sp+1;ty++) {
					for(tx=x+1;tx<W+1;tx++) {
						rect(x,y,tx,ty,&l,&p);
						if(li[1000+l-p][0] < l+p) li[1000+l-p][0]=l+p;
					}
				}
			}
			//
			for(y=sp;y<H;y++) FOR(x,W) {
				for(ty=y+1;ty<H+1;ty++) {
					for(tx=x+1;tx<W+1;tx++) {
						rect(x,y,tx,ty,&l,&p);
						if(li[1000+l-p][1] < l+p) li[1000+l-p][1]=l+p;
					}
				}
			}
			FOR(x,2000) if(li[x][0]>=0) FOR(y,2000) if(li[y][1]>=0 && abs(x+y-2000)<=maxDiff && li[x][0]+li[y][1]>best){
				best = li[x][0]+li[y][1];
			}
		}
		
		//横分割
		for(sp=1;sp<W;sp++) {
			FOR(i,2000) li[i][0]=li[i][1]=-1;
			//上
			FOR(y,H) FOR(x,sp) {
				for(ty=y+1;ty<H+1;ty++) {
					for(tx=x+1;tx<sp+1;tx++) {
						rect(x,y,tx,ty,&l,&p);
						if(li[1000+l-p][0] < l+p){
							li[1000+l-p][0]=l+p;
						}
					}
				}
			}
			//
			FOR(y,H) for(x=sp;x<W;x++) {
				for(ty=y+1;ty<H+1;ty++) {
					for(tx=x+1;tx<W+1;tx++) {
						rect(x,y,tx,ty,&l,&p);
						if(li[1000+l-p][1] < l+p){
							li[1000+l-p][1]=l+p;
						}
					}
				}
			}
			FOR(x,2000) if(li[x][0]>=0) FOR(y,2000) if(li[y][1]>=0 && abs(x+y-2000)<=maxDiff && li[x][0]+li[y][1]>best){
				best = li[x][0]+li[y][1];
			}
		}
		
		return best;
	}
}

まとめ

2つ長方形を置くのは難易度の上げ方としては安直だけど解き方のアプローチは面白いな。