Problem Solving Diary #11

BOJ 25422. Seesaw

오름차순으로 정렬된 길이 $N$의 수열이 있고, 그 수열의 양쪽 끝 수 중 하나를 제거하는 작업을 $N-1$번 반복한다. 이 과정 동안 수열의 수들의 평균의 최댓값과 최솟값의 차를 최소화 해야 한다.

 

다항 시간 풀이를 만들려고 생각해 보면, 일단 상태가 $[l, r]$ 꼴로 표현될 것임을 쉽게 예측할 수 있다. 그러나 여기서 문제는 각 상태에 대해 두 가지 값을 관리해야 한다는 점이다. 지금까지 본 구간의 최대 평균과 최소 평균을 관리해야 한다. 그런데 문제는 이 두 값이 독립적이 아니라는 것이다. 즉, 상태 $[l, r]$까지 오는 방법 중 가능한 최대 평균의 최솟값 $M$과 가능한 최소 평균의 최댓값 $m$을 동시에 얻을 수 있을지 확실하지 않다는 것이다.

 

그렇다면 상태 $[l, r]$까지 가능한 최대 평균의 최솟값이 얼마일 지 생각해 보자. 이 값은 min(초기 평균, $[l, r]$ 구간의 평균)과 같다. 최대 평균의 최솟값은 자명하게도 이 값보다 작아질 수 없다. 이 값을 달성하는 방법은, 먼저 큰 수부터 차례대로 빼고, 다음으로 작은 수부터 차례대로 빼면 된다. 이 방법으로는 당연히 최소 평균을 최대화시킬 수 없다.

 

따라서 최적해를 달성하기 위해서는 최대 평균의 최소화, 그리고 최소 평균의 최대화 그 사이 어떤 적당한 지점을 잡아 타협해야 한다. 그 첫 단추는 그리 어렵지 않다. 가능한 평균의 개수는 $O(N^2)$ 개 정도이므로, 인자에 최대 평균의 최솟값 같은 걸 하나 넣어주면 DP의 복잡도는 $O(N^4)$가 된다. 이렇게 Subtask 2를 풀 수 있다.

 

그러나 상태에 이런 무거운 값을 넣는 것은 일반적으로는 별로 좋은 선택지가 아니다. 조금 다른 방법으로 생각해 보자.어떤 적당한 평균의 한계값 $m$과 $M$이 주어져서, 문제의 process가 평균값이 항상 $[m, M]$ 범위에 있게 하면서 완료될 수 있는지 판별하는 결정 문제를 풀 수 있을까? 이것은 greedy한 approach로 풀 수 있는데, 왼쪽 끝을 제거하는 경우와 오른쪽 끝을 제거하는 경우 중 범위 안에 평균이 들어가는 것을 계속 택하면 된다. 이 전략이 항상 성립함은 다음과 같은 명제를 생각하면 증명할 수 있다.

 

• $a < b < c < d$이고, 구간 $[a, c]$의 평균이 $[m, M]$ 안에 속하며, 구간 $[b, d]$의 평균이 $[m, M]$ 안에 속할 때, 구간 $[b, c]$의 평균도 $[m, M]$ 안에 속하는가?
  • 그렇다. $avg([a, c]) < avg([b, c]) < avg([a, d])$이기 때문이다.

 

이 명제를 통해 문제를 결정 문제로 바꾸는 방법을 알아냈다. 그런데 문제는 인자가 두 개라서, 이렇게 단순한 방법으로는 여전히 힘들다는 것이다. 이 방법을 곧바로 이용하면 $O(N^3 \log N)$ 정도의 풀이를 만드는 데에 그칠 뿐인데, 이것으로 해결할 수 있는 추가적인 Subtask는 없다.

 

한 가지 짚고 넘어가야 하는 것은, 위 방법을 통해 $m$이 주어졌을 때 가능한 최소 $M$의 값을 알 수 있다는 것이다. 여기서 $m$과 $M$으로 가능한 수가 $O(N^2)$ 가지가 있는데, $m$이 증가할 때 $M$이 어떻게 이동하는지를 보는 것이 좋을 것 같다. 이것을 모델링하기 위해서는 $(l, r)$을 정점으로 한 그래프를 그려볼 필요가 있다. $m$을 서서히 증가시킬 생각이기 때문에, 만약 $m$과 $M$이 정해져 있을 때 $(l+1, r)$과 $(l, r-1)$로 구간을 축소시키는 방법이 두 가지가 있다면 $(l, r-1)$을 항상 택하겠다고 하자. 이렇게 설정했을 때 $m$이 결정되면 path가 하나 새로 생겨날 것이다. 

 

그래프를 그리고 나면 한 턴이 지날 때마다 $r-l+1$의 크기가 1씩 준다는 것을 알 수 있다. (자명하다.) 그렇다면, 각 턴에서 어떤 칸을 밟게 될까? 일단 초기 평균값 $\bar{m}$과 가까울 수록 좋을 것이다. 이 값은 무조건 거쳐 가야 하는 평균이기 때문이다. 편의상 $r-l=d$라고 두자. 이렇게 하면 적당한 수 $X_d$가 존재해서, $[X_d, X_d+d]$의 평균은 $X_m$ 이하이고, $[X_d+1, X_d+d+1]$의 평균은 $\bar{m}$ 이상이게 하는 수 $X_d$가 항상 존재한다. 직관적으로 봤을 때 $r-l=d$인 상태에서는 이 두 상태 이외의 다른 상태를 거칠 이유가 전혀 없다.

 

그래서 각 깊이마다 가능한 상태를 두 개로 줄일 수 있다. 이렇게 하면 가능한 평균 최솟값, 최댓값 개수가 각각 $O(N)$으로 줄어들고, 최소 평균을 설정한 뒤 가능한 최대 평균의 최솟값을 구하는 식으로 문제를 $O(N^2)$에 풀 수 있다. 이렇게 하면 Subtask 3이 해결된다.

 

발상이 꽤 좋아 보이기 때문에 Full Task도 비슷한 방식으로 풀릴 것 같다. 이제 어떤 기교를 부릴 수 있을지 조금 생각해 보면, 평균 최솟값을 가능한 최대부터 시작해서 점점 내려 보거나, 반대로 최소부터 시작해서 점점 올려 보면 좋을 것 같다. 아니면 투 포인터로 최소 평균과 최대 평균을 들고 다니면서 관리해도 괜찮을 것 같다는 생각이 든다. 이렇게 최소 평균과 최대 평균이 주어졌을 때, 위의 그래프에서 갈 수 있는 칸이 색칠된다고 보면, 색칠된 칸만 이용해서 시작점에서 마지막 두 도착점 중 하나까지 갈 수 있는지를 보는 형태의 문제가 될 것이다.

 

잠시 그래프의 형태를 살펴보면, 다음과 같이 요약할 수 있다.

• 맨 윗 줄에 정점 $O$가 있고,
• 이후 $i$번째 줄에 정점 $A_{i-1}$과 $B_{i-1}$이 있다.
• $A_{i-1}$과 $A_i$는 연결되어 있으며, $B$도 마찬가지이다. $O$는 $A_1$, $B_1$과 연결되어 있다.
• $A_{i-1}$과 $B_i$가 연결되어 있거나, $A_i$와 $B_{i-1}$이 연결되어 있다. 둘 중 정확히 하나만 성립한다.

이 그래프에서 켜져 있는 정점만 이용해서 맨 아래 두 정점 중 하나까지 갈 수 있는지 판별해야 한다. 일반적인 그래프라면 이게 매우 어렵지만, 이 그래프는 특수한 형태이기 때문에 이 문제를 풀 수 있다. 다음 사실을 증명할 수 있다.

• 모든 $i$에 대해, $A_i$나 $B_i$ 둘 중 하나 이상 켜져 있으면, 끝까지 갈 수 있다.
  • 증명: $A_i$와 $B_i$가 둘 다 켜져 있으면 걱정할 것이 없다. 두 층 연속으로 한 쪽만 켜져 있는 경우가 있으면, 즉 예를 들어 $A_i$와 $B_{i+1}$이 켜져 있고, $A_{i+1}$과 $B_i$가 꺼져 있으면, $A_i$에서 $B_{i+1}$로 진행할 수 있음을 보일 수 있다. 위에서 설명한 명제를 통해 증명할 수 있다.

따라서 결국 보여야 하는 조건이 많이 완화되었다. 이 조건을 해석하면, 최소 상한 $X$와 최대 하한 $Y$에 대해 $X \le A_i$ 또는 $B_i \le Y_i$ 와 같은 형태로 보일 수 있다. 따라서 $A_i$를 정렬해 놓고 가면서 $B_i$ 최댓값을 구하는 식으로 문제를 풀 수 있다.

 

BOJ 25424. School Road

시작점부터 끝점까지 모든 경로가 최단경로인지를 묻는 문제이다. 일단 시작점부터의 끝점까지의 경로에 포함될 수 없는 점들이 있다. 이런 점은 시작점, 끝점과 다른 BCC에 있는 점들인데, 이들은 먼저 제거해 주자. 남은 점에 대해서, 모든 경로가 최단경로이려면 시작점에서 이 점까지의 거리 + 도착점에서 이 점까지의 거리가 나올 것이고, 그 거리가 최단경로와 같을 것이다. 또한 인접한 두 점 사이를 오갈 때도 이 값에 모순되는 정보가 나오면 안 된다.

 

위 모든 조건을 만족하는 그래프라면, 최단경로의 길이를 $L$이라고 할 때, 각 점은 시작점에서의 최단경로 $A_i$, 끝점에서의 최단경로 $L - A_i$를 가지고 있다. 주목할 것은 $A_i$가 감소하는 단순 경로가 존재하는지의 여부이다. 이런 단순 경로가 존재한다면 여전히 길이가 $L$ 초과인 경로가 생기기 때문에 안 된다.

 

이제 이런 경로가 없을 조건을 생각해 보자. 단절점이 있는 위치별로 분리해서 생각해도 되는데, 어차피 그 점은 무조건 지나야 하기 때문이다. 이제 단절점이 없는 어떤 컴포넌트를 생각해 보자. 이때 시작점에서 끝점으로 최단경로가 아닌 경로가 존재하는지를 판단해야 한다. 간선이 하나뿐인 컴포넌트는 제외하고 생각하자. 단절점이 없으므로 시작점과 끝점을 제외하고는 겹치지 않는 경로 두 개가 존재할 것이다. 경로 두 개가 존재한다는 것만으로는 문제의 조건을 위배하지 않는다. 문제는 경로 두 개 사이에 중간 간선이 존재하는 경우이다. 이 경우 경로를 진행하다가 중간 간선을 이용해 경로를 갈아탈 수 있으므로, 더 긴 경로가 생기게 된다. 따라서 각 컴포넌트에서 문제 조건을 만족하기 위해서는 중간 간선이 없는지만 확인해 주면 된다.

 

실제로는 한 컴포넌트 내에 최단 경로가 두 개를 넘어 세 개, 네 개일 수도 있는데, 각각의 중간 정점들끼리 연결되지 않았는지를 확인하면 된다. 이것을 확인하는 가장 쉬운 방법은 차수가 2인지를 확인하는 것이다. 차수가 2 이상이면 어딘가 다른 곳과 연결되었다고 짐작할 수 있다.

 

BOJ 10847. 자카르타의 마천루

문제를 보자마자 눈에 들어오는 점은 특이한 제한 $N \le 30000$이다. 생김새를 봐서 제곱을 의도한 것 같진 않고, 루트라고 하기에는 너무 작은데, 문제를 조금 읽고 생각해 보면 아이디어가 하나 떠오른다. $i$번 doge의 위치는 항상 $x_i \equiv a_i \mod b_i$일 수밖에 없는데, 이런 $(a_i, b_i)$ 쌍이 모든 $i$에 대해 다르다고 가정해 보자. 이렇게 할 경우 그래프를 만들어서 단순히 BFS를 돈다고 해도 간선 개수가 800만 개가 채 되지 않아서 문제를 풀 수 있다. 상수를 잘 줄이면 충분히 만점이 나올 수 있는 정도의 양이다.

 

그렇다면 $(a_i, b_i)$가 같은 게 여러 개 있으면 어떻게 될까? 어차피 간선은 최대 800만 개라서 상관이 없을 것 같지만, 이 경우에는 이미 방문한 점을 체크하기 어렵다는 문제가 생긴다. 이걸 체크하려면 log가 하나 더 붙기 때문이다. 이 800만 남짓한 수를 $S$라고 하자. $O(S \log S)$는 절대 안 돌 것이다. (TL이 1초) 따라서 선형에 문제를 푸는 아이디어가 하나 더 필요하다.

 

여기서 루트를 가져와야 한다. 시간 복잡도는 여전히 $O(S)$이지만, 세부적인 처리를 하는 과정에서 루트를 사용할 것이다. 현재 $(a_i, b_i)$인 doge를 이용하는 상황에서 점 $x$에 도달했을 때, 다음과 같이 처리한다: (칸의 개수를 $N$이라고 하자.)

• $b_i < \sqrt{N}$인 경우 $[b_i, x]$를 담는 table에 표시한다. 이 table의 크기는 최대 $O(N \sqrt {N})$이다.
• $b_i > \sqrt{N}$인 경우 해당 $(a_i, b_i)$에서 가능한 $x$의 개수가 최대 $\sqrt {N}$개라는 점을 이용한다. $(a_i, b_i)$ 쌍별로 인덱스를 붙여 놓는데, 이것은 전처리 과정에서 각 doge마다 붙이면 되는 것이기에 $O(N \log N)$에 가능하다. 그 다음은 단순히 table을 만들어 표시하면 $O(N \sqrt {N})$에 된다.

이런 아이디어로 문제를 $O(N \sqrt {N} + S)$에 풀 수 있으며, 위에서도 언급했듯이 $S$는 약 800만 정도라서 문제를 풀 수 있다. 상수가 조금 빠듯한 편이라서 조심해야 한다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int G = 175;

struct dat{
    int x, doge, dist;
    dat(){}
    dat(int x, int doge, int dist): x(x), doge(doge), dist(dist){}
};

int n, k;
bool visited1[30002][180];
bool visited2[30002][180];
bool started[30002];
int st[30002], a[30002], b[30002], idx[30002];
vector<int> lst[30002];

dat que[10000002];
int que_size, que_front;

dat pop(){
    return que[que_front++];
}

void push(dat tmp){
    que[que_size++] = tmp;
}

inline bool chk(int d, int x){
    if(b[d] <= G) return visited1[x][b[d]];
    return visited2[idx[d]][x/b[d]];
}

inline void mark(int d, int x){
    if(b[d] <= G) visited1[x][b[d]] = 1;
    else visited2[idx[d]][x/b[d]] = 1;
}

inline void go(dat &tmp){
    int r = b[tmp.doge];
    if(tmp.x - r >= 0 && !chk(tmp.doge, tmp.x - r)) mark(tmp.doge, tmp.x-r), push(dat(tmp.x - r, tmp.doge, tmp.dist+1));
    if(tmp.x + r <  n && !chk(tmp.doge, tmp.x + r)) mark(tmp.doge, tmp.x+r), push(dat(tmp.x + r, tmp.doge, tmp.dist+1));
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=k; i++){
        scanf("%d %d", &st[i], &b[i]);
        a[i] = st[i] % b[i];
        lst[st[i]].push_back(i);
    }

    vector<pair<int, int> > vec;
    for(int i=1; i<=k; i++) vec.push_back(make_pair(a[i], b[i]));
    sort(vec.begin(), vec.end());
    for(int i=1; i<=k; i++){
        int tmp = lower_bound(vec.begin(), vec.end(), make_pair(a[i], b[i])) - vec.begin() + 1;
        idx[i] = tmp;
    }

    push(dat(st[1], 1, 0));
    mark(1, st[1]);
    while(que_size != que_front){
        dat tmp = pop();
//        printf("x: %d, doge: %d, dist: %d\n", tmp.x, tmp.doge, tmp.dist);
        if(tmp.doge == 2){
            printf("%d", tmp.dist);
            return 0;
        }
        if(!started[tmp.x]){
            started[tmp.x] = 1;
            for(int d: lst[tmp.x]){
                if(d == 2){
                    printf("%d", tmp.dist);
                    return 0;
                }
                if(chk(d, tmp.x)) continue;
                mark(d, tmp.x);
                dat tmp2 = dat(tmp.x, d, tmp.dist);
                go(tmp2);
            }
        }
        go(tmp);
    }

    printf("-1");
}