ICPC 2003国内予選B 「Get Many Persimmon Trees」

問題URL: https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1125?year=2003

問題の言い換え

横，縦個のマス目がある．ここに個の点を打つ．個目の点は座標である．点の座標は重複しない．この下で，横，縦の領域で囲める点の数の最大値を出力せよ．

解法

まずは点の情報を保存します．これは0で初期化されたの二次元配列に対して，の要素を+1することで得られます．例えば，サンプルの最初のデータセットでは

0 0 0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 1 0 1 0 0
0 1 0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 1 0 0 0

のような二次元配列を構築します．16なので，1も16個あります．

次に，答えの最大値をどう探索するかを考えます．とりあえず，横，縦の領域の点の数を求めることを考えると，2重ループでできることが分かります．

for(int i=0;i<T;i++){
 for(int j=0;j<S;j++){
   // 二次元配列[i][j]の 1 or 0 を見る
 }
}

ただし，横，縦の領域は様々に取れるので，これは全通り見てやる必要があります．よって今回は，領域の左上の座標を全探索することにします．4乗オーダーになりますが，が100以下であることを考慮すると，十分高速です．

for(int y=0;y<h-t+1;y++){ // 左上のy座標
  for(int x=0;x<w-s+1;x++){ // 左上のx座標
    for(int i=0;i<T;i++){
      for(int j=0;j<S;j++){
        // 二次元配列[y+i][x+j]の 1 or 0 を見る
      }
    }
  }
}

左上の座標によっては範囲がをはみ出すこともあり得ますが，そのような場合は考慮しなくて良いです．（はみ出したときの点の数は，はみ出さないように調整したときの点の数には勝てないため）

以上を考慮すると，全体としては次のように書けます.

#include <iostream>
#include <vector>

using namespace std;
int main(){
    int n;
    while(cin >> n){
        if(n == 0)break;
        int w, h;
        cin >> w >> h;
        vector<vector<int>> v(h, vector<int>(w, 0));
        # 点を打つ
        for(int i=0;i<n;i++){
            int x, y;
            cin >> x >> y;
            x--; y--;
            v[y][x]++;
        }
        int s, t;
        cin >> s >> t;
        int ans = 0;
        # 左上の座標を全探索
        for(int y=0;y<h-t+1;y++){
            for(int x=0;x<w-s+1;x++){
                # S,Tの領域の点の数を数える
                int count = 0;
                for(int i=0;i<t;i++){
                    for(int j=0;j<s;j++){
                        count += v[y+i][x+j];
                    }
                }
                # 最大値を更新
                ans = max(ans, count);
            }
        }
        cout << ans << endl;
    }
}