Problem Solving Diary #5

BOJ 7644. Highway Construction

트리 DP를 돌려 주며, 각 점이 경로의 LCA일 때의 답을 구해 주면 됩니다. 먼저 각 점에서 아래로 가장 먼 점까지의 거리를 전처리해 주고, 이것을 이용해 트리 DP를 할 수 있습니다. 어떤 점 $v$의 자식 $c$를 봅시다. $v$를 LCA라고 하면, 자식 최대 두 개를 골라 해당 자식을 경로에 포함시킬 수 있습니다. 경로에 포함되지 않는 자식의 경우 해당 서브트리에서 가장 먼 정점까지의 거리만이 중요하고, 경로에 포함되는 자식의 경우 트리 DP를 통해 올려준 값이 중요합니다. 해당 값들로 LCA가 $v$일 때의 답을 구한 후, 이번에는 자식을 하나만 골랐을 때의 답을 부모로 전달해 줍니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<pair<int, ll> > link[100002];
ll maxDepth[100002];
vector<ll> vec[100002];
ll ans = LLONG_MAX;

void dfs1(int x, int par=-1){
    for(auto y: link[x]){
        if(y.first==par) continue;
        dfs1(y.first, x);
        maxDepth[x] = max(maxDepth[x], maxDepth[y.first] + y.second);
        vec[x].push_back(maxDepth[y.first]+y.second);
    }
    sort(vec[x].rbegin(), vec[x].rend());
    vec[x].push_back(0);
}

ll dfs2(int x, int par=-1, ll fromUp = 0){
    vector<pair<ll, ll> > tVec;
    for(auto y: link[x]){
        if(y.first==par) continue;
        ll tUp = max(fromUp, ((int)vec[x].size() > 1 && vec[x][0] == maxDepth[y.first]+y.second) ? vec[x][1] : vec[x][0])
                             + y.second;
        tVec.push_back(make_pair(maxDepth[y.first] + y.second, dfs2(y.first, x, tUp)));
        assert(tVec.back().first >= tVec.back().second);
    }
    sort(tVec.rbegin(), tVec.rend());
    for(int i=0; i<4; i++) tVec.push_back(make_pair(0, 0));
    ans = min(ans, max({fromUp, tVec[0].second, tVec[1].second, tVec[2].first}));
    return max(tVec[0].second, tVec[1].first);
}

int main(){
    scanf("%d", &n);
    if(!n) return 0;

    ans = LLONG_MAX;
    for(int i=1; i<=n; i++){
        link[i].clear();
        maxDepth[i] = 0;
        vec[i].clear();
    }

    for(int i=1; i<n; i++){
        int x, y; ll w;
        scanf("%d %d %lld", &x, &y, &w);
        link[x].push_back(make_pair(y, w));
        link[y].push_back(make_pair(x, w));
    }
    dfs1(1);
    dfs2(1);
    printf("%lld\n", ans);
    main();
}

 

BOJ 3878. 점 분리

빨간색 점들의 볼록 껍질과 파란색 점들의 볼록 껍질을 구한 후, 이들 사이에 교점이 없으면 됩니다. 선분 교차를 통해 변이 겹치는 지 확인한 후, 한 볼록 껍질이 다른 쪽 안에 완전히 포함되는 경우도 처리해 줄 수 있습니다. 다만 모든 기하 문제가 그렇듯이 예외가 정말 많이 나올 수 있는데, 그런 예외에 걸리지 않도록 꼼꼼히 코딩해야 합니다.

 

BOJ 11987. Train Fare

몇 가지 간단한 관찰을 통해 풀이를 이끌어 내야 하는 류의 문제입니다. 아래 사실을 관찰합시다.

• 초기 상태보다 최단거리가 늘어난 정점을 outdated vertex라고 하자. 간선 가중치를 늘리기만 해서 최단경로를 줄일 수는 없으므로, 한 번 outdated vertex가 된 정점은 영원히 outdated vertex가 된다.
• 초기에 정점 1에서 시작한 bfs를 돌려서, 각 간선 $e$에 대해 $e$의 양끝점의 거리가 같은 경우 간선은 의미 없으므로 제거해 줘도 된다. 간선의 양끝점의 거리가 다른 경우(이 경우 정확히 1 차이나게 된다), 정점 1에서 더 가까운 쪽을 시작점, 더 먼 쪽을 끝점으로 하는 방향 간선으로 바꿀 수 있다.
• 이렇게 그래프를 방향 그래프로 바꾼 뒤, 간선 $e$에 대해 해당 간선을 이용하는 모든 (최단)경로의 길이가 처음보다 커져 있다면 해당 간선을 outdated edge라고 부르자.

이제 outdated vertex와 outdated edge 간의 관계를 살펴 봅시다.

• 각 쿼리는 edge 하나를 잡아 (이미 outdated되지 않았다면) outdated edge로 만드는 것과 같다.
• 만약 어떤 점으로 들어오는 모든 간선이 outdated되어 있다면 해당 정점이 outdated vertex가 된다.
• outdated vertex에서 나가는 모든 간선은 자동으로 outdated edge가 된다.

이제 그래프 정점 indegree를 가지고 큐로 잘 다루는 흔한 유형이 되었습니다. 굳이 구현 방법을 설명하자면 위상 정렬 비슷한 느낌으로 하시면 됩니다.

 

BOJ 21341. Endgame

Alice가 이길 수 있는 지 판별하는 건 쉽습니다. 첫 움직임을 고정한 뒤, 두 번째 움직임으로 가능한 것이 존재하는지만 판별해 주면 됩니다. $O(N \log N)$ 정도에 쉽게 처리할 수 있습니다.

 

이제 Alice가 이길 수 없을 때를 계산합시다. Alice의 위치를 고정하고 나면, Bob이 승리할 수 있는지를 계산하는 것은 위와 똑같은 방법으로 가능합니다. 하지만 고정할 위치가 $O(N^2)$개인데, 한 번의 판별에 $O(N \log N)$ 시간이 들기 때문에 모든 위치를 시도해 볼 수는 없습니다.

 

여기서 아래 사실을 관찰해야 합니다.

• 만약 Alice가 무승부를 이끌어낼 수 있다면, Alice가 도달할 수 있는 칸의 비율이 \frac{1}{8}$ 이상이다.

증명은 간단한 카운팅입니다. $N$이 작을 때 저 비율이 굉장히 작아진다는 사실을 알 수 있고, $N=3$일 때의 최악의 케이스를 계산하면 확률이 저렇게 나옵니다. 그래서 랜덤하게 아무 칸이나 잡아서 판별하는 과정을 충분히 많이 하면 답을 찾을 수 있습니다. 저 같은 경우에는 60번 정도 아무 칸이나 잡은 뒤, Alice가 무승부를 이끌어낼 수 없다면 불가능으로 판정했습니다.

 

BOJ 10124. Couriers

구간에서 과반을 차지하는 원소가 있는지 판별하는 문제입니다. 과반이라고 하면 보통 랜덤을 이용한 접근을 먼저 생각하시는 분이 많은데, 과반을 쉽고 간단하게 판별할 수 있는 결정론적인 알고리즘인 보이어-무어 알고리즘(Boyer-Moore Majority Vote)이 존재합니다. 이 알고리즘은 이미 다른 분들의 블로그에서 잘 설명되어 있습니다.

 

보이어-무어 알고리즘을 알고 있다면 수열에서 세그먼트 트리를 구축하고, 각 노드가 담당하는 구간에 대한 보이어-무어 알고리즘의 결과값을 저장해 둡니다. 그리고 구간 쿼리를 날려서 최빈값이 될 수 있는 후보 값 하나를 구한 뒤, 그 값이 실제로 과반을 차지하는지 판별하면 됩니다. 이 판별은 단순한 전처리에 이분 탐색(lower_bound)를 통해 할 수 있습니다.

 

BOJ 1848. 동굴 탐험

정말 아무 생각을 거치지 않고 나오는 풀이는 다음과 같습니다.

• 시작점에서 다익스트라 알고리즘을 돌려, 다시 1번 정점으로 돌아가는 최단 거리를 구한다.

위 알고리즘이 동작하지 않는 이유는 같은 도로를 왕복한 거리가 답이 될 수 있기 때문입니다. 따라서 이런 경우가 없도록 처리를 해 주어야 합니다.

 

문제는 1번 정점을 지나는 사이클의 최단 길이를 구하는 것입니다. 사이클에서 1번 정점으로 돌아오기 직전에 방문하는 점의 번호를 $x$라고 고정합시다. 이때 현재까지의 가정과 조건을 만족하는 사이클의 최단 거리는 ($1$번 정점에서 $x$번 정점까지 거리 2 이상인 경로 중 최단 경로의 길이) + ($x \rightarrow 1$ 간선의 길이)가 됩니다. 왼쪽 항을 어떻게 구할까요?

 

다익스트라 알고리즘을 돌리는데, (현재 정점, 거리) pair에 하나의 원소를 더 저장합시다. 바로 처음 1번 정점에서 출발한 다음 막 들른 정점의 번호 $p$입니다. 또한 통상적인 다익스트라 알고리즘은 각 정점을 최대 한 번만 방문하는데, 여기서는 두 번까지 방문할 수 있도록 허용합시다. 이때 두 번 방문했을 때의 $p$값이 서로 달라야 합니다. (즉, 이미 이 정점을 방문한 상태에서 이전과 같은 $p$값을 가진 데이터가 들어온다면 그냥 무시해 주면 됩니다.)

 

다익스트라 알고리즘 과정에서 1번 정점과 인접한 정점 $x$에 도달했다면, 먼저 $p \neq x$인지 확인합시다. $p = x$라면 이미 사용한 간선을 왕복하는 것이기 때문에 안 됩니다. $p \neq x$라면 이 사이클은 답의 후보가 될 수 있습니다. 이렇게 1번 정점과 인접한 모든 정점에 대해서 답 후보를 찾아준 뒤 그 중 가장 거리가 짧은 것을 구하면 됩니다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x; ll y; int p;
    dat(){}
    dat(int x, ll y, int p): x(x), y(y), p(p){}

    bool operator<(const dat &r)const{
        return y>r.y;
    }
};

int n, m;
vector<pair<int, ll> > link[10002];
priority_queue<dat> pq;
vector<dat> vec[10002];
ll ans = LLONG_MAX;

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

    for(auto p: link[1]){
        pq.push(dat(p.first, p.second, p.first));
    }
    while(!pq.empty()){
        dat tmp = pq.top(); pq.pop();
        int x = tmp.x;
        if((int)vec[x].size() >= 2 || ((int)vec[x].size() == 1 && vec[x][0].p == tmp.p)) continue;
        vec[x].push_back(tmp);
        for(auto y: link[x]){
            if(y.first == 1){
                if(x != tmp.p) ans = min(ans, tmp.y + y.second);
                continue;
            }
            pq.push(dat(y.first, tmp.y+y.second, tmp.p));
        }
    }
    printf("%lld", ans);
}