Problem Solving Diary #26

BOJ 13874. Internet Trouble

문제

• 수직선 상에 $N$개의 마을이 있고, $K$개의 마을에 인터넷을 설치할 것이다. 하나의 마을에 인터넷을 설치하는 데는 $B$의 비용이 든다.
• $i$번째 마을에는 $A_i$개의 집이 있으며, 각 집과 인터넷을 연결하는 케이블을 설치해야 한다. 이때 $i$번 마을의 집 하나와 $j$번 마을의 인터넷을 연결하는 비용은 $|i-j|\times C$이다.
• $1 \le K \le N$인 모든 $K$에 대해, $K$개의 마을에 인터넷을 설치할 때 드는 최소 비용을 구하시오.
• $1 \le N \le 6000$

풀이

일단 문제의 생김새를 보아 DP로 푸는 것 같다. 그러나 상태 전이를 어떻게 시켜야 할지가 잘 보이지 않는다. 모든 구간 $[l, r]$을 하나의 인터넷으로 덮는 비용을 미리 계산해 둔다고 하더라도, DP 전이를 단순히 하면 $O(N^3)$이 될 것이고, 여기서 $N$을 하나 떼어야 한다. 언뜻 봤을 때는 D&C Optimization이 통할 것 같아 보이는데, $N$이 워낙 크기 때문에 $O(N^2 \log N)$이 돌아가기도 어려워 보인다.

 

Strictly $O(N^2)$에 이를 처리할 수 있는 DP 최적화 기법이 뭐가 있을까? 현재 점화식의 꼴은
$$
DP[i][cnt]=\min_{j<i} \left( DP[j][cnt-1]+cost(j+1, i) \right)
$$의 형태이다. 여기서 $cost$ 함수를 계산하는 방법이 어떻게 될까? 인터넷을 설치하는 위치는 중간값으로 두는 게 이득이다. 그런데 이 형태로는 뭔가 최적화가 잘 될 것 같지 않다. 설치 위치(피봇) 왼쪽 부분과 오른쪽 부분에 대해 비용 함수식이 다르기 때문이다. 그렇다면 아예 이 둘을 두 개의 상태로 나눠서 계산하면 어떨까?

 

이 아이디어를 조금 더 자세히 기술하자면, 구간을 총 $2K$개로 나눌 것이다. 여기서 홀수번째 구간들은 오른쪽 끝에 인터넷을 설치하고, 짝수번째 구간들은 왼쪽 끝에 인터넷을 설치한다. 구간의 끝점 처리 관련해서 조금 조심해 줘야 한다. 어떤 구간 $[l, r]$에 대해 오른쪽 끝 구간에 인터넷을 설치하는 비용을 $c_r(l, r)$, 왼쪽 끝에 설치하는 비용을 $c_l(l, r)$이라고 하자.

 

다음과 같이 점화식을 세워 보자.
$$
DP[i][cnt] = \begin{cases}
\min_{j<i} \left( DP[j][cnt-1] + c_r(j+1, i) \right) & (cnt\text{ is odd}) \
\min_{j \le i} \left( DP[j][cnt-1] + c_l(j, i) \right) & (cnt\text{ is even})
\end{cases}
$$
식의 형태가 비슷해 보이지만 $c_l$과 $c_r$은 그 형태가 훨씬 간단하기 때문에 위 점화식은 계산할 수 있는 꼴이 된다. $c_l(l, r)$은 $\sum_{l \le i \le r} iH_i - l \sum_{l \le i \le r} H_i$와 같이 계산할 수 있다. 여기서 $\sum_{1 \le i \le x} H_i = S_x$, $\sum_{1 \le i \le x} iH_i = P_x$로 미리 초기화를 해 둔다면, 저 식은 $c_l(l, r) = (P_r - P_l) - l(S_r - S_l)$로 나타낼 수 있다. 마찬가지로 $c_r(l, r) = r(S_r-S_{l-1})-(P_r-P_{l-1})$로 나타낼 수 있다.

 

이제 거의 다 왔다. $c_l(l, r)$과 $c_r(l, r)$의 식 형태를 관찰하면 CHT를 쓸 수 있음을 직감할 수 있다. $cnt$의 홀짝 여부로 케이스를 나눠 보자.

• $cnt-1$이 짝수, $cnt$가 홀수일 때:
  $$
  \begin{align}
  DP[i][cnt] &= \min_{j<i} \left( DP[j][cnt-1] + iS_i - iS_j - P_i + P_j \right) \
  &= \min_{j<i} \left(DP[j][cnt-1] + P_j - iS_j\right) + iS_i - P_i
  \end{align}
  $$
  가 되어 CHT를 적용할 수 있다. 이때 기울기 $-S_j$가 점점 감소하고 쿼리 포인트 $i$가 점점 증가하며 min 쿼리이므로, 덱을 이용해 step마다 선형에 처리 가능하다.
• $cnt-1$이 홀수, $cnt$가 짝수일 떄:
  $$
  \begin{align}
  DP[i][cnt] &= \min_{j \le i} \left( DP[j][cnt-1] + P_i - P_j - jS_i + jS_j \right) \
  &= \min_{j \le i} \left( DP[j][cnt-1] + jS_j - P_j - jS_i \right) + P_i
  \end{align}
  $$
  가 되어 CHT를 이용할 수 있다. 이때 기울기 $-j$가 점점 감소하고 쿼리 포인트 $S_i$가 점점 증가하며 min 쿼리이므로, 덱을 이용해 step마다 선형에 처리 가능하다.

따라서 전체 문제를 $O(N^2)$에 풀 수 있다.

 

CHT를 오랜만에 짜서 잘못 짰더니 많이 틀렸다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll divFloor(ll a, ll b){
    if(b<0) a=-a, b=-b;
    return a>=0 ? a/b : -((-a+b-1)/b);
}

inline ll divCeil(ll a, ll b){
    if(b<0) a=-a, b=-b;
    return divFloor(a+b-1, b);
}

struct LineContainer{
    ll a, b, st;
    LineContainer(ll a, ll b): a(a), b(b){st=0;}

    ll get(ll x){
        return a*x+b;
    }

    ll cross(LineContainer &r){
        return divCeil(r.b-b, a-r.a);
    }
};

int n; ll b, c;
ll arr[6002], S[6002], P[6002];
ll DP[3][6002];
ll ans[6002];
vector<LineContainer> vec;

void line_insert(LineContainer p){
    while((int)vec.size() >= 2 && vec.back().st >= vec.back().cross(p)){
        vec.pop_back();
    }
    if(!vec.empty()) p.st = vec.back().cross(p);
    vec.push_back(p);
}

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

    for(int i=1; i<=n; i++){
        S[i] = S[i-1] + arr[i];
        P[i] = P[i-1] + arr[i] * i;
    }

    DP[0][0] = 0;
    for(int cnt=1; cnt<=n; cnt++){
        int pnt = 0;
        vec.clear();
        for(int i=cnt; i<=n; i++){
            if(cnt>1 || i==1) line_insert(LineContainer(-S[i-1], DP[0][i-1] + P[i-1]));
            pnt = min(pnt, (int)vec.size()-1);
            while(pnt+1 < (int)vec.size() && vec[pnt+1].st <= i) pnt++;
            DP[1][i] = vec[pnt].get(i) + i * S[i] - P[i];
        }
        pnt = 0;
        vec.clear();
        for(int i=cnt; i<=n; i++){
            line_insert(LineContainer(-i, DP[1][i] + i * S[i] - P[i]));
            pnt = min(pnt, (int)vec.size()-1);
            while(pnt+1 < (int)vec.size() && vec[pnt+1].st <= S[i]) pnt++;
            DP[2][i] = vec[pnt].get(S[i]) + P[i];
        }

        assert(DP[2][n] <= 3e16);
        ans[cnt] = DP[2][n] * c + b * cnt;
        for(int i=0; i<=n; i++){
            DP[0][i] = DP[2][i];
        }
    }

    for(int i=1; i<=n; i++) printf("%lld ", ans[i]);
}

BOJ 20217. Eightgon

문제

• 2차원 격자 상에 $N$개의 점이 있다.
• $N$개의 점 여덟 개를 골라 팔각형을 만들 것이다. 이때, 모든 내각이 135도여야 하고, x축에 평행한 변이 존재해야 한다. (즉, 모든 변은 +x 방향 기준으로 0, 45, 90, 135, 180, 225, 270, 315도 회전된 방향으로 놓여 있다.)
• 위 조건을 만족하도록 팔각형을 만드는 방법의 수를 구하시오.

풀이

위 그림과 같이 여덟 개의 점에 $A \cdots H$로 이름을 붙이자.

 

먼저 각 $(A, D)$ 쌍에 대해 가능한 $(B, C)$ 쌍의 개수를 찾을 것이다. 기울기가 $1$인 모든 직선과 기울기가 $-1$인 모든 직선을 보며, 왼쪽부터 투 포인터 느낌으로 sweep해주면서 답을 찾을 수 있다. 이때 $B$의 $y$좌표가 $C$의 $y$좌표보다 더 높아야 한다는 조건을 주의하자.

 

비슷한 느낌으로 모든 $(E, H)$ 쌍에 대해 가능한 $(F, G)$ 쌍의 수를 찾을 수 있다.

 

이제 이 두 개를 합쳐야 한다. 이것 역시 가능한 모든 기울기 $0$인 직선의 쌍을 보며 문제를 해결해 주면 된다.

 

시간 복잡도가 문제라고 생각할 수 있겠지만, 두 직선 쌍을 고르고 그 안에서 두 점 쌍을 고르는 방법의 수는 $n^2$이라서 $O(n^2)$에 해결할 수 있다.

 

메모리가 512MB로, 2차원 배열을 마구 선언하다가 MLE를 당할 수 있음에 조심하자.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x, y, idx;
    dat(){}
};

int n;
dat arr[5002];
int AD[5002][5002], HE[5002][5002];
ll DP[5002][5002];
ll ans;

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

    vector<dat> v1 (arr+1, arr+n+1), vm1 (arr+1, arr+n+1), vr (arr+1, arr+n+1);
    sort(v1.begin(), v1.end(), [&](dat A, dat B){
        if(A.x-A.y != B.x-B.y) return A.x-A.y < B.x-B.y;
        return A.x<B.x;
    });
    sort(vm1.begin(), vm1.end(), [&](dat A, dat B){
        if(A.x+A.y != B.x+B.y) return A.x+A.y < B.x+B.y;
        return A.x<B.x;
    });
    sort(vr.begin(), vr.end(), [&](dat A, dat B){
        if(A.y != B.y) return A.y < B.y;
        return A.x<B.x;
    });
    vector<pair<int, int> > vr1, vrm1, vrr;
    for(int i=0; i<n; i++){
        int j = i;
        while(j+1 < n && v1[i].x-v1[i].y == v1[j+1].x-v1[j+1].y) j++;
        vr1.push_back(make_pair(i, j));
        i=j;
    }
    for(int i=0; i<n; i++){
        int j = i;
        while(j+1 < n && vm1[i].x+vm1[i].y == vm1[j+1].x+vm1[j+1].y) j++;
        vrm1.push_back(make_pair(i, j));
        i=j;
    }
    for(int i=0; i<n; i++){
        int j = i;
        while(j+1 < n && vr[i].y == vr[j+1].y) j++;
        vrr.push_back(make_pair(i, j));
        i=j;
    }

    /// A-D
    for(auto [l, r]: vr1){
        for(auto [s, e]: vrm1){
            vector<pair<int, int> > match;
            for(int i=l; i<=r; i++) for(int j=s; j<=e; j++){
                if(v1[i].x == vm1[j].x && v1[i].y > vm1[j].y) match.push_back(make_pair(i, j));
            }
            for(int i=l; i<=r; i++){
                int pnt = -1;
                for(int j=s; j<=e; j++){
                    if(pnt+1 < (int)match.size() && match[pnt+1].first < i && match[pnt+1].second < j) pnt++;
                    AD[v1[i].idx][vm1[j].idx] = pnt + 1;
                }
            }
        }
    }

    /// E-H
    for(auto [l, r]: vr1){
        for(auto [s, e]: vrm1){
            vector<pair<int, int> > match;
            for(int i=r; i>=l; i--) for(int j=e; j>=s; j--){
                if(v1[i].x == vm1[j].x && v1[i].y < vm1[j].y) match.push_back(make_pair(i, j));
            }
            for(int i=r; i>=l; i--){
                int pnt = -1;
                for(int j=e; j>=s; j--){
                    if(pnt+1 < (int)match.size() && match[pnt+1].first > i && match[pnt+1].second > j) pnt++;
                    HE[vm1[j].idx][v1[i].idx] = pnt + 1;
                }
            }
        }
    }

    /// AD + HE
    for(int pi=0; pi<(int)vrr.size(); pi++){
        int l = vrr[pi].first, r = vrr[pi].second;
        for(int pj=0; pj<pi; pj++){
            int s = vrr[pj].first, e = vrr[pj].second;
            for(int i=l; i<=r; i++){
                for(int j=s; j<=e; j++){
                    DP[i][j] = HE[vr[i].idx][vr[j].idx];
                }
            }
            for(int i=r-1; i>=l; i--) for(int j=s; j<=e; j++) DP[i][j] += DP[i+1][j];
            for(int j=e-1; j>=s; j--) for(int i=l; i<=r; i++) DP[i][j] += DP[i][j+1];
            for(int i=l; i<r; i++) for(int j=s; j<e; j++){
                ans += AD[vr[i].idx][vr[j].idx] * DP[i+1][j+1];
            }
        }
    }

//    for(int i=1; i<=n; i++){
//        printf("%d: ", i);
//        for(int j=1; j<=n; j++) printf("%lld ", AD[i][j]);
//        puts("");
//    }
//
//    for(int i=1; i<=n; i++){
//        printf("%d: ", i);
//        for(int j=1; j<=n; j++) printf("%lld ", HE[i][j]);
//        puts("");
//    }

    printf("%lld", ans);
}

BOJ 32063. Contigency Plan

문제

• $n$개의 정점을 가진 트리가 있고, 각 간선에는 $1$번부터 $m-1$번까지의 번호가 붙어 있다.
• 이 $n$개의 정점을 가지는 트리를 또 하나 만들어야 한다. 이 간선들에는 $m$번부터 $2m-2$번까지의 번호가 붙어 있고, $2m-2$개의 간선이 모두 서로 달라야 하며, $1 \le i \le m$인 모든 $i$에 대해 $i$번 간선부터 $i+m-2$번 간선까지를 모으면 트리가 되어야 한다.

풀이

자명하게도 기존 트리가 스타 그래프인 경우에는 불가능하다. 이미 한 정점과 연결된 간선이 모두 선택되었으므로, 남은 간선들은 해당 정점과 연결된 간선이 없기 때문이다.

 

그렇다면 나머지 경우에는 모두 가능할까? 임의의 정점 $p$를 하나 잡고, 이 정점을 기준으로 생각해 보자. 각 간선이 끊어짐에 따라, 정점 $p$와의 연결이 끊어지는 연결 성분이 하나 생긴다. 이때 만약 해당 연결성분에 기존에 $p$와 연결되지 않은 점이 있었다면, 간선을 $p$에서 해당 정점으로 연결해 다시 트리를 만들 수 있다. $p$를 리프 노드 비슷한 걸로 잡으면 이게 될 것 같다는 아이디어를 얻을 수 있다.

 

다음과 같은 알고리즘을 이용하자.

 

정점 $p$를 $1$번 간선에 연결되지 않은 임의의 리프 노드로 고르자. 이러한 리프 노드가 반드시 존재함이 보장된다. 또한 $p$가 연결된 유일한 점을 $q$라고 하자.

• 처음 $1$번 간선을 끊을 때, $1$번 간선의 양끝점 $a$와 $b$ 중 $q$에서 더 먼 것을 $b$라고 하자. $p$와 $b$를 연결한다.
• 이후 이런 식으로 어떤 간선이 끊어지면, $q$에서 먼 점과 $p$를 연결하는 것을 반복하자. 이것을 $p-q$ 간선이 끊어질 때까지 반복한다.
• 만약 $p-q$ 간선이 끊어질 차례가 되면, $q-b$를 연결하면 된다. 이후에는 앞의 과정을 반복한다.

그런데 이 알고리즘이 통하지 않는 경우가 딱 하나 있다. 그 조건은,

• $p-q$ 간선의 번호가 $k$번일 때, $1$번부터 $k-1$번까지의 모든 간선이 $q$번 정점과 연결되어 있다.

이 경우에는 모든 $a=q$라서, $b$들이 초기에 모두 $q$와 연결되어 있기 때문에 저 과정이 불가능하다. 하지만 저 경우 $k < l$인 어떤 $l$번 간선과 연결되어 있고 $q$와는 연결되지 않은 리프 노드가 반드시 하나는 존재해야 한다. 해당 리프 노드를 $p$번 노드로 잡으면 위와 같은 방식으로 문제를 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int ex[100002], ey[100002];
vector<pair<int, int> > link[100002];
int deg[100002], dist[100002];

void dfs(int x, int p=-1){
    for(auto [y, z]: link[x]){
        if(y==p) continue;
        dist[y] = dist[x] + 1;
        dfs(y, x);
    }
}

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

    if(count(deg+1, deg+n+1, n-1)){
        puts("-1");
        return 0;
    }

    int p = 1;
    for(; p<=n; p++){
        if(deg[p] > 1 || link[p][0].second == 1) continue;
        bool bad = 1;
        int q = link[p][0].first, k = link[p][0].second;
        for(int r=1; r<k && r<=3; r++){
            if(ex[r] != q && ey[r] != q) {bad = 0; break;}
        }
        if(bad) continue;
        else break;
    }
    int q = link[p][0].first;

    dfs(p);

    int key = -1;
    for(int i=1; i<n; i++){
        if(ex[i] != p && ey[i] != p){
            int pnt = dist[ex[i]] > dist[ey[i]] ? ex[i] : ey[i];
            printf("%d %d\n", p, pnt);

            bool linked = 0;
            for(auto [a, b]: link[pnt]) if(a==q) linked = 1;
            if(!linked) key = pnt;
        }
        else{
            assert(key != -1);
            printf("%d %d\n", q, key);
        }
    }
}