BOJ 9208 - 링월드

요즘 codeforces 에서 문제를 푸느라고 한동안 블로그 글을 쓰지 않았다... 다시 백준에서 문제를 조금 풀게 된 만큼 한 번씩 글을 써야겠다.

문제 링크 : https://www.acmicpc.net/problem/9208

문제 풀이 (의식의 흐름)

※ 제 풀이는 intended solution에서 좀 벗어난 풀이입니다. 관련 개념 및 의도 된 풀이를 보고 싶으시면 https://qwerasdfzxcl.tistory.com/11 를 참고해주세요. 

문제의 첫 방향성을 잡는 것이 힘들었다. 관찰의 실마리도 별로 보이지 않았으며, 무엇을 사용해야겠다는 감도 잡히지 않았다. 그렇기 때문에 일단 문제를 직선에서 풀기로 생각하였다. 원형 문제는 보통 길이를 두 배로 하여 직선으로 바꿀 수 있기 때문에, 그리고 그 편이 관찰을 하거나 생각, 구현을 하는데 편하기 때문에 직선에서 이 문제를 해결하려고 생각했다. 

가장 먼저 생각 된 부분은 구간 [a,b]에 포함 되어있는 범위에 완벽히 포함되는 도시 구간이 b-a+1 개 보다 크면 불가능 하다는 것이다. 그리고 그렇지 않으면 된다는 것이다.
추가적인 관찰로 이것이 불가능 하게 되는 순간은 어떠한 도시 구간 [xi,yi]가 추가되면서 [xi, yi] 구간에 대해서 위와 같은 상황이 벌어진다고 생각했다.
그렇기 때문에 좌표 압축을 하고 yi 기준으로 정렬하여 xi 에 1을 더하면서 구간에 속한 도시 구간의 갯수를 세그트리를 이용해서 확인하면 O(T N lg N) 에 해결할 수 있을 줄 알았다. 

예제 - (1,1), (1,2), (2,3), (3,3). 
내가 생각한 관찰에 의하면 [1,1] [1,2] [2,3] [3,3] 만 확인해도 된다. 하지만 이대로 확인하면 불가능한 구간이 없으며, [1,3] 구간을 확인해야 한다. 따라서 위에서 적은 추가적인 관찰은 틀렸다. 

 다시 "구간 [a,b]에 포함 되어있는 범위에 완벽히 포함되는 도시 구간이 b-a+1 개 보다 크면 불가능 하다는 것" 으로 돌아가자. 위의 관찰이 틀렸기 때문에 한 번 도시 구간을 추가할 때마다 yi 보다 작은 모든 k에 대해서 [k,yi] 를 다 확인해야 하고 이는 나이브하게 n^3의 시간복잡도를 가진다. 

 위에서 1~yi-1 의 모든 k를 본다고 했다. 하지만, 분명히 가장 불가능에 가깝게 만드는 k는 존재한다. 지금까지 체크한 [k, yi] 사이의 도시 구간 시작 점 개수가 yi-k+1 보다 많으면 불가능이다. 이를 식 변환 하면 [k, yi] 사이의 도시 구간 시작 점 개수 + k 가  yi+1 보다 많으면 불가능이다
따라서 불가능에 가장 가까운 구간의 시작점은 k+( [k,yi]에 있는 도시 구간 시작 점 개수) 가 가장 큰 k일 것이다. 이는 xi에 대해서 1~xi 에다가 1을 더하고 max 값을 뽑아내는 Segment Tree lazy propagation을 사용하면 해결할 수 있다. 
 하지만 Segment Tree lazy propagation을 사용하면 시간 초과가 나게 된다. 따라서 k+( [k,yi]에 있는 도시 구간 시작 점 개수) 가 가장 큰 k를 찾는 더 빠른 방법이 필요하다. 

 관찰을 해보자. 1~xi 에다가 1을 더하고 [1, yi-1] 에서 max 값을 뽑아내는 것을 반복해야 한다. 이때 1 ~ xi에 1을 더하는 것이기 때문에 a<b 인데 a의 값이 b의 값보다 크다면 b는 절대로 답이 될 수 없다. 즉 더 오른쪽에 있으며 값도 작으면 후보가 될 수 없다는 것이다. 
따라서 가능한 후보를 모노톤하게 관리하면 된다. 왼쪽이 작고 오른쪽으로 갈 수록 커지게. 이 중 반복적으로 왼쪽 일부분에 1이 더해지게 될 것이고, 이를 통해서 오른쪽보다 커지면 그 오른쪽 값을 빼면 된다. 이를 셋으로 관리할 수도 있지만, 이는 시간초과가 날 가능성이 있기 때문에 uf, disjoint set 을 응용해서 관리하였다. 
 lx[ i ] 에는 i 이하의 가장 큰 가능한 후보를 담고, rx[ i ]에는 i 이상의 가장 작은 후보를 담는다. 도시 구간이 들어올 때마다 lx[ xi ]에 1을 더해주고 xi 오른쪽에 있는 후보보다 값이 커지면 오른쪽의 후보를 합쳐주면 된다.  

풀이 정리

1. 원형을 길이 두 배의 직선으로 펼친다.
2. 구간 [a,b]에 포함 되어있는 범위에 완벽히 포함되는 도시 구간이 b-a+1 개 보다 크면 불가능 하다.
3. 도시 구간 [xi,yi] 를 yi 에 대해서 정렬한다.
4. 정렬된 도시 구간을 순차적으로 보는데, 지금까지 체크한 [k, yi] 사이의 도시 구간 시작 점 개수 + k 가  yi +1 보다 많으면 불가능이다. 
5. [k, yi] 사이의 도시 구간 시작 점 개수 + k 의 최댓값을 찾는 것으로 목표 설정. 
6. 도시 구간 시작점의 개수는 도시 구간이 추가됨에 따라서 1 ~ xi 에만 추가되기 때문에 왼쪽의 값이 오른쪽 보다 값이 크면 영원히 역전이 안된다. 따라서 모노톤 하게 값을 관리하면 된다. 
7. disjoint set을 이용하여 가능한 후보들만 남기고 바로 왼쪽 후보 오른쪽 후보에 접근이 가능하도록 한다. 
8. 왼쪽 후보가 오른쪽 후보보다 커질 때마다 union 해주고, 현재 가장 오른쪽 후보랑 yi 랑 비교하여 위의 조건을 만족하면 불가능 끝까지 만족하지 않으면 가능이다. 
9. 시간 복잡도는 O(T N lg N) 이지만, disjoint set 이기 때문에 2초 문제를 1484ms 로 통과할 수 있었다. (set이나 segment tree면 아마 불가능 할 것 같다. )

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll u,a,b;
};
 
vector<poi> v[1101010];
vector<ll> x;
ll arr[1010101];
ll bns[1010101];
ll lx[1010101];
ll rx[1010101];
ll ans=0;
ll n,m;
vector<pii> qr;
 
bool sf(pii a,pii b){
    if(a.ss!=b.ss) return a.ss<b.ss;
    return a.ff>b.ff;
}
 
ll fil(ll x){
    if(x==lx[x]) return x;
    return lx[x]=fil(lx[x]);
}
 
ll fir(ll x){
    if(x==rx[x]) return x;
    return rx[x]=fir(rx[x]);
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t,T;
    cin>>t;
    while(t--){
        ll i,j,k,l;
        ll chk=1;
        cin>>n>>m;
        for(i=1;i<=m;i++){
            ll a,b;
            cin>>a>>b;
            
            if(a<=b){
                qr.eb(a,b);
                x.pb(a);
                x.pb(b);
                a+=n;
                b+=n;
                qr.eb(a,b);
                x.pb(a);
                x.pb(b);
            }
            else{
                b+=n;
                qr.eb(a,b);
                x.pb(a);
                x.pb(b);
            }
        }
        x.pb(-1);
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()),x.end());
        m=qr.size();
        for(auto &k:qr){
            k.ff=lower_bound(x.begin(), x.end(),k.ff)-x.begin();
            k.ss=lower_bound(x.begin(), x.end(),k.ss)-x.begin();
        }
 
        for(i=0;i<=x.size()+3;i++){
            lx[i]=i;
            rx[i]=i;
            bns[i]=0;
        }
 
        sort(all(qr),sf);
        
        for(auto k:qr){
            ll fl=fil(k.ff);
            bns[fl]++;
            
            while(1){
                ll nxt=fir(fl+1);
                if(nxt>k.ss+1) break;
                ll ngl=fir(nxt+1);
                if(x[fl]+bns[fl]>=x[nxt]){
                    lx[nxt]=fl;
                    rx[nxt]=ngl;
                    bns[fl]+=bns[nxt];
                }
                else break;
            }
            ll bi=fil(k.ss);
            if(x[bi]+bns[bi]>x[k.ss]+1){
                chk=0;
                break;
            }
        }
 
        if(chk) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
        x.clear();
        qr.clear();
    }
    
}