Problem Solving Diary #6

BOJ 22031. Yet Another Interval Graph Problem

먼저 구간들을 끝점 순서대로 정렬합시다. 즉 $i < j$이면 $e_i \le e_j$입니다. $DP[i]$를 $i$번 구간이 선택된 가장 번호가 큰 구간일 때의 답으로 정의합시다. 이때 $j < i$인 $j$에 대해 $DP[j]$에서 $DP[i]$의 상태 전이를 빠르게 구할 수 있으면 문제를 $O(N^2)$ 남짓한 시간 복잡도에 풀 수 있습니다.

 

$DP[j]$에서 $DP[i]$로 전이하는 방법을 찾아봅시다. 이는 곧 $[j+1, i]$ 인덱스를 가진 범위 중 $K$개 이하를 잘 선택해 최대 가중치를 가진 연결 성분을 구하는 것과 같은데, $DP[j]$의 정의상 $j$번 범위를 이미 선택했으므로 다음 연결 성분의 범위들은 모두 시작점이 $e_j$보다 커야 합니다. 이걸 나이브하게 구현하면 $O(N^3 \log N)$이 됩니다. 더 줄일 수 있는지 살펴봅시다.

 

이런 DP는 보통 cost 계산을 나이브하게 하면 터지기 때문에, $i$나 $j$ 둘 중 하나를 고정시키고 나머지 하나를 계속 늘려 나갈 때마다 cost를 빠르게 갱신해주는 방법을 사용해 주게 됩니다. 이 문제에서는 $j$를 고정시키는 것이 편합니다. $j$를 고정하고 $i$를 하나씩 늘려 가면서 $e_{j-1} < s_i$라면 $w_i$를 힙에 넣습니다. 힙의 크기가 $K$ 이하가 되도록 계속 관리해 주면서 힙에 들어 있는 모든 원소의 합을 구하면 이것이 전이할 때의 비용이 됩니다. 이렇게 하면 문제가 $O(N^2 \log N)$에 풀립니다.

 

BOJ 17438. 전생했더니 슬라임 연구자가 아니었던 건에 대하여

풀이만 고민해 보고 직접 짜 보진 않았기 때문에, 오류가 있을 수 있습니다.

#1. 불변량

이런 Constructive 문제에서 해 볼 수 있는 첫 관찰은 불변량이 존재하는지에 대한 것입니다. 단순히 각 색깔에 0 1 2의 가중치를 부여하고 나면, 아무리 연산을 해도 가중치 합이 3으로 나눈 나머지가 변하지 않는다는 것을 알 수 있습니다. 이것이 하나의 불변량이 됩니다. 이 불변량으로부터 얻을 수 있는 사실은,

• $NM$이 3의 배수가 아닌 경우 (모든 슬라임의 색을 똑같이 만드는 것이 가능하다면) 최종 색이 고정된다.
• $NM$이 3의 배수인 경우, 가중치 합이 3의 배수가 아니면 무조건 불가능하고, 가중치 합이 3의 배수이면 최종 색에 대한 힌트를 알 수 없다. (즉 아직 세 색 모두 가능할 수 있다.)

실제로 예제 2번의 경우 불가능 출력이 나왔는데, 이는 $NM$이 3의 배수이고 가중치 합이 3의 배수가 아니기 때문입니다. 위에서 짚어낸 불가능 조건을 정확히 만족하고 있습니다.

#2. $N=1$, $M \equiv 0, 1 (\mod 3)$

$N=1$일 때 문제를 풀 수 있는지 살펴봅시다. 만약 $N=1$일 때 푸는 방법을 발견하면 이 방법을 각 가로줄에 적용해 같은 가로줄의 슬라임 색을 모두 같게 만든 뒤, 다시 이 기법을 각 세로줄에 적용해 모든 슬라임 색을 같게 만들 수 있을 것입니다. (가로줄 작업이 끝난 뒤 모든 세로줄의 슬라임 색 배치는 서로 같기 때문에, 같은 알고리즘을 적용하면 당연히 같은 결과가 나올 것입니다.)

 

$M$이 3의 배수가 아니라고 한다면, 최종 결과가 고정됩니다. 이는 간단한 계산으로 해결이 가능합니다. $M$개 칸에 적힌 수의 합 (세 색깔을 각각 수 0, 1, 2에 대응) $S$에 대해 $M \times x \equiv S$ (앞으로 mod 3 표기는 생략합니다.) 인 $x \in \{ 0, 1, 2 \}$는 단 하나뿐이기 때문입니다.

 

여기까지 왔다면 가장 먼저 시도해 볼 수 있는 방법은 앞에서부터 차례대로 $x$로 만드는 방법입니다. 하지만 이 방법을 사용할 경우 뒤에 있는 칸이 3의 배수 개만큼 남았을 때 모두 같아져 버릴 수 있습니다. 이 부분은 잠깐 앞에서 만들어 준 $x$를 다른 걸로 바꿔준 다음, 다시 과정을 반복하면 됩니다. 이런 나쁜 상황이 무한히 많이 일어날 수 있다고 생각했는데, 시뮬레이션을 돌려 보면 그런 상황이 잘 나오지 않았습니다. 이렇게 간단한 시뮬레이션을 돌려 보면 생각보다 과정이 빨리 끝나는 것을 알 수 있는데, 랜덤 데이터의 경우 $2M$번 안으로 끝남을 확인할 수 있었습니다.

 

이 알고리즘의 정당성에 대한 증명은 하지 못했지만, 대략적인 추측은 다음과 같습니다. 가장 작업을 많이 할 것으로 추측되는 케이스는 $11111111\cdots 11112$와 같이 $x$가 아닌 수가 앞에 많이 반복되는 패턴입니다. 이걸 $x$로 만들기 위해 작업을 하다 보면 $\cdots020202020202$와 같이 두 개의 숫자가 반복되는 형태가 되는데, 이 형태는 앞으로의 작업 횟수를 크게 줄여 주는 형태입니다. 서로 같은 수가 연속한 경우 작업할 수 없어서 자유도가 많이 줄어드는데, 다른 수가 연속한 경우 언제든지 작업을 수행할 수 있기 때문입니다.

#3. $N=1$

$M$이 3의 배수인 경우 불가능 케이스인지부터 판별합니다. 불가능 케이스가 아니라면, $x=A_1$로 잡고 위 알고리즘을 수행시키면 역시 랜덤 데이터에서 잘 돌아감을 확인할 수 있습니다.

#4. Full Task

이제 각 가로줄에 대해 위 알고리즘을 적용하고, 다시 세로줄에 대해 위 알고리즘을 적용하면 풀 수 있을까요? 그렇지 않습니다. 여기서 추가적으로 고민해 줘야 할 케이스가 있는데, 아래와 같은 상황입니다.

• (Case 1) $M$이 3의 배수이고, 전체 $A_{ij}$의 합은 3의 배수이지만, 어떤 특정 $i$에 대해 $A_{ij}$의 합이 3의 배수가 아니라 해당 가로줄을 완성할 수 없는 상황
• (Case 2) 가로줄 작업까진 성공적으로 완료했지만, $N$과 $M$이 3의 배수이고 어떤 세로줄에 있는 모든 수들의 합이 3의 배수가 아니라 작업이 중단되는 상황

먼저 Case 1부터 해결해 봅시다. 만약 $M$이 3의 배수이고 $A_ij$의 합이 3의 배수라면 각 가로줄의 합 역시 3의 배수로 맞춰 주는 작업이 필요합니다. $i$번 가로줄에 있는 수들의 합을 구한 뒤, 3으로 나눈 나머지를 $S_i$라고 합시다. $S$라는 배열은 길이 $N$의 배열이고, 모든 수의 합이 0입니다.

 

만약 배열 $S$를 $1 \times N$ 격자로 생각하고 이 문제를 해결하고자 하면 어떻게 될까요? 모든 수의 합이 0이기 때문에 항상 해가 존재합니다. 갑자기 뜬금없는 전환이 나왔지만 일단 계속 풀이를 봅시다. 원래 문제에서의 "작업"은 값이 다른 두 개의 연속된 위치, 즉 $A$와 $B$의 값을 가진 두 위치를 모두 $C$의 값으로 바꿔 주는 작업이었습니다. 그런데 배열 $B$에서 $B_i$와 $B_{i+1}$이 다르다는 것은 $i$번 가로줄에 적힌 수의 합과 $i+1$번 가로줄에 적힌 수의 합이 mod 3으로 다르다는 것을 의미합니다. 이는 $A_{ij} \neq A_{(i+1)j}$인 $j$가 존재한다는 사실을 의미합니다. (간단한 대우증명법입니다.) 이건 뭔가 앞의 "작업이 가능할 조건"과 상당히 닮았습니다.

 

원래 문제에서 작업 뒤의 결과는 $AB \rightarrow CC$였습니다. 그렇다면 작업의 단위가 칸 하나가 아닌 줄 하나가 된 현재에도 이걸 보여줄 수 있을까요? 결론부터 말하자면 가능합니다. 두 인접한 가로줄에는 위아래로 같은 칸이 붙어있기도 하고, 다른 칸이 붙어있기도 합니다. 여기서 다른 칸에 전부 작업을 해 주면 $AB \rightarrow CC$가 실제로 줄 단위에서도 동작하는 메커니즘임을 알 수 있습니다.

 

이제 줄 단위로 $1 \times M$ 해법을 적용하면 $B_i$가 모두 같은 상태가 만들어집니다. $N$이 3의 배수가 아니라면 모두 0으로 같아질 것까지 알 수 있습니다. 하지만 $N$과 $M$이 모두 3의 배수이고 $B_i$가 모두 0이 아닌 값으로 같을 경우 여전히 알고리즘을 사용할 수 없습니다. 이 경우 다음과 같이 처리합니다.

 

첫 번째 가로줄에 적힌 수들의 합은 3의 배수가 아닙니다. $M$이 3의 배수이므로 이 말은 다른 수가 적어도 하나 있다는 뜻입니다. 수를 "바꿀" 수 있는 여지가 생긴 것입니다. $B_1=0$으로 만들 수만 있다면 해결되기 때문에, 이 전략을 찾는 데 집중합시다. 1번 가로줄에 서로 다른 인접한 두 수를 $A$와 $B$라고 하고, 나머지 종류의 수 하나를 $C$라고 합시다. 정말 많은 케이스가 있는데 하나하나 분석해 봅시다. 

 

첫째로 $A=0$이고 $B=1$인 경우입니다. 이때 $A$ 밑에 있는 수를 $x$라고 합시다. $x$가 1이나 2라면 $A$와 바로 작업할 수 있는데, 작업했을 때 $B_1 \neq 1$인 상황이 만들어진다면 $A$랑 $B$를 먼저 작업한 다음 $A$와 $x$를 작업하면 항상 처리가 됩니다. $x$가 0이라면 $A$와 $B$를 교환, $A$와 $x$를 교환, $A$와 $B$를 교환 이 3단계 중 반드시 $B_1 = 1$인 타이밍이 오기 때문에 그때 멈춰 주면 됩니다.

 

둘째로 $A=1$이고 $B=2$인 경우입니다. 나머지 경우는 모두 대칭적으로 처리되므로 여기까지만 고려해도 됩니다. 만약 $x=0$이라면, 아래 두 방법 중 하나로 해결됩니다.

• $A$와 $x$를 교환
• 위 메커니즘으로 처리되지 않으면 $A$, $B$, $x$가 모두 서로 달라서 이 세 수만 작업하고는 해결할 수 없습니다. $B$ 아래에 적힌 수를 $y$라고 합시다. $y=0$인 경우 $B$와 $y$를 교환, $y=1$인 경우 $x$와 $y$를 교환한 뒤 $A$와 $x$를 교환, $y=2$인 경우 $x$와 $y$, $A$와 $B$, $B$와 $y$를 차례로 교환하면 됩니다.

BOJ 5466. 상인

일단 행사가 열리는 시간이 전부 다르다고 가정해 봅시다. 가장 먼저 관찰해야 할 건 DP 각이 잡힌다는 겁니다. $DP[i]$를 마지막으로 방문한 행사가 시간순으로 $i$번째 행사일 때의 최고 이익이라고 합시다. $DP[j] \rightarrow DP[i]$의 전이를 나이브하게 하면 $O(N^2)$에 풀 수 있고 이렇게 하면 (본 대회 기준) 15점을 받습니다. $DP[i] + L_i \times D$, $DP[i] - L_i \times U$를 담는 세그먼트 트리를 활용하면 $O(N \log N)$에 풀 수 있습니다.

 

이제 시간이 겹칠 때를 고려합시다. 시간이 같은 행사들의 경우 위치의 오름차순 또는 내림차순으로 방문한다고 해도 답은 같게 유지됩니다. 따라서 시간이 같은 행사들은 오름차순으로 한 번, 내림차순으로 한 번 순회하고 그 둘 중 최댓값을 세그먼트 트리에 넣어 주면 됩니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Market{
    int day; int loc; int w;

    bool operator<(const Market &r)const{
        return day == r.day ? loc < r.loc : day < r.day;
    }
};

struct segTree{
    int tree[1048578];

    void init(int i, int l, int r){
        if(l==r){
            tree[i] = -2e9;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m), init(i*2+1, m+1, r);
        tree[i] = -2e9;
    }

    void update(int i, int l, int r, int x, int v){
        if(l==r){
            tree[i] = max(tree[i], v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return -2e9;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} treeU, treeD;

int n; int u, d; int s;
Market arr[500002];

int main(){
    scanf("%d %d %d %d", &n, &u, &d, &s);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d", &arr[i].day, &arr[i].loc, &arr[i].w);
    }
    sort(arr+1, arr+n+1);

    const int MAX = 500001;
    treeU.init(1, 1, MAX), treeD.init(1, 1, MAX);
    treeU.update(1, 1, MAX, s, -u*s);
    treeD.update(1, 1, MAX, s, d*s);
    for(int i=1; i<=n; i++){
        int j = i;
        while(arr[j+1].day == arr[i].day) j++;
        if(i==j){
            int val = max(treeU.query(1, 1, MAX, arr[i].loc, MAX) + arr[i].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[i].loc) - arr[i].loc * d) + arr[i].w;
            treeU.update(1, 1, MAX, arr[i].loc, val-u*arr[i].loc);
            treeD.update(1, 1, MAX, arr[i].loc, val+d*arr[i].loc);
            continue;
        }

        vector<pair<int, int> > vec;
        int btmp = -2e9;
        for(int x=i; x<=j; x++){
            int val = max(treeU.query(1, 1, MAX, arr[x].loc, MAX) + arr[x].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[x].loc) - arr[x].loc * d) + arr[x].w;
            val = max(val, btmp - arr[x].loc * d + arr[x].w);
            vec.push_back(make_pair(arr[x].loc, val));
            btmp = max(btmp, val + arr[x].loc * d);
        }
        for(int x=j; x>=i; x--){
            int val = max(treeU.query(1, 1, MAX, arr[x].loc, MAX) + arr[x].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[x].loc) - arr[x].loc * d) + arr[x].w;
            treeU.update(1, 1, MAX, arr[x].loc, val-u*arr[x].loc);
            treeD.update(1, 1, MAX, arr[x].loc, val+d*arr[x].loc);
        }
        for(auto p: vec){
            treeU.update(1, 1, MAX, p.first, p.second-u*p.first);
            treeD.update(1, 1, MAX, p.first, p.second+d*p.first);
        }
        i=j;
    }

    int ans = max(treeU.query(1, 1, MAX, s, MAX) + s*u,
              treeD.query(1, 1, MAX, 1, s) - s*d);
    printf("%d", ans);
}

BOJ 18038. Jumping Grasshopper

업데이트가 없을 때 푸는 풀이 중 하나는 다음과 같습니다. 먼저 가장 높은 점을 찾은 뒤, 그 점 왼쪽과 오른쪽에 각각 monotone chain을 관리합니다. monotone chain을 그림으로 나타내면 이렇습니다.

점 $x$에 쿼리가 들어오면 두 가지 케이스가 있습니다. 편의상 $x$가 최고점 왼쪽에 있다고 합시다. $x$번 점이 monotone chain 위에 있다면 간단한 케이스 워크로 처리됩니다. 방향이 L일 경우 그 점이 답이 되고 방향이 R일 경우 monotone chain상에서 $x$ 오른쪽에 있는 점이 답이 됩니다.

 

반면 $x$번 점이 monotone chain 위에 없다면 이때는 무조건 monotone chain 상에서 $x$보다 오른쪽에 있는 가장 왼쪽 점이 답이 됩니다. 이유는 간단합니다. monotone chain 아래에 있는 점은 모두 왼쪽이나 오른쪽에 더 큰 점이 있기 때문에 끝점이 될 수 없습니다. 따라서 monotone chain에서 $x$ 왼쪽으로 가장 가까운 점 $L$, $x$ 오른쪽으로 가장 가까운 점 $R$ 둘 중 하나를 반드시 지나야 하는데, $L$에 진입했을 때 무조건 왼쪽으로 점프해 진입했을 것이므로 이때 방향은 오른쪽이 되고 $R$에 진입합니다. $R$에 진입했을 때는 무조건 오른쪽으로 점프해 진입했을 것이므로 왼쪽 방향을 쳐다보게 되고, 왼쪽 방향에 $R$보다 더 높은 점이 없으므로 무조건 $R$에서 끝이 납니다.

 

업데이트 쿼리가 들어와도 문제는 크게 어려워 지지 않습니다. set을 이용해 monotone chain을 쉽게 관리할 수 있으므로 $O(N \log N)$ 시간에 문제를 풀 수 있습니다.

BOJ 15978. 족보

서브태스크 1, 2 (44점)

만약 답이 YES라면, 트리 1의 노드 $x$와 트리 2의 노드 $y$는 아래 두 성질 중 하나를 만족합니다.

• $x$번 노드 아래에 있는 리프와 $y$번 노드 아래에 있는 리프는 교집합이 없다.
• $x$번 노드 아래에 있는 리프와 $y$번 노드 아래에 있는 리프 집합 둘 중 하나가 다른 쪽에 포함된다.

이 조건을 만족하지 않는 두 노드가 있는지 검사하는 코드를 짜면 서브태스크 2까지 $O(N^3)$에 풀 수 있습니다.

 

서브태스크 3, 4 (100점)

리프에서 루트까지 올라가는 과정에서 리프 집합이 어떻게 변하는지를 살펴 보면, 다른 노드들의 리프 집합을 흡수해 가면서 계속 커지는 것을 관찰할 수 있습니다. 이 형태를 유니온 파인드에 접목시켜 봅시다.

 

아래에 있는 리프 노드가 작은 상위 노드들부터 보면서, 자식들 아래에 있는 리프 노드를 모두 Merge해 줍니다. 이때 이 집합의 크기가 리프 노드의 개수와 같다면 문제가 없지만, 리프 노드의 개수보다 크다면 불가능으로 판정하면 됩니다. 노드를 보는 정렬 기준이 조금 까다로운데, 일단 리프 노드의 개수를 먼저 보고, 이것이 같다면 더 깊은 것부터 봐야 반례가 생기지 않습니다.

 

BOJ 16357. Circuits

계속 다이아만 풀다 보니 힘들어서 쉬운 플래티넘도 하나 풀었습니다.

 

일단 직사각형의 x좌표 경계는 전혀 중요하지 않으므로 y좌표 경계만 따 와서 수직선 상의 구간이라고 생각해도 됩니다. 그러면 수직선 상의 점 두 개를 잡아 점 둘 중 하나를 포함하는 구간을 최대화시키는 문제로 환원할 수 있습니다. 먼저 점을 하나만 찍는다고 생각해 봅시다. 각 구간에 대해 $[l, r]$ 구간에 1을 더한 후, 최댓값을 찾으면 답이 됩니다.

 

이제 점 두 개를 찍어야 하는 상황입니다. 왼쪽 점을 고정하고 난 뒤 오른쪽 점을 적당히 잡아 답을 최대화시키는 기법을 찾아 봅시다. 왼쪽 점을 고정하고 나면 그 점을 포함하는 구간들은 이미 답으로 정해진 뒤이기 때문에, 해당 구간의 $[l, r]$에서 -1을 빼 주고 나서 최댓값을 구해 주면 왼쪽 점을 고정시켰을 때의 답이 됩니다. 또한 우리가 고정시킨 점은 무조건 "왼쪽" 점이므로, 그 점 왼쪽에 있는 구간들도 모두 생각에서 제외시켜도 됩니다. 즉, 왼쪽 점으로 가능한 것을 맨 왼쪽부터 하나씩 시험해 보면서 겹치는 구간이 생기는 즉시 세그먼트 트리의 해당 $[l, r]$에서 1씩을 빼주고, 자기 오른쪽 점들 중 최댓값을 구해 주면 답을 찾을 수 있게 됩니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAX = 200001;

struct Rect{
    int l, r;
    Rect(){}
    Rect(int l, int r): l(l), r(r){}

    bool operator<(const Rect &nxt){
        return l < nxt.l;
    }
};

struct segTree{
    int tree[800002], lazy[800002];
    segTree(){}

    void propagate(int i, int l, int r){
        tree[i] += lazy[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    int query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }

    void update(int i, int l, int r, int s, int e, int v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }
} tree;

int n, k;
Rect arr[100002];

void renumber(){
    vector<int> vec;
    for(int i=1; i<=n; i++) vec.push_back(arr[i].l), vec.push_back(arr[i].r);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(int i=1; i<=n; i++) arr[i].l = lower_bound(vec.begin(), vec.end(), arr[i].l) - vec.begin()+1;
    for(int i=1; i<=n; i++) arr[i].r = lower_bound(vec.begin(), vec.end(), arr[i].r) - vec.begin()+1;
}

int ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d %d", &arr[i].r, &arr[i].r, &arr[i].l, &arr[i].l);
    }
    renumber();
    sort(arr+1, arr+n+1);
    for(int i=1; i<=n; i++){
        tree.update(1, 1, MAX, arr[i].l, arr[i].r, 1);
    }

    vector<int> tVec (MAX+5);
    for(int i=1; i<=MAX; i++) tVec[i] = tree.query(1, 1, MAX, i, i);

    int pnt = 1;
    for(int i=1; i<=MAX; i++){
        while(pnt <= n && arr[pnt].l <= i){
            tree.update(1, 1, MAX, arr[pnt].l, arr[pnt].r, -1);
            pnt++;
        }
        ans = max(ans, tVec[i] + tree.query(1, 1, MAX, 1, MAX));
    }
    printf("%d", ans);
}