Problem Solving Diary #7

BOJ 14636. Money for Nothing

문제는 $\max_{1 \le i \le m} \max_{1 \le j \le n} (q_j - p_i) (e_j - d_i)$를 구하는 것입니다. 식의 형태가 직사각형의 넓이를 구하는 것과 닮았기 때문에, $(p_i, d_i)$, $(q_j, e_j)$ 상에 플로팅한 기하 문제로 바꿔 봅시다.

 

모든 점 쌍을 시도해 보기에는 시간이 너무 오래 걸립니다. 여기서 관찰해야 할 사실 하나는 [절대로 답에 포함될 수 없는 점]이 존재한다는 것입니다. 예를 들어, $(p_i, d_i)$가 $(p_j, d_j)$보다 오른쪽 위에 있다면 $(p_i, d_i)$는 절대 답에 포함될 수 없습니다.

 

또한 어떤 $(q_i, e_i)$에 대해서도 이득을 볼 수 없는 $(p_i, d_i)$도 후보에서 제거해 줄 수 있습니다.이러한 점들을 모두 지우고 나면 남은 $(p_i, d_i)$는 오른쪽으로 갈수록 $y$좌표가 작아지는 형태가 되고, 이는 $(q_i, e_i)$도 마찬가지입니다.

 

 

이제 아래 사실을 증명합니다.

• $(p_i, d_i)$ 오른쪽 위에 있으면서 가장 큰 이득을 볼 수 있는 $(q_j, e_j)$에 대해, $i$가 정해졌을 때의 $j$ 값을 $opt_i$라고 정의하자. $i \le j$일 때 $opt_i \le opt_j$이다.

이 사실은 $N=2$일 때만 증명해도 무리가 없습니다. 따라서 $N=2$, $M=2$일 때 $opt_1 = 2$이고 $opt_2 = 1$인 상황이 존재하지 않음을 보이면 됩니다.

위 그림에서 네 개의 점 사이의 $x$좌표 간격을 왼쪽부터 차례대로 $a$, $b$, $c$라고 두고, 같은 방식으로 $y$좌표 간격을 아래부터 각각 $d$, $e$, $f$라고 해 봅시다. $\min(a, b, c, d, e, f) \ge 0$ 일 때, 아래 두 조건이 동시에 만족할 수 없음을 보이면 됩니다.

• $(a+b)(e+f) < (a+b+c) \times e$, 즉 $bf - ce < -af$
• $(b+c)(d+e) < (d+e+f) \times b$, 즉 $bf - ce > cd$

그런데 위 식에서 $bf - ce < 0$이고, 아래 식에서 $bf - ce > 0$이 됩니다. 따라서 모순이 이끌어지고, 항상 $opt_1 \le opt_2$임을 알 수 있습니다.

 

이 조건까지 찾아냈다면 남은 것은 Divide & Conquer Optimization을 이용해 $O(N \log N)$에 답을 구하는 것뿐입니다.

 

BOJ 18189. 참 어려운 문제

어떤 색 $x$에 대해, 트리 위의 정점들을 아래와 같이 두 종류로 나눌 수 있습니다.

• 정점의 색이 $x$이다.
• 정점의 색이 $x$가 아니다.

먼저 색 $x$를 고정한 뒤, 트리의 각 정점에 "색깔"이 있다고 생각하지 말고, 색이 $x$인 정점을 "색칠되어 있다", 색이 $x$가 아닌 정점을 "색칠되어 있지 않다"고 합시다. 이렇게 하면 색이 $x$인 점들에 대해서만 편하게 생각할 수 있습니다.

 

색칠된 정점이 두 개 이상 존재한다고 합시다. 이때 아래와 같이 나머지 정점들을 세 구역으로 나눌 수 있습니다.

만약 왼쪽 구역이나 오른쪽 구역에 루트가 있다면, 문제의 조건에 모순이 됩니다. 따라서 루트는 무조건 가운데 구역에 존재해야 합니다. 또한 두 노드 역시 루트가 될 수 없습니다.

 

색을 고정하고 이런 식으로 가능한 노드 후보를 줄여 나가는 접근을 할 수도 있지만, 여기서는 노드를 고정하는 것이 더 편리합니다. 노드를 고정하고 그 노드를 "임시 루트"로 설정합니다. 임시 루트와 인접한 정점 $c_1, c_2, \cdots, c_k$를 살펴봅시다. $c_i$의 서브트리에 임시 루트와 색이 같은 정점이 있다면 $j \neq i$인 $c_j$의 서브트리에 있는 정점들을 후보에서 제거할 수 있습니다. 이 처리는 오일러 투어 트릭(dfs ordering)과 누적합을 이용하면 가능합니다.

 

단 한 번도 후보에서 제거되지 않은 점들만이 루트로 가능합니다. 이 점들이 답이 됩니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[250002];
vector<int> link[250002];
vector<int> eulerVec[250002];

int in[250002], idx[250002], sz[250002], out[250002], inCnt;
ll sum[250002];

void dfs(int x, int par = -1){
    in[x] = ++inCnt, idx[inCnt] = x;
    sz[x] = 1;
    for(auto y: link[x]){
        if(y == par) continue;
        dfs(y, x);
        sz[x] += sz[y];
    }
    out[x] = in[x] + sz[x] - 1;
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
    }
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }

    dfs(1);
    for(int i=1; i<=n; i++) eulerVec[arr[i]].push_back(in[i]);
    for(int i=1; i<=n; i++) sort(eulerVec[i].begin(), eulerVec[i].end());

    for(int i=1; i<=n; i++){
        int c = arr[i];
        for(auto y: link[i]){
            if(in[y] < in[i]){ /// y가 i의 부모
                if(eulerVec[c].front() < in[i] || eulerVec[c].back() > out[i]){
                    sum[in[i]]++;
                    sum[out[i]+1]--;
                }
            }
            else{ /// y가 i의 자식
                if(lower_bound(eulerVec[c].begin(), eulerVec[c].end(), in[y]) !=
                   upper_bound(eulerVec[c].begin(), eulerVec[c].end(), out[y])){
                    sum[1]++;
                    sum[in[y]]--;
                    sum[out[y]+1]++;
                }
            }
        }
    }

    for(int i=1; i<=n; i++) sum[i] += sum[i-1];

    ll ans0 = 0, ans1 = 0, ans2 = 0;
    for(int i=1; i<=n; i++) if(!sum[in[i]]) ans0++, ans1 += i, ans2 += ll(i)*ll(i);
    printf("%lld\n%lld\n%lld", ans0, ans1, ans2);
}

 

BOJ 24028. 사진 촬영

먼저 몇 가지 관찰을 합시다.

• 자리를 모두 바꾼 뒤에 사진을 찍어도 됩니다. 만약 사진을 먼저 찍고 자리를 바꾼 뒤 다시 사진을 찍는 것이 최적해라면, 자리를 바꾸지 않아도 손해 보지 않습니다.
• 단체 사진을 찍을 사람이라면 독사진을 찍지 않아도 됩니다.
• 한 사람이 단체 사진에 여러번 찍힐 수는 없습니다. 그런 경우가 있다면, 그냥 더 긴 단체 사진 하나를 찍는 것이 이득입니다.
• 독사진 비용이 $B$보다 작은 사람이라도, 옆 사람들의 가격과 $K$ 등의 영향으로 인해 단체 사진을 찍는 것이 유리한 경우가 존재합니다.

따라서 각 사람은 독사진 또는 단체 사진 중 하나에 정확히 한 번 찍히게 됩니다. 제한이 $N \le 5000$이고 비용을 구하는 문제인 경우 $O(N^2)$ 정도의 DP를 생각해 볼 수 있습니다. 

 

자리를 모두 바꾸고 단체 사진을 찍게 되는데, 단체 사진끼리는 서로 겹치지 않는다는 조건이 있습니다. 따라서 찍은 단체 사진(개수를 편의상 $M$이라고 합시다.)에 왼쪽부터 번호를 붙일 수 있습니다. 왼쪽부터 단체 사진의 번호를 각각 1번, 2번, ..., $M$번이라고 붙입시다.

 

단체 사진은 연속된 사람들을 찍습니다. 하지만 이건 사진을 찍었을 때의 이야기고, 초기 상태에서는 어떨까요? 예제에서도 보듯이 연속하지 않을 수 있습니다. 그렇다면 $i$번 단체 사진에 찍힌 사람 중 초기 위치의 최솟값을 $L_i$, 초기 위치의 최댓값을 $R_i$라고 해 봅시다. 이렇게 하면 $[L_i, R_i]$들끼리는 서로 겹치지 않습니다. (자명한 사실입니다. 단체 사진을 찍기 위해 단체 사진에 찍힐 사람 두 명의 순서를 바꾸는 것은 손해이기 때문입니다. 단체 사진에 찍힐 사람들의 순서는 유지되어야 합니다.)

 

여기까지 왔으면 풀이의 방향성이 대충 보입니다. 초기에 $[i, j]$ 구간에 있는 사람들을 봅시다. 이 구간에서 학생들의 위치를 적당히 옮긴 뒤, 단체 사진을 정확히 한 장 찍고 나머지 학생들은 독사진을 찍는다고 해 봅시다. 이때의 최소 비용을 $Cost[i][j]$로 정의하면, 이 배열을 이용한 DP로 문제를 해결할 수 있게 됩니다.

 

이제 $Cost[1][N]$을 구하는 특수한 경우의 문제를 풀어 봅시다. 학생은 앞에서도 봤다시피 두 그룹으로 나눌 수 있습니다.

• 독사진을 찍을 학생: $X$라는 표식을 달아 줍니다.
• 단체 사진을 찍을 학생: $Y$라는 표식을 달아 줍니다.

처음에 학생의 배치는 $XYXXY\cdots$와 같이 $X$와 $Y$가 섞여 있는 상태입니다. 여기서 $XXYYY\cdots YYYXX$와 같이 $Y$가 가운데에 몰려 있는 형태를 만들어야 단체 사진을 찍을 수 있습니다. $Y$의 개수는 $K$개 이상이어야 한다는 조건도 붙습니다. $Y$ 개수 조건은 잠시 무시하고, 표식이 모두 달렸을 때 최소 비용으로 학생을 옮기는 방법을 고민해 봅시다.

 

각각의 $X$에 대해, $X$를 $Y$ 묶음 밖으로 끄집어 낸다고 생각해 봅시다. 이때 그 $X$의 위치를 교환하는 횟수는 min(X 왼쪽에 있는 Y 개수, X 오른쪽에 있는 Y 개수)입니다. 따라서 $Y$들 중 가운데에 있는 것을 중심으로, 왼쪽에 있는 $X$들은 왼쪽으로, 오른쪽에 있는 $X$들은 오른쪽으로 움직이는 것이 최소 이동입니다.

 

하지만 이 풀이는 잘 발전되지 않습니다. 정해는 위의 $XY$ 관찰만 가져온 뒤 방향을 바꿔야 합니다. 위의 '중앙값' 관찰에 주목합시다. 학생들에게 $X$, $Y$를 적당히 매기다가 중앙값 $Y$를 매기는 순간 그 뒤 $Y$의 개수까지 고정됩니다. 따라서 중앙값에 도달하기 전의 상태와 중앙값에 도달한 후의 상태를 적당히 전이해 주면, 아직 중앙값에 도달하지 않은 경우 현재 $Y$가 몇 개 누적되었는지, 이미 중앙값에 도달한 경우 $Y$가 몇 개 더 필요한지를 두 번째 인자로 가진 DP를 이용해 해결할 수 있습니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

int n, k; ll b, c;
ll arr[5002];
ll DP[5002][5002][2];

int main(){
    scanf("%d %d %lld %lld", &n, &k, &b, &c);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);

    if(k==1){
        ll ans = 0;
        for(int i=1; i<=n; i++) ans += min(arr[i], b);
        printf("%lld", ans);
        return 0;
    }

    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) DP[i][j][0] = DP[i][j][1] = 1e18;
    DP[0][0][0] = 0;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
//            printf("%d %d: %lld %lld\n", i, j, DP[i][j][0], DP[i][j][1]);
            /// A 배정
            DP[i+1][j][0] = min(DP[i+1][j][0], DP[i][j][0] + arr[i+1]);
            DP[i+1][j][1] = min(DP[i+1][j][1], DP[i][j][1] + arr[i+1]);

            /// B 배정 - 상승
            DP[i+1][j+1][1] = min({DP[i+1][j+1][1], DP[i][j][1] - c * (i+1),
                                                    j ? INF : (DP[i][j][0] - c * (i+1))});

            /// B 배정 - 하강
            if(j){
                DP[i+1][j-1][0] = min(DP[i+1][j-1][0], DP[i][j][0] + c * (i+1));
                if(j*2 >= k){
                    DP[i+1][j-1][0] = min(DP[i+1][j-1][0], DP[i][j][1] - c * j * j + c * (i+1) + b*j*2);
                }
                if(j*2+1 >= k){
                    DP[i+1][j][0] = min(DP[i+1][j][0], DP[i][j][1] - c * j * (j+1) + b*(j+j+1));
                }
            }
        }
    }

    printf("%lld", DP[n][0][0]);
}

BOJ 18196. 정기 모임

쿼리를 하나만 생각하고, 최솟값이 $v$ 이하인지 결정하는 결정 문제를 풀어 봅시다. 최솟값이 $v$ 이하라는 말은 $S_i$와 $E_i$ 사이 번호를 가진 정점을 $v$ 이하 가중치를 가진 간선만을 사용해 모두 오고 갈 수 있다는 뜻과 같습니다. 여기까지를 보면 가중치가 작은 간선부터 차례로 union find를 이용해 양 끝 정점을 합쳐 주면서, 병렬 이분 탐색을 이용한 뭔가를 해야 할 것 같은 느낌이 듭니다. union find 도중에 $S_i$에서 $E_i$까지의 정점들이 모두 같은 연결 성분 안에 있는지를 빠르게 확인할 수 있으면 되는데, 어떻게 빠르게 확인할 수 있을까요?

 

문제를 바꿔서, $S_i = i$이고 $E_i = i+1$인 경우를 생각해 봅시다. 이 경우 $i$번 정점과 $i+1$번 정점 사이 경로의 가중치 최댓값을 찾는 문제가 되는데, 스파스 테이블을 이용하거나 HLD와 세그먼트 트리를 이용해 해결할 수 있습니다. 이때의 답을 $A_i$라고 해 봅시다. 그렇다면, 임의의 $S_i$와 $E_i$가 주어져도 답은 $\min(A_{S_i}, A_{S_i+1}, \cdots, A_{E_i-1})$임을 알 수 있습니다. 이것은 세그먼트 트리를 이용해 구하면 간단하게 해결할 수 있습니다.

 

BOJ 10126. Cards

카드를 일종의 함수로 생각해볼 수 있습니다. 카드의 양면에 적힌 수 중 작은 것을 $a_i$, 큰 것을 $b_i$라고 합시다. 입력 값을 $x$라고 할 때, 카드 함수의 출력 값은

• $x \le a_i$일 경우 $a_i$이고,
• $a_i < x \le b_i$일 경우 $b_i$이고,
• $b_i < x$일 경우 $\infty$이다.

이 함수를 맨 앞의 카드부터 맨 뒤의 카드까지 차례대로 적용해 주고, 초기 입력 값을 0으로 설정해 줬을 때 최종 출력 값이 $\infty$이면 트릭이 불가능하고, 무한대가 아니라면 트릭이 가능하다고 판정할 수 있습니다.

 

업데이트가 추가되어도 문제는 크게 어려워지지 않습니다. 이 함수는 중첩시킬 수가 있는데, 이를 세그먼트 트리를 이용해 관리해 주면 됩니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1000000000;

struct segTree{
    struct Node{
        int x, y, a, b, c;
        Node(){}
        Node(int x, int y, int a, int b, int c): x(x), y(y), a(a), b(b), c(c){}

        Node operator+(const Node &r)const{
            return Node(x, y, a<=r.x ? r.a : a<=r.y ? r.b : r.c, b<=r.x ? r.a : b<=r.y ? r.b : r.c, INF);
        }
    } tree[800002];

    void update(int i, int l, int r, int x, Node v){
        if(l==r){
            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] = tree[i*2] + tree[i*2+1];
    }

    bool query(){
        return tree[1].a < INF;
    }
} tree;

int n;
int a[200002], b[200002];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &a[i], &b[i]);
        if(a[i] > b[i]) swap(a[i], b[i]);
        tree.update(1, 1, n, i, segTree::Node(a[i], b[i], a[i], b[i], INF));
    }
    int q;
    scanf("%d", &q);
    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        swap(a[x], a[y]), swap(b[x], b[y]);
        tree.update(1, 1, n, x, segTree::Node(a[x], b[x], a[x], b[x], INF));
        tree.update(1, 1, n, y, segTree::Node(a[y], b[y], a[y], b[y], INF));
        printf("%s\n", tree.query() ? "TAK" : "NIE");
    }
}