2023 1주차 멘토링 일지

CEOI 2017 Day 1 셋을 돌아 245 (100 100 45)점을 받았다. 비교적 쉬운 셋이었는데 1번에서 뇌절하고 2시간 반 정도를 날려서 3번을 생각할 충분한 시간을 확보하지 못했다. 

 

[BOJ 15247] B. Sure Bet (0:16)

처음 7분 동안 문제를 읽었다. 이후 B번이 가장 쉬워 보여서 접근했다. $N=1000$으로 잘못 보고 제곱을 짜 60점을 받았는데, 제곱과 $O(N \log N)$ 난이도가 크게 다르지 않아 바로 100점을 받았다.

 

0에 베팅할 개수를 $A$개, 1에 베팅할 개수를 $B$개라고 하자. $A$와 $B$가 정해지면, 해당하는 베팅 중 가장 큰 것들만을 고르는 것이 이득이다. 따라서 최적의 $A$와 $B$를 정해야 한다. 0이 나왔을 때 버는 돈을 $X_A$, 1이 나왔을 때 버는 돈을 $X_B$라고 했을 때, 이익은 $\min(X_A,X_B)-(A+B)$이다. 그런데 $X_A$와 $X_B$는 모두 $A$와 $B$에 대해 증가하는 함수이므로, $A+B$가 일정할 때, $A$가 증가함에 따라 $\min(X_A, X_B)$의 그래프를 그리면 이 값은 위로 볼록한 형태의 함수가 된다. 따라서 최댓값을 삼분 탐색으로 찾을 수 있고 문제를 $O(N \log N)$에 해결할 수 있다.

[BOJ 15246] A. One-Way Streets (4:00)

풀이는 빠르게 찾았는데 여러 이유로 뇌절을 많이 해서 푸는 데 5시간 중 대부분을 썼다. 기본적인 풀이는 BCC를 이용한다. 여기서는 BCC를 단절선 단위로 구분하기로 하자. 즉, 기존 BCC의 정의인 '정점 하나를 제거했을 때 연결되어 있는 정점의 집합' 대신 '간선 하나를 제거했을 때 연결되어 있는 정점의 집합'으로 생각한다. (사실 원래 정의대로 생각해도 큰 차이는 없지만, 구현이 조금 더 편리해진다.)

 

이렇게 생긴 BCC 중 사이클이 존재하는 것을 살펴보자. 이러한 BCC 위에 있는 간선의 답이 무조건 B임을 알 수 있다. 엄밀하지 않은 증명은, 사이클 위의 모든 간선은 답이 당연히 B이고 (두 방향으로 모두 돌릴 수 있으니까), 사이클 밖에 있는 간선은 사이클 내부로 연결해줄 수 있는데 그 방향이 두 가지이기 때문이다.

 

따라서 사이클 있는 BCC 밖에 있는 간선들만 봐 주면 된다. 그런데 간선 기준으로 BCC를 구분했으므로 BCC는 점의 집합으로 분리되는데, 서로 다른 BCC를 잇는 간선들이 이에 해당할 것이다. 여기서 블록 컷 트리(Block Cut Tree)와 비슷한 느낌의 트리를 활용한다. 각 BCC 위의 모든 점을 하나의 정점으로 두고, 간선으로 이어진 BCC들끼리 연결하면 트리가 된다. 문제 상황을 이러한 트리로 압축할 수 있는데, 압축 과정에서 손실되는 모든 간선은 어차피 답이 B임이 보장되기 때문이다.

 

따라서 남은 간선들이 트리를 이루므로, HLD라든지 단순한 트리 DP라든지 등 여러 방법을 사용해 남은 문제를 해결할 수 있다. 시간 복잡도는 $O(N+M)$에 해결할 수 있다.

 

초반에 그래프가 연결 그래프라고 생각하고 코딩을 했는데, 계속 틀려서 2시간 쯤 지났을 때 지문을 다시 읽었고, 지문 어디에도 그런 말이 없다는 것을 깨달았다. 그래서 다시 비연결 그래프인 경우까지 감안해 코딩을 했는데, 거기서 여러 가지 실수를 해서 대회 시간 대부분을 날려먹었다. 오랜만에 시간 재고 셋을 돌아보는 거라 황당한 실수를 했는데, 앞으로는 절대 이러면 안 될 것이다.

 

[BOJ 15248] C. Mousetrap (45점)

Subtask 1은 $O(3^N \times N)$ Bitmask DP를 짜면 된다. 3진법이라 구현이 많이 힘들고 실수할 구석도 많다.

 

Subtask 2부터는 정해와 연관될 것으로 추정되는 관찰이 들어간다. 쥐의 경로가 정해졌을 때 답이 무엇이 되는지를 먼저 생각해 본다. 쥐가 이용하는 경로는, 덤보가 최적의 전략을 따를 때, 다음과 같은 형태가 된다: 쥐의 시작점 $s$와 함정의 위치 $e$ 사이의 최단 경로 $P$를 생각하자. $P$ 위의 적당한 점 $x$에 대해, 쥐는

$$s \rightarrow x \rightarrow y \rightarrow x \rightarrow e$$

의 경로를 거친다. $y$는 $x$이거나, $x \rightarrow y$ 경로가 $s \rightarrow e$ 경로와 $x$를 제외하고 만나지 않는 한 점이다. 그림으로 나타내면 아래와 같다.

$x=s$일 수는 있지만, $x=e$인 경우 $y=x$라는 사실을 생각해 두자. 일단 Subtask 2에서는 $s$와 $e$의 거리가 1이기 때문에 $x$가 $s$인 경우만 고려하면 된다. 따라서 아래 경우만을 고려한다. (이 서브태스크에 한해 앞으로 $y$를 $x$로 표기함)

위와 같은 경로를 지나갈 때 답은 얼마가 될까? 일단 쥐가 $x$에서 다시 돌아온다는 것은, $x$ 위치에서 돌아올 길이 없다는 것이다. 이때는 $x$ 직전의 길을 청소하기 전까지 쥐가 움직일 수 없으므로, 필요없는 길을 막을 무한한 시간을 벌 수 있다. 이를 통해 유추해 보면, $e$를 제외한 전체 경로 부분과 인접한 모든 간선에 대해, 정확히 한 번, 가로막거나 청소하는 둘 중 하나의 행동을 해야 함을 알 수 있다.

 

$s$에서 $x$로 가는 과정은 어떨까? 이 과정에서 덤보가 쥐의 $x$의 선택에 제한을 걸 수 있다는 사실을 알아봐야 한다. $x$에 도달하기 전까지 덤보가 할 수 있는 최선은, 트리의 루트를 $s$로 놓을 때, 현재 쥐가 있는 위치 $v$의 자식 정점들 중 하나로 가는 경로를 막는 것이다. 만약 $v$의 자식이 하나뿐이라면, 쥐는 갇힐 것이다. 그렇지 않다면 쥐는 남은 자식들 중 하나를 선택해 이동할 것이다.

 

그렇다면 트리 DP를 할 수 있다. $DP[x]$는 쥐가 $x$까지 내려오는 경우 (더 내려갈 수도 있다) 에 덤보의 최소 행동 횟수이다. $DP[x]$를 계산할 때는 자식의 $DP$ 값을 모두 계산해준 뒤 그 중 두 번째로 큰 값과 $x$의 자식 개수를 더해 주면 된다.

 

Full Task는 아까의 관찰을 이용하되 가장 깊이 들어가는 점 $x$가 될 수 있는 범위가 늘어났다는 점을 이용한다. 그런데 Subtask 2와 달리 $x$를 정하는 과정에서 쥐와 덤보의 의사가 복합적으로 작용하기 때문에 문제가 어려워진다. 쥐가 현재 $s$와 $e$를 잇는 최단 경로상의 어떤 점 $v$에 있다고 해 보자. 쥐가 선택할 수 있는 것은 아래 두 가지이다.

• $e$의 방향으로 한 발짝 다가간다. 덤보가 이 경로를 막는 것은 불가능하므로 쥐는 항상 이 선택지를 선택할 수 있다. 이 경우 향하는 칸을 $v'$라고 하자.
• 곁가지로 빠진다. 이 경우 $e$와의 거리가 1 늘어난다. 곁가지로 향하는 통로가 막혀 있다면 이 선택지는 불가능하다. 이 경우 향하는 칸을 $w$라고 하자.

조금 생각해 보면, $w$로 갈 수 있다면 $w$로 가는 것이 최적일 것 같아 보인다. 이동 경로가 늘어나기 때문이다. 그러나 조금 더 생각해 보면 $v'$로 빠졌을 때 더 좋은 $w$를 얻을 수 있는 경우가 있다. 따라서 단순한 그리디 접근은 불가능하다. Parametric search를 해 보자. 답이 $A$ 이하인지를 보려고 한다. 이때 막아야 하는, $s$부터 $e$까지의 경로에 인접한 간선들을 모두 찾고 그 위치 관계를 보며 모두 막는 게 가능한지를 살펴본다. 모두 막는 것이 가능한지를 고려할 때는 고려해 주어야 할 것이 조금 있는데, 어떤 위치에서 가지치기를 할 때 막아야 할 통로 개수를 정확히 세는 것이 중요하다. 자세한 구현은 코드를 참고하자.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, s, e;
vector<int> link[1000002];

int depth[1000002], par[1000002];
int LCADB[1000002][20];

int getLCA(int x, int y){
    if(depth[x] > depth[y]) swap(x, y);
    for(int d=0; d<20; d++) if((depth[y] - depth[x]) & (1<<d)) y = LCADB[y][d];
    if(x==y) return x;
    for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

int dist(int x, int y){
    return depth[x] + depth[y] - 2*depth[getLCA(x, y)];
}

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

int org[1000002];
void dfs_org(int x, int p=-1){
    vector<int> v (2, 0);
    int ccnt = 0;
    for(auto y: link[x]){
        if(y==p || y==e) continue;
        ccnt++;
        dfs_org(y, x);
        v.push_back(org[y]);
    }
    sort(v.rbegin(), v.rend());
    org[x] = v[1] + ccnt;
}

vector<int> path;
bool onPath[1000002];
int basis = 0;

bool able(int num){
    int cnt = 0;
    int behind = basis;
    for(auto v: path){
        cnt++;
        int tmp = 0;
        for(auto y: link[v]){
            if(onPath[y]) continue;
            if(num < behind + org[y]) cnt--;
            else tmp++;
        }
        behind -= tmp;
        if(cnt < 0) return false;
    }
    return true;
}

int main(){
    scanf("%d %d %d", &n, &e, &s);
    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_org(s);
    dfs(s);
    for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    path.push_back(e);
    while(path.back() != s) path.push_back(par[path.back()]);
    reverse(path.begin(), path.end());
    for(auto x: path){
        onPath[x] = 1;
        if(x != e) basis += (int)link[x].size() - 2;
    }
    basis++;

    for(int i=1; i<=n; i++) sort(link[i].begin(), link[i].end(), [&](auto &x, auto &y){
        return org[x] < org[y];
    });

    int L = basis, R = n+n, ANS=R;
    while(L<=R){
        int M = (L+R)/2;
        if(able(M)) R=M-1, ANS=M;
        else L=M+1;
    }

    printf("%d", ANS);
}