TopCoder SRM 552 Div1 Medium FoxAndFlowerShopDivOne

問題

HxWマスのグリッドがあり、それぞれのマスは'L'または'P'または'.'である。
このグリッドに、二つの互いに交わらない長方形を書き、
その中に入っている(Lの数) + (Pの数)を最大化したい。

ただし、(Lの数) と (Pの数)の差の絶対値はmaxDiff以下でなくてはならない。
(Lの数) + (Pの数)の最大値はいくつか。

制約条件

H, W≦30
maxDiff≦900

方針

二つの交わらない軸に平行な長方形は、必ず軸に平行な直線で分離できる。
なので、分離する直線を30通りごとに、、
それぞれの上側と下側で、全ての(L, P)の候補を列挙し、
その中で条件を満たす最大のペアを見つければよい。

これは、diffごとにL + Pの最大値を覚えておくようなDPをすればよい。
が、それに気づかなかったので、下のコードでは気づかずにsegment treeとか使ってる。

あとは90度回転して、分離する直線が縦の場合も調べればよい。

ソースコード

const int N = 65536;
int dat[131072];
int query(int a, int b, int k, int l, int r){
	if(b <= l || a >= r) return -inf;
	if(a <= l && r <= b) return dat[k];
	return max(query(a, b, k * 2 + 1, l, (l + r) / 2),
		query(a, b, k * 2 + 2, (l + r) / 2, r));
}

int L[40][40], P[40][40];
vector<pi> u[40], l[40];

int calc(const vector<string> &f, int d){
	int h = f.size(), w = f[0].size();
	int ans = -1;
	
	rep(i, 40) u[i].clear(), l[i].clear();
	memset(L, 0, sizeof(L));
	memset(P, 0, sizeof(P));
	
	rep(i, h) rep(j, w){
		L[i + 1][j + 1] = L[i + 1][j] + L[i][j + 1] - L[i][j] + (f[i][j] == 'L');
		P[i + 1][j + 1] = P[i + 1][j] + P[i][j + 1] - P[i][j] + (f[i][j] == 'P');
	}
	rep(y, h) rep(x, w) for(int Y = y + 1; Y <= h; Y++) for(int X = x + 1; X <= w; X++){
		int cl = L[Y][X] - L[Y][x] - L[y][X] + L[y][x];
		int cp = P[Y][X] - P[Y][x] - P[y][X] + P[y][x];
		
		for(int i = 0; i <= y; i++) l[i].pb(mp(cl - cp, cl + cp));
		for(int i = Y; i <= h; i++) u[i].pb(mp(cl - cp, cl + cp));
	}
	
	rep(i, h + 1){
		sort(all(l[i]));
		sort(all(u[i]));
		l[i].erase(unique(all(l[i])), l[i].end());
		u[i].erase(unique(all(u[i])), u[i].end());
		
		rep(j, 2 * N - 1) dat[j] = -inf;
		rep(j, u[i].size()) dat[j + N - 1] = max(dat[j + N - 1], u[i][j].second);
		for(int j = N - 2; j >= 0; j--) dat[j] = max(dat[j * 2 + 1], dat[j * 2 + 2]);
		
		rep(j, l[i].size()){
			int lb = lower_bound(all(u[i]), mp(-d - l[i][j].first, -inf)) - u[i].begin();
			int ub = upper_bound(all(u[i]), mp(d - l[i][j].first, inf)) - u[i].begin();
			
			ans = max(ans, l[i][j].second + query(lb, ub, 0, 0, N));
		}
		
	}
	return ans;
}

class FoxAndFlowerShopDivOne {
	public:
	int theMaxFlowers(vector <string> flowers, int maxDiff) {
		int ans = -1;
		rep(it, 2){
			ans = max(ans, calc(flowers, maxDiff));
			vector<string> s(flowers[0].size(), string(flowers.size(), ' '));
			rep(i, flowers.size()) rep(j, flowers[0].size())
			s[j][i] = flowers[i][j];
			swap(s, flowers);
		}
		return ans;
	}
};