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