[Atcoder] ABC304 :: D - A Piece of Cake

D - A Piece of Cake

당시에는 풀지 못했지만 좀 간단하게 생각해보면 어렵지 않은 문제이다.

딸기의 위치가 2차원 격자로 주어지고, 이 2차원 격자를 A개의 row, B개의 column으로 자르려고 한다. 그러면 (A+1) * (B+1)개의 공간이 생기게 되는데, 여기서 발생한 공간 중 딸기가 존재하는 최소 영역과 최대 영역을 구하면 되는 문제이다.

좌표의 크기가 매우 크기 때문에 좌표 압축이 필요하다는 것을 알 수 있고, 이 좌표 압축 기법을 활용하면 별도의 알고리즘 없이 문제를 해결할 수 있다. 

각 딸기가 위치한 [x, y] 좌표를 압축하고, 이 [x, y] 좌표를 map에 넣어서 count를 하면 된다. 그리고 이 [x, y]는 A, B를 기준으로 상대적인 위치만 계산하면 되기 때문에 정답을 보장할 수 있게 된다.

 

#include<iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#define NUM 200010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

vector<ll> A, B;
ll C[NUM], R[NUM];
int w, h, n, a, b;
map<pll, ll> mp;

int main()
{
    memset(C, 0, sizeof(C));
    memset(R, 0, sizeof(R));
    
    cin >> w >> h;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> C[i] >> R[i];
    }
    
    
    cin >> a;
    for (int i=1; i<=a; i++) {
        ll x;
        cin >> x;
        A.push_back(x);
    }
    cin >> b;
    for (int i=1; i<=b; i++) {
        ll x;
        cin >> x;
        B.push_back(x);
    }
    A.push_back(w);
    B.push_back(h);
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
        
    for (int i=1; i<=n; i++) {
        ll x = lower_bound(A.begin(), A.end(), C[i]) - A.begin();
        ll y = lower_bound(B.begin(), B.end(), R[i]) - B.begin();
        mp[{x, y}]++;
    }
    
    ll m = n, M = 0;
    for (auto p : mp) {
        M = max(M, p.second);
    }
    
    if (mp.size() == (a+1) * (b+1)) {
        for (auto p : mp) m = min(m, p.second);
    } else m = 0;
    
    cout << m << " " << M << '\n';
}