Problem Solving Diary #27

BOJ 땅따먹기가 생겼다는 소식을 들어서, 테스트 삼아 몇 개 풀어 보았다.

 

https://blobnom.xyz/room/90

BOJ 1626. 두 번째로 작은 스패닝 트리

먼저 최소 스패닝 트리를 하나 잡은 뒤, 각 간선에 대해 해당 간선을 자르고 넣을 수 있는 가장 작은 가중치의 간선을 구해 보는 식으로 풀면 될 것 같다. 하지만 단순히 이렇게 하면 같은 가중치의 간선을 고를 수도 있으므로, 최소 가중치를 두 개까지 저장해 주는 식으로 문제를 풀 수 있을 것이다.

 

처음에 Kruskal 알고리즘 등으로 MST를 찾아 준 후, 사용되지 않은 간선들을 양끝점 사이의 경로에 업데이트해 주고, 세그먼트 트리 등을 이용하는 방식으로 문제를 해결할 수 있다. 여러 가지 사소한 edge case들에 주의해야 할 것 같다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct UnionFind{
    int par[200002];
    void init(int n){
        for(int i=1; i<=n; i++) par[i] = i;
    }
    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

struct Edge{
    int s, e; ll v;
    Edge(){}
    Edge(int s, int e, ll v): s(s), e(e), v(v){}
    bool operator<(const Edge &r)const{
        return v<r.v;
    }
};

struct segTree{
    ll min1[800002], min2[800002];

    void init(int i, int l, int r){
        min1[i] = min2[i] = 1e18;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void update(int i, int l, int r, int s, int e, ll v){
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            if(v < min1[i]) min2[i] = min1[i], min1[i] = v;
            else if(v == min1[i]) {}
            else if(v < min2[i]) min2[i] = v;
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
    }

    pair<ll, ll> query(int i, int l, int r, int x){
        if(l==r) return make_pair(min1[i], min2[i]);
        int m = (l+r)>>1;
        pair<ll, ll> A = make_pair(min1[i], min2[i]), B;
        if(x<=m) B = query(i*2, l, m, x);
        else B = query(i*2+1, m+1, r, x);
        ll c = min(A.first, B.first);
        ll d = min(c==A.first?A.second:A.first, c==B.first?B.second:B.first);
        return make_pair(c, d);
    }
} tree;

int n, m;
Edge edges[200002];
vector<Edge> tedge;
vector<int> link[200002];

int in[200002], sz[200002], inCnt, top[200002];
int par[200002], LCADB[200002][20], depth[200002];

void dfs_in(int x, int p=-1){
    if(p!=-1) link[x].erase(find(link[x].begin(), link[x].end(), p));
    sz[x] = 1;
    for(int &y: link[x]){
        par[y] = LCADB[y][0] = x, depth[y] = depth[x] + 1;
        dfs_in(y, x);
        sz[y] += sz[x];
        if(sz[y] > sz[link[x][0]]) swap(link[x][0], y);
    }
}

void dfs_hld(int x){
    in[x] = ++inCnt;
    for(int y: link[x]){
        top[y] = (link[x][0] == y) ? top[x] : y;
        dfs_hld(y);
    }
}

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 main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d %d %lld", &edges[i].s, &edges[i].e, &edges[i].v);
    }
    sort(edges+1, edges+m+1);
    dsu.init(n);
    for(int i=1; i<=m; i++){
        int x = edges[i].s, y = edges[i].e;
        if(dsu.find(x)==dsu.find(y)) continue;
        dsu.merge(x, y);
        link[x].push_back(y), link[y].push_back(x);
        tedge.push_back(edges[i]);
    }

    if((int)tedge.size() != n-1){
        puts("-1");
        return 0;
    }

    ll sum = 0;
    for(Edge e: tedge) sum += e.v;

    dfs_in(1);
    top[1] = 1;
    dfs_hld(1);

    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    tree.init(1, 1, n);
    for(int i=1; i<=m; i++){
        Edge e = edges[i];
        int x = e.s, y = e.e, z = getLCA(x, y);
        while(in[x] > in[z]){
            tree.update(1, 1, n, max(in[top[x]], in[z]+1), in[x], e.v);
            x = par[top[x]];
        }
        while(in[y] > in[z]){
            tree.update(1, 1, n, max(in[top[y]], in[z]+1), in[y], e.v);
            y = par[top[y]];
        }
    }

    ll ans = LLONG_MAX;
    for(Edge e: tedge){
        int is = in[e.s], ie = in[e.e];
        pair<ll, ll> p = tree.query(1, 1, n, max(is, ie));
        ll v1 = sum - e.v + p.first, v2 = sum - e.v + p.second;
        if(sum != v1) ans = min(ans, v1);
        if(sum != v2) ans = min(ans, v2);
    }

    if(ans >= 1e16) printf("-1");
    else printf("%lld", ans);
}

BOJ 15564. Äventyr 2

문제 출제자가 리듬 게임을 좋아하시는 것 같다. 문제 내용을 정리하면

• $N$개의 정점으로 이루어진 트리가 있고, $Q$개의 쿼리가 주어진다. 쿼리는 다음과 같은 두 가지이다.
• 1 x: $x$번 정점이 색칠된다.
• 2 x: $x$번 정점에서 색칠된 정점까지 가는 최단 거리를 구한다.

문제의 구조상 Centroid Decomposition으로 쉽게 풀리는 문제라는 것을 알 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 1e9;

int n, q;
vector<int> link[100002];

int subtreeSize[100002];
int centroidPar[100002], centroidDepth[100002], centroidDist[100002][20];
int minDist[100002];
bool centroidUsed[100002];

void subtreeDfs(int x, int p=-1){
    subtreeSize[x] = 1;
    for(int y: link[x]){
        if(centroidUsed[y] || y==p) continue;
        subtreeDfs(y, x);
        subtreeSize[x] += subtreeSize[y];
    }
}

int find_centroid(int x, int p, int lim){
    for(int y: link[x]){
        if(centroidUsed[y] || y==p) continue;
        if(subtreeSize[y] >= lim) return find_centroid(y, x, lim);
    }
    return x;
}

void getDist(int x, int p, int d, int dist){
    centroidDist[x][d] = dist;
    for(int y: link[x]){
        if(centroidUsed[y] || y==p) continue;
        getDist(y, x, d, dist+1);
    }
}

int centroid_decomposition(int x, int d){
    subtreeDfs(x);
    x = find_centroid(x, -1, (subtreeSize[x] + 1) / 2);
    centroidUsed[x] = 1;
    centroidDepth[x] = d;

    getDist(x, -1, d, 0);

    for(int y: link[x]){
        if(centroidUsed[y]) continue;
        int tmp = centroid_decomposition(y, d+1);
        centroidPar[tmp] = x;
    }
    return x;
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=2; i<=n; i++){
        int j;
        scanf("%d", &j);
        link[i].push_back(j);
        link[j].push_back(i);
    }
    int c = centroid_decomposition(1, 0);
    for(int i=1; i<=n; i++) minDist[i] = INF;
    while(q--){
        int t, x;
        scanf("%d %d", &t, &x);
        if(t==1){
            int c = x, d = centroidDepth[x];
            for(; d>=0; d--){
                minDist[c] = min(minDist[c], centroidDist[x][d]);
                c = centroidPar[c];
            }
        }
        else{
            int ans = INF;
            int c = x, d = centroidDepth[x];
            for(; d>=0; d--){
                ans = min(ans, centroidDist[x][d] + minDist[c]);
                c = centroidPar[c];
            }
            printf("%d\n", ans >= INF ? -1 : ans);
        }
    }
}

BOJ 13127. 도박과 사각형

$1$, $2$, $3$, $4$, $5$ 각각에 대해 따로 생각해도 됨이 자명하다. 따라서 편의상 $1$에 대해 푸는 방법을 생각해 보자.

 

기댓값을 구하는 문제이므로 모든 경우의 수에 대한 합을 생각해야 한다. 이를 나중에 전체 경우의 수로 나누어 주면 된다. 즉 문제를 모든 부분직사각형에 대해 $1$이 적힌 칸의 제곱 합을 구하는 문제로 바꿀 수 있다.

 

그냥 합을 구하라면 쉬운데, 제곱 합은 어떻게 구해야 할지 도저히 감이 잡히지 않는다. 그러나 다음과 같은 유명한 테크닉이 있다.

• 집합의 원소 수의 제곱의 합은, 모든 집합 $S$와 임의의 원소 $i$, $j$ (같아도 된다) 에 대해 $i \in S, j \in S$이면 $1$을 더했을 때의 합과 같다.

따라서 임의의 두 $1$에 대해, 해당 두 $1$을 포함하는 직사각형의 수를 모두 더하면, 이 문제의 답이 우리가 구하고자 하는 합과 같다.

 

그런데 저걸 어떻게 빠르게 구할까? 확실한 건 두 개의 $1$을 고정하면 좌표를 통해 답을 구할 수 있다는 것이다. 구체적으로 두 개의 $1$이 $(x_1, y_1)$, $(x_2, y_2)$에 있다고 할 때 ($x_1 \le x_2, y_1 \le y_2$ 가정), 직사각형의 개수가 $x_1y_1(n-x_2+1)(n-y_2+1)$으로 계산됨을 알 수 있다. 따라서 적당한 누적합 전처리를 해 준 뒤, 하나의 $(x_1, y_1)$을 고정하고, $x_2$와 $y_2$가 $x_1$, $y_1$보다 작은지 큰지로 네 영역으로 나눈 다음에 각각에 대해 누적합으로 한번에 합을 계산해줄 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[1002][1002];
ll s1[1002][1002], s2[1002][1002], s3[1002][1002], s4[1002][1002];
double ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        scanf("%d", &arr[i][j]);
//        arr[i][j]=1;
    }

    for(int d=1; d<=5; d++){
        double dans = 0;
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
            if(arr[i][j] != d) s1[i][j]=s2[i][j]=s3[i][j]=s4[i][j]=0;
            else{
                s1[i][j] = i * j;
                s2[i][j] = i * (n+1-j);
                s3[i][j] = (n+1-i) * j;
                s4[i][j] = (n+1-i) * (n+1-j);
            }
        }
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) s1[i][j] += s1[i-1][j];
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) s1[i][j] += s1[i][j-1];
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) s2[i][j] += s2[i-1][j];
        for(int i=1; i<=n; i++) for(int j=n; j>=1; j--) s2[i][j] += s2[i][j+1];
        for(int i=n; i>=1; i--) for(int j=1; j<=n; j++) s3[i][j] += s3[i+1][j];
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) s3[i][j] += s3[i][j-1];
        for(int i=n; i>=1; i--) for(int j=1; j<=n; j++) s4[i][j] += s4[i+1][j];
        for(int i=1; i<=n; i++) for(int j=n; j>=1; j--) s4[i][j] += s4[i][j+1];

        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
            if(arr[i][j] != d) continue;
            dans += s1[i][j] * (n+1-i) * (n+1-j);
            dans += s2[i][j+1] * (n+1-i) * j;
            dans += s3[i+1][j] * i * (n+1-j);
            dans += s4[i+1][j+1] * i * j;
        }
        ans += dans * d;
    }

    double rans = double(ans) / (n*(n+1)/2) / (n*(n+1)/2);
    printf("%.9f", rans);
}

BOJ 16880. 룩, 비숍, 킹, 나이트, 궁전 게임

여러 개의 말이 독립적으로 움직일 수 있는데, 자명히도 스프라그-그런디를 쓰면 된다. 따라서 각 말의 스프라그 그런디 수를 알아내는 것이 문제의 핵심이 된다.

 

스프라그 그런디 수의 정의는 아무 수도 둘 수 없는 상태를 $0$이라 했을 때, 가능한 모든 다음 상태의 스프라그 그런디 수의 mex를 취하면 된다. 여기서 mex는 어떤 집합에 존재하지 않는 가장 작은 음의 정수를 의미한다.

 

룩을 예시로 보면, 다음과 같은 식으로 스프라그 그런디 수가 나온다.

 

위 표에서 재귀적인 구조를 관찰할 수 있고, 해당 구조대로 코딩하면 된다.

 

비슷한 방식으로 하면 비숍은 애초에 왼쪽 아래로 가는 선택지밖에 없어서 간단히 $\min(x, y)$가 나옴을 알 수 있다.

 

이제 킹을 보자. 킹이 움직일 수 있는 칸은 아래, 왼쪽, 왼쪽 아래 세 칸이다. 이걸 염두에 두고 테이블을 채워주면

와 같은 형태가 된다. 따라서,

• $\min(x, y)$가 짝수인 경우, $x+y$가 짝수면 $0$, 홀수면 $1$,
• $\min(x, y)$가 홀수인 경우, $x+y$가 짝수면 $2$, 홀수면 $3$

이 된다.

 

다음으로 나이트를 보자. 나이트는 이동 가능한 칸이 두 가지인데, $(-1, -2)$ 방향과 $(-2, -1)$ 방향 중 하나로 가야 한다. 표를 채워보면 아래와 같은 패턴이 나온다.

굉장히 복잡해 보인다. $\lfloor \frac{\min(x, y)}{3} \rfloor$를 $a$로 정의하고, $x$와 $y$에서 $3a$씩을 뺀 상태로 생각하자. 이때 $\min(x, y) \le 2$이다.

• 만약 $x=0$ 또는 $y=0$ 또는 $x=y=1$이라면 그런디 수가 $0$이다.
• 만약 $x=2, y \ge 4$ 또는 $y=2, x \ge 4$라면 그런디 수가 $2$이다.
• 그렇지 않다면, 그런디 수는 $1$이다.

마지막으로 궁전을 보자. 궁전은 킹과 룩의 이동을 모두 할 수 있다고 한다.

위와 같이 재귀적인 형태이지만 룩과 살짝 다른 형태의 그런디 수를 얻을 수 있다.

 

이제 스프라그 그런디를 짜면 문제를 맞을 수 있다.

BOJ 13575. 보석 가게

기본적인 FFT + 분할 정복을 이용한 거듭제곱 문제다.

#include <bits/stdc++.h>
#include <atcoder/convolution>

using namespace std;
using namespace atcoder;

typedef long long ll;

int n, k;
int arr[1002];
vector<ll> vec;
vector<ll> vecp[10];

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        if((int)vec.size() <= x) vec.resize(x+1);
        vec[x]=1;
    }
    vecp[0] = vec;
    for(int d=1; d<10; d++){
        vecp[d] = convolution(vecp[d-1], vecp[d-1]);
        for(ll &v: vecp[d]) v = min(v, 1LL);
    }

    vector<ll> ans (1, 1);
    for(int d=0; d<10; d++){
        if((k>>d)&1) ans = convolution(ans, vecp[d]);
    }
    for(int i=0; i<(int)ans.size(); i++){
        if(ans[i]) printf("%d ", i);
    }
}

BOJ 17157. Hobson's Trains

Functional Graph가 주어질 때, 각 정점으로 $k$번의 이동 안에 들어올 수 있는 점의 개수를 세는 문제이다.

 

sparse table로 풀 수 있어 보인다. $x$번 정점에서 출발했을 때 이미 방문한 지점을 다시 방문하지 않는 최대 이동횟수를 $A[x]$로 구해 두고, sparse table을 통해 $f^0(x)$부터 $f^{A[x]}(x)$까지 $1$을 더해 주는 것이다.

 

$A[x]$를 어떻게 구할 수 있을까? 그래프 분할을 해야 할 것이다. 임의의 정점에서 시작해서 사이클을 모두 찾고 $A[x]$를 구해줄 수 있다. 그 다음에 sparse table을 이용해 답을 구해 주면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int arr[500002];
vector<int> rev[500002];
int sps[500002][20];

bool visited[500002];
bool chk[500002];
int MX[500002];

void dfs(int x, int v){
    MX[x] = v;
    visited[x] = 1;
    for(int y: rev[x]) dfs(y, v+1);
}

int sum[500002][20];

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]), rev[arr[i]].push_back(i);

    for(int i=1; i<=n; i++){
        if(visited[i]) continue;
        vector<int> path;
        int x = i;
        while(!chk[x]){
            path.push_back(x);
            chk[x] = 1;
            x = arr[x];
        }
        path.erase(path.begin(), find(path.begin(), path.end(), x));
        int cycle_len = (int)path.size();
        for(int d: path) MX[d] = cycle_len-1, visited[d] = 1;
        for(int d: path) for(int x: rev[d]) if(!visited[x]) dfs(x, cycle_len);
    }

    for(int i=1; i<=n; i++) sps[i][0] = arr[i];
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) sps[i][d] = sps[sps[i][d-1]][d-1];

    for(int i=1; i<=n; i++){
        int v = min(MX[i], k) + 1;
        int x = i;
        for(int d=0; d<20; d++){
            if((v>>d)&1){
                sum[x][d]++;
                x = sps[x][d];
            }
        }
    }
    for(int d=19; d>=1; d--){
        for(int i=1; i<=n; i++){
            sum[i][d-1] += sum[i][d];
            sum[sps[i][d-1]][d-1] += sum[i][d];
        }
    }

    for(int i=1; i<=n; i++) printf("%d\n", sum[i][0]);
}