POJ 1810 - Covering

http://poj.org/problem?id=1810

概要

\([0, N] \times [0, N]\) の平面上に、地雷が埋まっている可能性のある点が \(K\) 個ある。 \(M \times M\) の正方形の領域について地雷を調査できる人工衛星があるので、これを使ってなるべく多くの点をカバーできるような領域を選択したい。 ただし \(M \times M\) の領域の頂点は格子点でなければならない。つまり左下の座標を \((A, B)\) として \([A, M+A] \times [B, M+B]\) の領域をカバーすることができる \((0 \le A, 0 \le B, M+A \le N, M+B \le N)\)。 最も多くの点をカバーできるように領域を設定したときの \(A, B\) を答える。

制約

解法

領域を格子点の上に置く制約と最後の制約により、あるマスに存在する点はすべて同一視してよい。 すると \(N \times N\) グリッド上の各マスにいくつかの点があって、なるべく多くの点をカバーできる \(M \times M\) の領域を探す問題になる。

これは2次元累積和を \(O(N ^ 2)\) で求めておけば、各マスについてそのマス左下に領域の左下を設定したときにカバーできる点の数を定数時間で求めることができるので、 全体で \(O(N ^ 2)\) で計算できる。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int T;
 8   scanf("%d", &T);
 9   while (T-- > 0) {
10     int K, N, M;
11     scanf("%d %d %d\n", &K, &N, &M);
12     static int a[1000][1000];
13     for (int i = 0; i < N; i++) {
14       fill_n(a[i], N, 0);
15     }
16     for (int i = 0; i < K; i++) {
17       double x, y;
18       scanf("%lf %lf", &x, &y);
19       ++a[int(y)][int(x)];
20     }
21 
22     static int sums[1001][1001];
23     for (int i = 0; i <= N; i++) {
24       fill_n(sums[i], N+1, 0);
25     }
26     for (int i = 0; i < N; i++) {
27       for (int j = 0; j < N; j++) {
28         sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + a[i][j];
29       }
30     }
31     int ansx = -1, ansy = -1, ans = 0;
32     for (int i = 0; i+M <= N; i++) {
33       for (int j = 0; j+M <= N; j++) {
34         const int n = sums[i+M][j+M] - sums[i][j+M] - sums[i+M][j] + sums[i][j];
35         if (n > ans) {
36           ans = n;
37           ansx = j;
38           ansy = i;
39         } else if (n == ans) {
40           if (ansy < i) {
41             ansx = j;
42             ansy = i;
43           } else if (ansy == i && ansx < j) {
44             ansx = j;
45           }
46         }
47       }
48     }
49     printf("%d %d\n", ansx, ansy);
50   }
51   return 0;
52 }
poj/1810.cc