Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

IOI 2005-day1 Garden

問題文 : 庭園

解法 :
O(n^3) で長方形列挙を行い, 上下左右から周長の最大値を記録してやれば良い.
長方形列挙は, y 軸の2 点はO(H^2) で決め打ち, x 軸については尺取り法でO(W) で求めれば良い.

計算量はO(WH^2) だが, 制限時間ギリギリなので結構大変.

コード :

#include <cstdio>
#include <algorithm>
#include <climits>

using namespace std;

struct rect {
	int x1, y1, x2, y2;
	rect(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

int field[256][256], rSum[256][256];

inline int getSum(int x1, int y1, int x2, int y2)
{
	int ret = 0;
	ret += rSum[y2][x2];
	if (y1) ret -= rSum[y1 - 1][x2];
	if (x1) ret -= rSum[y2][x1 - 1];
	if (x1 && y1) ret += rSum[y1 - 1][x1 - 1];
	
	return (ret);
}

inline int len(rect q)
{
	return (2 * (q.y2 - q.y1 + q.x2 - q.x1 + 2));
}

int main()
{
	int W, H, N, K;
	
	scanf("%d %d", &H, &W);
	scanf("%d %d", &N, &K);
	
	for (int i = 0; i < N; i++){
		int y, x;
		scanf("%d %d", &y, &x);
		field[--y][--x]++;
	}
	
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			rSum[i][j] += field[i][j];
			if (i) rSum[i][j] += rSum[i - 1][j];
			if (j) rSum[i][j] += rSum[i][j - 1];
			if (i && j) rSum[i][j] -= rSum[i - 1][j - 1];
		}
	}
	
	int left[256], right[256], top[256], bottom[256];
	fill(left, left + 256, INT_MAX / 2);
	fill(right, right + 256, INT_MAX / 2);
	fill(top, top + 256, INT_MAX / 2);
	fill(bottom, bottom + 256, INT_MAX / 2);
	
	for (int y1 = 0; y1 < H; y1++){
		for (int y2 = y1; y2 < H; y2++){
			int x1 = 0, x2 = 0;
			while (x1 != W){
				while (x2 != W && getSum(x1, y1, x2, y2) < K) x2++;
				if (getSum(x1, y1, x2, y2) == K){
					rect x(rect(x1, y1, x2, y2));
					left[x2] = min(left[x2], len(x));
					top[y2] = min(top[y2], len(x));
					right[x1] = min(right[x1], len(x));
					bottom[y1] = min(bottom[y1], len(x));
				}
				x1++;
			}
		}
	}
	
	int ans = INT_MAX;
	
	for (int i = 0; i < W; i++){
		left[i] = min(i ? left[i - 1] : INT_MAX / 2 : , left[i]);
	}
	for (int i = 0; i < H; i++){
		top[i] = min(i ? top[i - 1] : INT_MAX / 2, top[i]);
	}
	for (int i = W - 1; i >= 0; i--){
		right[i] = min(right[i + 1], right[i]);
		ans = min(ans, left[i] + right[i + 1]);
	}
	for (int i = H - 1; i >= 0; i--){
		bottom[i] = min(bottom[i + 1], bottom[i]);
		ans = min(ans, top[i] + bottom[i + 1]);
	}
	
	if (ans > 2000000) printf("NO\n"); 
	else printf("%d\n", ans);
	
	return (0);
}