GCJに向けて本気で問題を解説してみる 第4回 (Get Many Persimmon Trees)

Tatsuya Yatagawa
Programming Contest

第4回の今回も少し飛びまして「Get Many Persimmon Trees」という問題を解説したいと思います。参考ページは以下の通り。

「ACM/ICPC国内予選突破の手引き」
「AOJの問題ページ」

さてこの問題では次のような条件が与えられています。

  • W×Hのフィールドに柿の木 (Persimmon Tree) が何本か生えている
  • そのフィールド内に大きさS×Tの領地がもらえることになった
  • 柿の木の数が最大になるような領地の取り方が知りたい

この問題も効率よくやろうとすると大変そうな気がしますが、計算量は高々$10^8$以下であり、十分に単純な探索で解くことができます。


#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;

int N, W, H;
int x, y;
int S, T;
char F[501][501];

int main() {
    while(cin >> N, N) {
        cin >> W >> H;
        memset(&F[0][0], 0, sizeof(char) * 501 * 501);

        rep(i,N) {
            cin >> x >> y;
            F[x][y] = 1;
        }
        cin >> S >> T;

        int mt = 0;
        repa(j,1,H-T+1) {
            repa(i,1,W-S+1) {
                int t = 0;
                rep(l,T) {
                    rep(k,S) {
                        if(F[i+k][j+l]) t++;
                    }
                }

                if(mt < t) {
                    mt = t;
                }
            }
        }

        cout << mt << endl;
    }
}