백준 7149번 Can of Worms

문제 요약

직선 상에 캔이 n개 놓여있다. 캔은 터질 수 있다. 각 캔이 놓여있는 위치 $x_i$와 캔이 터지는 반경 $r_i$가 주어진다.

캔이 터질 때, 터지는 반경 내에 있는 캔은 모두 연쇄적으로 터지게 된다. j번째 캔이 i번째 캔의 반경 내에 있으면 j번째 캔도 터지고 j번째 지뢰의 반경 내에 있는 캔은 모두 같이 터진다.

이 때, $i$번째 캔이 터졌을 때 같이 터지게 되는 캔의 수를 모두 출력하라.

$n \le 10^9$, $1 \le x_i, r_i \le 10^9$이다.

풀이

이 문제를 그래프로 생각해보자.

그러면, $i$번째 캔의 반경 내에 존재하는 모든 캔들에 대해서 간선을 연결해주자. 그렇게 만든 그래프에서 DFS를 돌리면 문제가 해결이 가능하다.

그러나, 간선 수가 $O(N^2)$만큼 나올 수 있기 때문에 그래프를 직접 만들면 시간초과를 받는다.

시간을 줄이기 위한 방법을 생각해보자. 일단, 모든 간선을 가질 필요가 없다.

$i$번째 캔에서 오른쪽으로만 갈 때 도달할 수 있는 캔들을 연결한 그래프, 왼쪽으로만 갈 때 도달할 수 있는 캔들을 연결한 그래프.

이 두 그래프를 합치면 위에서 말한 그래프와 같아진다. 하지만 아직 그대로 $O(N^2)$만큼 간선 수가 나올 수 있다.

그런데 위처럼 그래프를 만든다고 치면 도달 가능한 모든 캔에 연결할 필요가 없다. 도달 가능한 마지막 캔에만 간선을 이어주면 된다.

도달 가능한 마지막 캔이 $j$번째라고 하면, $i...j$사이의 캔들은 전부 도달 가능하기 때문이다.

이 방식으로 각 캔에 대해서 도달 가능한 마지막 캔을 찾는 것은 스택을 이용하면 $O(N)$에 가능하다. 그리고 각 그래프에서 간선은 최대 $N$개씩 생긴다.

이거로 시간 내에 그래프를 만들 수는 있는데 이 그래프에서 고려한 경로는 오른쪽으로만 가는 것, 왼쪽으로만 가는 것뿐이다.

왼쪽으로 갔다가 오른쪽으로 더 멀리 갈 수 있다거나 오른쪽으로 갔다가 왼쪽으로 더 멀리 갈 수 있는 그런 경로가 고려가 안 된 상태이다.

예를 들자면 반경 1짜리 캔이 5에 있고 반경 10짜리 캔이 6에 있고, 1, 2에 캔이 있다고 치자. 5짜리가 터지면 왼쪽으로만 고려하면 1, 2에 있는 것은 못가지만, 6짜리가 터지면서 1, 2에 있는 캔이 반경에 들어온다.

그럼 그냥 그래프를 만들 때 이런 경우도 고려하도록 만들면 안될까?

놀랍게도 이렇게 만들면 시간 내로 돈다.

그래프를 만드는 과정은 $O(N)$인데, 위처럼 오른 쪽으로 가는 경우, 왼쪽으로 가는 경우, 왼쪽으로 갔다가 오른쪽으로 가능 경우 등 다 고려해서 만든다 쳐도 이 시간은 딱히 변하지 않는다.

그러면 오른쪽으로 가능 경우, 왼쪽으로 가는 경우는 어차피 한 번만에 구할 수 있으니 다른 경우가 몇 번만큼 나올 수 있는지를 계산해보자.

오른쪽으로 가서 만난 캔을 통해서 원래는 못 갔던 왼쪽 캔에 갈 수 있게 된 경우를 생각해보자.

이 경우에 대해서 오른쪽에서 만난 캔과의 거리가 $x$였다면, 왼쪽에서 새롭게 만난 캔과의 거리는 $x$보다 크다는 뜻이 된다.

그러면 오른쪽 캔의 반경은 적어도 $2x$라는 뜻이고, 이를 통해서 원래 지뢰가 터졌을 때의 반경보다 두 배 이상이 된다.

새롭게 왼쪽에서 만나게 된 캔과의 거리를 $y$라고 하면 원래의 반경은 $2x$보다는 크거나 같지만 $2y$보단 작다.

오른쪽 캔의 반경이 $r$이라면 $r \ge x+y$다. 그러면 반경이 적어도 $r$만큼은 늘어난 것인데 이는 원래의 반경만큼은 늘어난다. 즉, 2배 이상 늘어나게 된다.

이를 통해서 늘어나는 횟수 많아봤자 전체 반경에 로그를 씌운 값이 된다. 따라서, 총 시간복잡도는 $O(Nlog10^9)$가 된다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
int N;
int largest[MAXN], smallest[MAXN];
int top;
int stk[MAXN];
int ans[MAXN];
struct Node {
    int x, r, idx;  
};

Node a[MAXN];

bool valid(int i, int j) {
    return abs(a[i].x-a[j].x) <= a[i].r;
}

bool update(int idx) {
    bool ret = false;
    while(top > 0 && valid(idx, stk[top-1])) {
        int t = stk[--top];
        if(largest[idx] < largest[t]) {
            largest[idx] = largest[t];
            ret = true;
        }
        if(smallest[idx] > smallest[t]) {
            smallest[idx] = smallest[t];
            ret = true;
        }
    }
    stk[top++] = idx;
    return ret;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    while(1) {
        cin >> N;
        if(!N) break;
        for(int i=0;i<N;++i) {
            cin >> a[i].x >> a[i].r;
            a[i].idx = i;
            largest[i] = smallest[i] = i;
        }
        sort(a, a+N, [] (Node a, Node b) { return a.x < b.x; });
        int cnt = 0;
        bool flag = true;
        top = 0;
        while(flag) {
            flag = false;
            ++cnt;
            assert(cnt <= 50);
            for(int i=0;i<N;++i) {
                flag |= update(i);
            }
            top = 0;
            for(int i=N-1;i>=0;--i) {
                flag |= update(i);
            }
            top = 0;
        }
        for(int i=0;i<N;++i) {
            ans[a[i].idx] = largest[i] - smallest[i] + 1;
        }
        for(int i=0;i<N;++i) cout << ans[i] << " \n"[i==N-1];
    }
    return 0;
}