백준11750 Wall Clocks

작성일 | In

문제 링크

  • http://icpc.me/11750

문제 출처

  • 2015 Tsukuba Regional D번

사용 알고리즘

  • 그리디
  • 스위핑

시간복잡도

  • $O(N^2 \log N)$

풀이

각 사람의 시야는 구간으로 표현할 수 있습니다.

선형인 경우의 풀이를 먼저 생각해보면, 끝점 기준으로 정렬을 한 다음 스위핑을 하면서 최대한 뒤쪽에 시계를 배치하는 방식의 그리디로 풀 수 있습니다. 이 풀이는 $O(N \log N)$입니다.

이 문제는 선형이 아니고 원형입니다. N도 최대 1000으로 꽤 작습니다.
이쯤 되면 다들 예상했겠지만, 선형일 때의 풀이를 N번 반복해주면 문제를 풀 수 있습니다.

원형 구조인 것이 싫으니까, 시작점으로 잡을 구간 하나를 선택해서 선형으로 펴주면 됩니다.
총 N번의 시도에서 가장 시계를 적게 썼을 때의 개수를 출력해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, w, d, k;
unordered_map<char, p> st_dir, ed_dir;
vector<p> line;

bool bound(int i, int j){
    return 0 <= i && i <= w && 0 <= j && j <= d;
}

void init(){
    st_dir['N'] = {-1, 1}; ed_dir['N'] = {1, 1};
    st_dir['E'] = {1, 1}; ed_dir['E'] = {1, -1};
    st_dir['S'] = {1, -1}; ed_dir['S'] = {-1, -1};
    st_dir['W'] = {-1, -1}; ed_dir['W'] = {-1, 1};
}

int cross(int x, int y, int dx, int dy){
    int l = 0, r = 1010101;
    while(l < r){
        int m = l + r + 1 >> 1;
        if(bound(x+dx*m, y+dy*m)) l = m;
        else r = m - 1;
    }
    x = x + dx*l; y = y + dy*l;
    // cout << x << " " << y << "\n";
    if(!x) return y;
    if(y == d) return d + x;
    if(x == w) return k - w - y;
    return k - x;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> w >> d; k = (w + d) * 2;
    init();
    for(int i=0; i<n; i++){
        int x, y; char c; cin >> x >> y >> c;
        auto ss = st_dir[c], ee = ed_dir[c];
        int s = cross(x, y, ss.x, ss.y);
        int e = cross(x, y, ee.x, ee.y);
        // cout << s << " " << e << "\n";
        if(s < e) line.emplace_back(s, e), line.emplace_back(s+k, e+k);
        else line.emplace_back(s, e+k);
    }
    sort(all(line), [](const p &a, const p &b){
        return p(a.y, a.x) < p(b.y, b.x);
    });

    int mn = 1e9+7;
    for(auto i : line) if(i.x < k){
        int t = i.x, now = 1;
        for(auto j : line) if(i.x < j.x && j.y < i.x + k){
                if(t < j.x) now++, t = j.y;
            }
        mn = min(mn, now);
    }
    cout << mn;
}