[2019.12.31] JOI spring camp 2018/2019 Day 3

https://oj.uz/problems/source/378

 

컨디션 난조인지, 못하는건지 직접 푼 게 하나도 없다... 그나마 1번은 거의 다 접근했으나 계속 꽉 막힌 생각 때문에 최종 답에는 도달하지 못했다.

1. Designated city

문제를 다시 설명하자면, 정점 몇 개를 골라 모든 정점에 대해 그 정점으로 가는 경로 상의 단방향 길을 다 만들 때 나머지 남은 비용을 최소화해야된다. 만약 한 개의 정점만 고른다면 그 정점에서 다른 정점들로 뻗어나가는 비용만 계산하면 되고, 여러 개일 때는 조금 복잡해 보인다.

 

우선 E=1일 때를 풀자.(이건 나도 직접 풀었다.) 트리에서 임의로 한 정점을 루트로 잡고 어떤 정점을 지정했을 때 비용을 생각해보자. 그 정점이 루트 정점이면 루트에서 내려가는 방향의 간선들의 가중치 합이다. 그렇지 않은 경우 바뀌는 비용은 단지 루트 정점에서 해당 정점으로 가는 경로 상의 정점들 뿐이다. dfs하며 루트에서 해당 정점까지 내려가는 비용과 그 정점에서 루트까지 올라가는 비용을 구한 뒤 적당히 더하고 빼주면 모든 정점에 대해 O(n)만에 구할 수 있다. 이들 중 최댓값이 E=1일 때의 답이다.

 

E>=2일 때는 조금 사고의 전환이 필요하다. 우선 알아두어야 할 사실은 리프 정점만을 고르는 것이 이득이라는 것이다. 때문에 나는 처음에 리프노드까지의 경로를 하나씩 고르는 것으로 그리디하게(Subway처럼) 답을 구하려 했지만 이전의 선택이 나중의 선택에 영향을 주기 때문에 이는 실패한 생각임을 알 수 있었다. 루트가 정해져있지 않기 때문이다. 여기서 조금 사고의 전환이 필요한데, 우선 이 문제에서는 리프 노드를 적게 고를수록 비용이 증가한다. 즉, 리프 노드를 많이 골랐을 때부터 답을 구해야 한다. 때문에 이 문제를 리프노드 수를 하나씩 줄이는데 그 줄이는 비용의 최소를 계속 더하는 문제로 생각할 수 있다.

 

우선순위 큐에 리프 정점을 모두 넣고 그 정점과 연결된 정점과의 비용이 최소인 순서로 뽑는다. 만약 뽑아서 정점을 제거했는데 리프 정점 수가 줄어들지 않았으면, 즉 리프 노드에서 연결된 선을 모두 제거하지 않았을 경우 해당 리프를 제거하는 비용에 현재 리프를 제거하는 비용을 더해 새로 pq에 넣는다. 만약 그렇지 않을 경우 pq에 들어있는 리프 노드 수가 변화하고, 이는 그 수만큼 정점을 골랐을 때의 최소 비용임을 알 수 있다.(방금 꺼낸 리프 노드 제거하는데 드는 비용이 이전 비용에 추가된다) 때문에 이 과정을 총 n log n만에 수행하면 모든 2<=E<=N에 대하여 답을 구할 수 있다.

 

코드

#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 MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

vector <pair <int, pll> > g[2*MAX];
ll d[2*MAX], sum, ans[2*MAX], up[2*MAX];
bool chk[2*MAX];
int deg[2*MAX];

void dfs(int x, int pa) {
    for(auto i : g[x]) {
        if(i.fi == pa) continue;
        d[i.fi] = d[x] + i.se.fi;
        up[i.fi] = up[x] + i.se.se;
        sum += i.se.fi;
        dfs(i.fi, x);
    }
}

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

    int n;
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v; ll c, d;
        cin >> u >> v >> c >> d;
        g[u].eb(v, make_pair(c, d)), g[v].eb(u, make_pair(d, c));
        deg[u]++, deg[v]++;
    }
    priority_queue <pll, vector <pll>, greater <pll> > pq;
    for(int i = 1; i <= n; i++) {
        if(deg[i] == 1) pq.em(g[i][0].se.se, i);
    }
    while(pq.size() > 2) {
        pll cur = pq.top();
        pq.pop();
        chk[cur.se] = true;
        int u;
        for(auto i : g[cur.se]) {
            if(!chk[i.fi]) {
                u = i.fi;
                break;
            }
        }
        deg[u]--;
        if(deg[u] == 1) {
            for(auto i : g[u]) {
                if(!chk[i.fi]) {
                    pq.em(cur.fi + i.se.se, u);
                    break;
                }
            }
            continue;
        }
        ans[pq.size()] = ans[pq.size()+1] + cur.fi;
    }
    dfs(1, 0);
    ans[1] = LINF;
    for(int i = 1; i <= n; i++) {
        ans[1] = min(ans[1], sum - d[i] + up[i]);
    }
    
    int q;
    cin >> q;
    while(q--) {
        int u; cin >> u;
        cout << ans[u] << '\n';
    }
}

 

2. Lamp

이 문제 또한 혼자 해결하지 못했다. 그리 어려운 문제가 아닌 것 같음에도 불구하고... 이런 류의 dp는 풀어보지 않으면 어려운 것 같다. dp로의 접근은 거의 비슷하게 했으나 내가 착각한 것이 있었다. 우선 나는 1) 어떤 램프에 아무 행동도 하지 않았을 경우의 비용도 구해야 한다고 생각했다. 2) 3번 수행과 1, 2번 수행의 순서를 적절히 바꿔도 상관이 없다는 것은 알았지만, 거기에 나는 한 램프에 최대 한 번의 수행만을 하게 된다고 착각하였다. 그래서 dp를 짰는데 예제컷 당하고 너무 슬펐다...

조금 더 알아보니 1) 어차피 해당 램프에 0 또는 1의 수행을 진행하였다고 생각할 수 있으므로 아무 수행도 하지 않은 경우는 고려할 필요가 없다. (그 수행의 비용을 0으로 생각?) 2) 최대 두 번의 수행이 일어날 수 있다.

이를 잘 고려해서 dp를 하면 되긴 하던데, 풀이가 참 다양한 것 같다. 아직 답에 대한 이해가 부족한 것 같다...

 

3. Bitaro, who leaps through time

이 문제는 아예 코딩조차 하지 않았다. 우선 1) 단방향만 고려해도 반대 방향은 반대 방향 문제로 풀면 된다. 2) 모든 시간을 T[i] - i로 바꾸면 i, T 좌표평면에서 축에 수직한 방향으로만 가는 것으로 경로를 표현할 수 있다. 는 것을 관찰했다. 특히 2)를 이용하면 i->j로 가는 수행을 세그먼트 트리 등의 구간 질의를 통해 해결할 수 있음을 알았다. 하지만 거기까지였다. 어떻게 해야 할지 도통 감이 잡히지 않았다. 공식 사이트 풀이 ppt를 대충 보니 두 개의 시간 구간을 합칠 수 있다 하더라. 세그먼트 트리로 잘 합쳐서 잘 구하면 답이 나온다고 한다. 합치는 방법은 조금 더 공부를 해야할 것 같다.