SRM 552 500pt : FoxAndFlowerShopDivOne

TopCoder

問題概要

W*H(<30)のテーブルがあり、各マスは白か黒か空。交わらない非空の矩形を二つ選んで矩形内の白と黒の個数の和を最大化したい。ただし白と黒の差がD(<900)を越えてはならない。

考えたこと

  • 30か。さすがに半分全列挙はないし5~6乗でもいいよ、ということなんだろう。
  • 最も愚直に(累積和使う程度はやるけど)やるとn^8か。係数小さいとは言えこれは無理。
  • 二つの矩形を選ぶのはもう少し分離したいしできそうだなあ。
  • どこかに境界ができるから、その境界を決め打ちすると？
  • 独立に計算できたら一方の領域では白と黒の差に対して最大いくつとれるか持っておけばよい。
  • もう一方の領域ではRMQ使って許容区間内の最大値取ってくればよい。
  • これはかなり楽(安全)に書ける気がする。
  • 一発コンパイルで全部通った。気分がよい。
  • 最大ケースと定数や配列のサイズを何度も確認して安心を得た。

反省

  • RMQとか持ち出すまでもなく、テーブルをふたつ作って愚直にマージすればよかった。愚直にマージするのはO(n^4)程度の操作だけど、それもO(n)回しか呼ばれないのだからそっちでやれば十分だった。
  • とはいえRMQでも別にそんな書きづらいわけじゃなかったので好みの差でしかない気もする。
  • ちなみに、幅固定なのでRMQの代わりにスライド最小値でもよい。

acceptされたコード

#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 30;
const int MAX_DIFF = 900;
const int INF = (int)(1.05e9);
const int SHIFT = 3*MAX_DIFF;

int accum[2][MAX_N+1][MAX_N+1];

struct FoxAndFlowerShopDivOne {

	int theMaxFlowers(vector <string> flowers, int maxDiff) {
		int ans = -1;
		for (int _ = 0; _ < 2; ++_) {
			const int H = flowers.size(), W = flowers[0].length();
			memset(accum, 0, sizeof(accum));
			for (int k = 0; k < 2; ++k) {
				for (int i = 0; i < H; ++i) {
					for (int j = 0; j < W; ++j) {
						accum[k][i+1][j+1] = accum[k][i+1][j] + accum[k][i][j+1] - accum[k][i][j] + ((flowers[i][j] == (k==0 ? 'P' : 'L')) ? 1 : 0);
					}
				}
			}


			for (int mid = 1; mid < W; ++mid) {
				rmq.clear();
				rmq.assign(6*MAX_DIFF, -INF);
				for (int sy = 0; sy < H; ++sy) {
					for (int sx = 0; sx < mid; ++sx) {
						for (int gy = sy + 1; gy <= H; ++gy) {
							for (int gx = sx + 1; gx <= mid; ++gx) {
								const int P = accum[0][gy][gx] - accum[0][sy][gx] - accum[0][gy][sx] + accum[0][sy][sx];
								const int L = accum[1][gy][gx] - accum[1][sy][gx] - accum[1][gy][sx] + accum[1][sy][sx];
								updateMax(rmq[P - L + SHIFT], P + L);
							}
						}
					}
				}
				rmq.build();
				for (int sy = 0; sy < H; ++sy) {
					for (int sx = mid; sx < W; ++sx) {
						for (int gy = sy + 1; gy <= H; ++gy) {
							for (int gx = sx + 1; gx <= W; ++gx) {
								const int P = accum[0][gy][gx] - accum[0][sy][gx] - accum[0][gy][sx] + accum[0][sy][sx];
								const int L = accum[1][gy][gx] - accum[1][sy][gx] - accum[1][gy][sx] + accum[1][sy][sx];
								updateMax(ans, P + L + rmq.getValue((L - P) - maxDiff + SHIFT, (L - P) + maxDiff + SHIFT + 1));
							}
						}
					}
				}
			}

			{
				vector<string> tmp(W, string(H, '.'));
				for (int i = 0; i < H; ++i) {
					for (int j = 0; j < W; ++j) {
						tmp[j][i] = flowers[i][j];
					}
				}
				flowers = tmp;
			}
		}
		return ans;
	}

};