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; } };