[BOJ] Journey to TST set4

저번에 이어서 Journey to TST set4를 풀려고 한다.

 

https://psforhobby.tistory.com/60

[BOJ] Journey to TST set3

 

https://dsstar.tistory.com/53

Journey to TST 문제 셋 공유

02/10의 문제 셋이고, 이번에도 내가 푼 순서대로 리뷰하려고 한다. 훈련도 있었고 마지막으로 푼 러시아어 문제의 지문을 제대로 이해하지 못해 덮어놨다가 다시 풀어 꽤 오래 걸렸다. 사실 문제 잘못 이해해서 걸린 시간 빼면 3일정도밖에 안 걸린 것 같긴 하다.

여담으로 (스포일러)4문제 중 3문제에서 DSU가 사용되서 의도된 것인가 싶었다.

 

1. Subway(15867)

https://www.acmicpc.net/problem/15867

제일 먼저 풀었는데 난이도가 높은 문제라 조금 당황했다. 18889번 문제와 비슷한 문제로 보이나 내 생각엔 이 문제가 저 문제의 하위호환 문제이지 절대 동일한 문제는 아니라고 생각한다. 이 문제는 간선을 하나씩 바꿔가며 두 번째 트리로 만들어야 하지만 18889번 문제는 첫 번째 트리의 각 간선에 두 번째 트리의 간선을 일대일 대응시켜야 한다. 이 사소해 보이지만 사소하지 않은 차이 때문에 이 문제는 훨씬 쉽다고 생각한다.

 

문제

정점이 $N$개인 두 트리가 주어진다. 하나의 간선을 끊고 새로운 간선을 만들되 트리 형태를 유지하도록 하는 수행을 반복하여 첫 번째 트리를 두 번째 트리로 바꾸려고 한다. 수행 횟수의 최소와 그 방법을 구하시오. 

$1 \leq N \leq 10^5$

 

풀이

우선 자명하게 두 트리에서 겹치는 간선은 바꿀 필요가 없으므로 제외하고 생각하자. 각 간선을 끊었을 때 두 번째 트리에서 트리 형태를 유지하도록 하는 간선을 찾을 수 있다면 두 트리에서 서로 다른 간선 개수만큼 간선 바꾸기 시행을 하여 첫 번째 트리를 두 번째 트리로 바꿀 수 있을 것이다. 

 

첫 번째 트리에 존재하지만 두 번째 트리에 존재하지 않는 간선들을 생각해보자. 해당 간선을 끊으면 두 개의 컴포넌트가 생기는데, 두 번째 트리에서 두 컴포넌트를 연결하는 간선은 항상 존재한다. 존재하지 않을 경우 연결 그래프가 아니기 때문에 모순이다. 따라서 위 가정은 참이 되고, 계속해서 간선을 하나씩 바꿔나간다고 생각하면 결국 두 트리의 서로 다른 간선 개수가 답이 됨을 알 수 있다.

 

이제 이 변환 과정을 찾아야 한다. 우선 초기에 첫 번째 트리로 트리를 구성하고, 두 번째 트리의 간선 중 아직 현재 트리에 존재하지 않는 간선을 하나씩 생성할 것이다. 해당 간선이 연결하는 두 정점을 잇는 경로상의 간선을 하나 자르고 두 정점을 하나로 합치는 과정을 반복하면 답을 구할 수 있음을 알 수 있다. 위 과정에서 문제가 생기려면 새로운 간선이 연결하는 두 정점이 이미 하나로 합쳐져 있어야 하는데, 이런 경우 두 번째 트리에 사이클이 있음을 의미하므로 모순이 됨을 알 수 있다. 

 

위 과정은 Disjoint Set & Union과 트리 깊이를 이용해 $O(N\log N)$에 쉽게 구현 가능하다. 나는 Disjoint Set 상에서 루트가 되는 점을 고를 수 있도록 하고 원래 트리에서 깊이가 깊은 정점을 낮은 정점에 합치는 식으로 구현했다. 두 정점 중 원래 깊이가 깊은 정점의 부모와 연결된 간선이 두 정점을 잇는 경로 상에 없는 경우는 원래 깊이가 깊은 정점이 lca인 경우인데 잘 생각해보면 이것이 불가능함을 알 수 있다. 

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;

struct DSU {
    vector <int> p;
    DSU(int n) {
        p.resize(n);
        for(int i = 0; i < n; i++) {
            p[i] = i;
        }
    }

    int find(int x) {
        return x == p[x] ? x : p[x] = find(p[x]);
    }

    void uni(int x, int y) {
        x = find(x), y = find(y);
        p[y] = x;
    }
};

void dfs(int x, int pa, vector <vector <int>> &g, vector <int> &p, vector <int> &dep) {
    dep[x] = dep[pa] + 1;
    p[x] = pa;
    for(int i : g[x]) {
        if(i == pa) continue;
        dfs(i, x, g, p, dep);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;
    vector <vector <int>> g(n);
    set <pii> st;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        if(u > v) swap(u, v);
        g[u].eb(v), g[v].eb(u);
    }
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        if(u > v) swap(u, v);
        st.em(u, v);
    }

    vector <int> dep(n), p(n);
    dfs(0, -1, g, p, dep);

    DSU S(n);
    for(int i = 0; i < n; i++) {
        for(int j : g[i]) {
            if(i > j) continue;
            if(st.find(pii(i, j)) != st.end()) {
                if(p[i] == j) S.uni(j, i);
                else S.uni(i, j);
                st.erase(pii(i, j));
            }
        }
    }
    
    cout << st.size() << '\n';
    for(auto [u, v] : st) {
        int pu = S.find(u), pv = S.find(v);
        if(dep[pu] < dep[pv]) swap(pu, pv), swap(u, v);
        cout << pu << ' ' << p[pu] << ' ' << u << ' ' << v << '\n';
        S.uni(v, u);
    }
}

 

2. Phone Call(18963)

https://www.acmicpc.net/problem/18963

MST 향기가 진하게 나는 문제고, 실제로 비슷한 철학을 이용하면 쉽게 풀 수 있다.

 

문제

크기 $N$의 트리가 주어진다. $M$개의 라인 네트워크가 있는데, $u$와 $v$를 잇는 경로 상의 정점 집합을 $S(u, v)$라 할 때 $i$번째 네트워크는 $S(a_i, b_i) \cup S(c_i, d_i)$의 두 정점을 비용 $w_i$에 연결할 수 있게 해준다. (횟수 제한 X)

1번 정점과 최대로 연결할 수 있는 점의 개수와 그렇게 연결하기 위한 최소 비용을 구하시오.

 

풀이

결국 간선이 꽤 많은 상태에서 MST 비슷하게 하기만 하면 되는 문제이다. 각 라인 네트워크를 $w_i$가 증가하는 순으로 정렬하고 생각해보자.

 

사실 그냥 $i$번째 네트워크는 $(a_i, b_i) \cup S(c_i, d_i)$의 정점들 사이의 비용 $w_i$인 간선 묶음이라고 생각해도 좋다. 따라서 이 정점들 중 이미 네트워크로 연결되지 않은 정점들끼리만 연결하면 된다. 

 

전체 비용이 아닌 1번 정점과 연결된 스패닝 트리의 비용을 구해야 하므로 Disjoint Set에 해당 집합의 연결비용도 같이 저장할 수 있도록 하자.

 

$a_i$와 $b_i$를 잇는 경로와 $c_i$와 $d_i$를 잇는 경로를 따라서 모두 합쳐주고 그 후 $a_i$와 $c_i$를 합쳐도 충분하다. 여기서 $S(a_i, b_i)$를 트리 상에서 하나의 정점으로 합치고 $S(c_i, d_i)$를 트리 상에서 하나의 정점으로 합치면 $O((N+M)\log N))$에 해결됨을 알 수 있다. 이렇게 해도 트리 구조는 망가지지 않기 때문에 두 정점을 잇는 경로를 항상 잘 찾을 수 있고, 합쳐지는 횟수가 많아봤자 총 $O(N+M)$번이 되므로 시간 안에 해결된다. 답을 구하는 Disjoint Set 상에서 1번 정점이 속한 집합의 크기와 그 연결비용을 출력해주면 된다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;

struct DSU {
    vector <int> p, sz;
    vector <ll> val;
    DSU(int n) {
        p.resize(n+1);
        sz.resize(n+1);
        val.resize(n+1);
        for(int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
    }
    
    int find(int x) {
        return x == p[x] ? x : p[x] = find(p[x]);
    }
    
    void uni(int x, int y, int w = 0) {
        x = find(x), y = find(y);
        if(x == y) return;
        p[y] = x;
        val[x] += val[y] + w;
        sz[x] += sz[y];
    }
};

struct Call {
    int a, b, c, d, w;
};

void dfs(int x, int pa, vector <vector <int>> &g, vector <int> &p, vector <int> &dep) {
    p[x] = pa;
    dep[x] = dep[pa] + 1;
    for(int i : g[x]) {
        if(i == pa) continue;
        dfs(i, x, g, p, dep);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector <vector <int>> g(n+1);
    vector <int> dep(n+1), p(n+1);
    vector <Call> C(m);
    
    for(int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].eb(v), g[v].eb(u);
    }
    for(int i = 0; i < m; i++) {
        cin >> C[i].a >> C[i].b >> C[i].c >> C[i].d >> C[i].w;
    }
    
    dfs(1, 0, g, p, dep);
    sort(all(C), [](Call x, Call y) {
        return x.w < y.w;
    });
    
    DSU S1(n), S2(n);
    for(auto [a, b, c, d, w] : C) {
        a = S1.find(a), b = S1.find(b), c = S1.find(c), d = S1.find(d);
        auto merge = [&](int x, int y) {
            while(x != y) {
                if(dep[x] < dep[y]) swap(x, y);
                S1.uni(p[x], x);
                S2.uni(p[x], x, w);
                x = S1.find(p[x]);
            }
        };
        merge(a, b), merge(c, d);
        S2.uni(a, c, w);
    }
    cout << S2.sz[S2.find(1)] << ' ' << S2.val[S2.find(1)];
}

 

3. Hoof and Brain(24972)

https://www.acmicpc.net/problem/24972

진짜 맞왜틀하기 너무 쉬운 문제다. 아이디어는 간단하다.

 

문제

정점 $N$개, 간선 $M$개의 방향 그래프와 두 정점이 주어졌을 때 다음 게임을 생각하자.

1. 한 사람(Brain)이 두 정점 중 하나를 고른다

2. 나머지 한 사람(Hoof)은 두 정점 중 하나를 원하는 간선을 따라 이동시킨다. 이 때 두 정점은 같은 정점일 수 없다.

어느 순간 Hoof가 유효한 행동이 불가능하다면 Brain이 승리한다. 만약 그렇지 않고 무한히 이어나갈 수 있다면 Hoof가 승리한다. $Q$개의 쿼리로 초기 두 정점이 주어질 때 승리할 사람을 구하시오.

$2 \leq N \leq 10^5$, $1 \leq M \leq 2 \times 10^5$, $1 \leq Q \leq 10^5$

 

풀이

우선 아무 간선을 따라 이동해도 더 이상 나가는 간선이 없는 정점에 도달하게 되는 정점들을 생각하자. 이러한 정점 중 하나라도 초기 게임에 포함되어 있다면 자명하게 Brain이 승리한다. 이런 경우를 역간선의 위상정렬을 통해 배제하자.

이제 Brain이 승리하는 경우를 생각해보면 한 정점을 이동시키려 할 때 이동시킬 수 있는 곳이 다른 한 정점이 있는 곳 뿐일때만이다. 즉 한 정점의 Outdegree가 1이고 그 유일한 간선의 끝 정점에 다른 한 정점이 있는 경우이다. 그리고 잘 생각해보면 사실 이러한 정점 쌍은 하나의 정점으로 생각해도 좋다는 것을 발견할 수 있다. Outdegree가 1이라는 의미는 그 정점에서 출발한다면 다음 정점이 강제된다는 것을 의미하기 때문이다.

 

따라서 그래프에서 Outdegree가 1인 정점을 찾아 그 유일한 간선의 끝 정점과 합치는 일을 가능한만큼 반복한 뒤 각 쿼리에서 두 점이 같은 점인지만 판별하면 됨을 알 수 있다. 합칠 때 간선들도 이동을 시켜줘야 되서 큰 집합에 작은 집합을 합치는 테크닉을 사용하여야 한다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;

struct DSU {
    vector <int> p;
    DSU(int n) {
        p.resize(n+1);
        for(int i = 1; i <= n; i++) p[i] = i;
    }
    
    int find(int x) {return x == p[x] ? x : p[x] = find(p[x]); }
    
    void uni(int x, int y) {
        x = find(x), y = find(y);
        p[x] = y;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector <set <int>> g(n+1), rg(n+1);
    vector <bool> chk(n+1);
    DSU S(n);
    for(int u, v, i = 0; i < m; i++) {
        cin >> u >> v;
        g[u].em(v);
        rg[v].em(u);
    }
    queue <int> Q;
    for(int i = 1; i <= n; i++) {
        if(g[i].empty()) Q.em(i);
    }
    while(!Q.empty()) {
        int x = Q.front();
        Q.pop();
        chk[x] = true;
        for(int i : rg[x]) {
            g[i].erase(x);
            if(g[i].empty()) Q.em(i);
        }
    }
    
    for(int i = 1; i <= n; i++) {
        if(chk[i]) continue;
        if(g[i].size() == 1) {
            Q.em(i);
            rg[*g[i].begin()].erase(i);
        }
    }
    while(!Q.empty()) {
        int x = Q.front();
        Q.pop();
        int y = *g[x].begin();
        x = S.find(x), y = S.find(y);
        if(x == y) continue;
        if(rg[x].size() > rg[y].size()) swap(x, y);
        for(int i : rg[x]) {
            g[i].erase(x);
            g[i].em(y);
            if(g[i].size() == 1) {
                rg[y].erase(i);
                Q.em(i);
            }
            else rg[y].em(i);
        }
        S.uni(x, y);
    }
    
    int q;
    cin >> q;
    while(q--) {
        int x, y;
        cin >> x >> y;
        if(chk[x] || chk[y] || S.find(x) == S.find(y)) cout << "B";
        else cout << "H";
    }
}

 

4. Классные парты

https://www.acmicpc.net/problem/19911

번역도 안 된 러시아어 문제를 넣다니 악마다. 근데 별개로 문제가 교육적이긴 하다. 처음에는 각 학생 그룹마다 책상을 다르게 구매할 수 있는 줄 알고 왜이렇게 어렵지 하면서 풀었는데 알고 보니까 책상 구매는 똑같이 해야 했다.

 

문제

$K$개의 2인용 책상 목록이 주어진다. $2N$명으로 구성된 학생그룹 $M$개가 주어지는데, 2인용 책상 $N$개를 적당히 구매하여 전체 학생이 느끼는 불편도의 합을 최소화할 것이다. 키가 $h$인 학생이 $i$번째 책상에 대해 느끼는 불편도는 책상이 허용하는 키 범위 $[L_i, R_i]$에서 $h$가 떨어진 정도이다.

$1 \leq NM \leq 2 \times 10^5$, $2 \leq K \leq 2 \times 10^5$

 

풀이

만약 $L_i \leq L_j$이고 $R_j \leq R_i$라면 $j$번째 책상은 구매할 이유가 없다. 따라서 책상을 $L_i$가 증가하는 순으로 정렬한 뒤 $R_i$가 증가하도록 책상을 뽑아 가능한 책상 목록을 재구성할 수 있다.

 

이제 책상 $N$개를 골라 $L_i$가 단조증가하는 순으로 늘어놓았다고 가정해보자. 이 상황에서 $2N$명 학생의 총 불편도를 최소화하는 방법은 학생들을 키 순으로 정렬하여 각 책상에 순서대로 앉게 시키는 경우임을 알 수 있다. (엄밀한 증명은 조금 어려운 듯 하지만 최적해 하나 가정하고 처음으로 다른 순간 적절히 바꾸는 식으로 생각하면 될 것 같다.) 이 관찰을 거쳤다면 각 그룹의 $2N$명의 학생을 짝지을 수 있고, 이 학생쌍들도 자연스럽게 순서가 정해진다. 각 그룹에서 $i$번째 학생쌍은 모두 같은 책상을 이용하게 되므로 모든 책상을 보면서 각 그룹에서 $i$번째인 학생쌍들의 불편도 합을 최소로 하는 책상을 구해준다면 $O(NMK)$에 해결 가능해 꽤나 높은 점수를 얻을 수 있다.

 

이제 추가로 각 학생쌍(들)이 최적해에서 고르는 책상의 $L_i$가 단조증가함을 이용해보자. 그냥 dnc optimization 예시급 문제임을 알 수 있다. $O(MN\log K)$가 된다.

 

마지막으로 $i$번째 학생 쌍에 대해 불편도 합을 구하는 것을 누적합과 이분탐색으로 최적화 가능함을 쉽게 발견할 수 있다. 최종적으로 $O(N\log M \log K)$에 해결 가능하다.

 

첫 그리디 풀이를 내면 이후 최적화는 어렵지 않은 듯 하다. 참고로 난 문제를 잘못 이해하여 그리디 풀이 잘 내놓고 맞왜틀을 했다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;

ll dnc(int s, int e, int l, int r, vector <vector <int>> &h, 
                    vector <vector <ll>> &sum, vector <pii> &v) {
    int m = s + e >> 1;
    ll mn = LINF;
    int idx = l;
    for(int i = l; i <= r; i++) {
        ll val = 0;
        
        int tidx;
        tidx = lower_bound(all(h[m]), v[i].fi) - h[m].begin() - 1;
        if(tidx >= 0) val += (ll)(tidx + 1) * v[i].fi - sum[m][tidx];
        tidx = upper_bound(all(h[m]), v[i].se) - h[m].begin() - 1;
        if(tidx >= 0) {
            val += sum[m].back() - sum[m][tidx];
            val -= (ll)(sum[m].size() - tidx - 1) * v[i].se;
        }
        else {
            val += sum[m].back();
            val -= (ll)(sum[m].size()) * v[i].se;
        }
        
        if(mn >= val) {
            idx = i;
            mn = val;
        }
    }
    if(s == e) return mn;
    ll ret = mn;
    if(s < m) ret += dnc(s, m - 1, l, idx, h, sum, v);
    if(m < e) ret += dnc(m + 1, e, idx, r, h, sum, v);
    return ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    int m, n, k;
    cin >> m >> n >> k;
    vector <pii> tv(k), v;
    for(int i = 0; i < k; i++) {
        cin >> tv[i].fi >> tv[i].se;
    }
    sort(all(tv), [](pii a, pii b) {
        if(a.fi == b.fi) return a.se > b.se;
        return a.fi < b.fi;
    });
    int pre = 0;
    for(pii &x : tv) {
        if(pre >= x.se) continue;
        pre = x.se;
        v.eb(x);
    }
    
    vector <vector <int>> h(n);
    vector <vector <ll>> s(n);
    vector <int> temp(2*n);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < 2 * n; j++) {
            cin >> temp[j];
        }
        sort(all(temp));
        for(int j = 0; j < n; j++) {
            h[j].eb(temp[2*j]);
            h[j].eb(temp[2*j+1]);
        }
    }
    for(int i = 0; i < n; i++) {
        sort(all(h[i]));
        s[i].eb(h[i][0]);
        for(int j = 1; j < 2 * m; j++) {
            s[i].eb(s[i].back() + h[i][j]);
        }
    }
    cout << dnc(0, n-1, 0, v.size()-1, h, s, v);
}