2023 5주차 멘토링 일지

싱가포르 NOI 2022를 돌아 364/500점을 받았다.

 

[BOJ 27288] A. Voting Cities (0:13)

바로 몇 주 전에 동아리에서 랜덤 플래 풀기를 하다가 본 문제라서 바로 풀었다. 기본적인 아이디어는 $K$개의 정점을 시작점으로 두고 한번에 다익스트라를 하면 되는데, 다익스트라에 상태 $d$를 추가적으로 저장한다. $d$는 사용한 쿠폰 목록이다. 아직 쿠폰 가격은 모르므로 쿠폰 가격은 쿼리를 처리할 때 더하도록 하자. 이후 쿼리가 들어올 때는 $32$가지 $d$를 고르는 경우 중 가장 싼 것을 고르면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

int n, m, k, q;
int voting[5002];
vector<pair<int, ll> > link[5002]; /// 역으로 저장함
ll dist[5002][32]; /// dist[i][j]: i번까지 j번 티켓 쓰고 도착하는 경로
bool visited[5002][32];

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

    priority_queue<dat> pq;
    for(int i=0; i<n; i++) for(int j=0; j<32; j++) dist[i][j] = 1e18;
    for(int i=1; i<=k; i++){
        pq.push(dat(voting[i], 0, 0));
        dist[voting[i]][0] = 0;
    }
    while(!pq.empty()){
        dat tmp = pq.top(); pq.pop();
        if(visited[tmp.x][tmp.d]) continue;
        int x = tmp.x, d = tmp.d; ll y = tmp.y;
        visited[x][d] = 1;
        dist[x][d] = y;
//        printf("%d %d: %lld\n", x, d, y);
        for(auto [nxt, add]: link[x]){
            for(int mode=0; mode<6; mode++){
                if((d >> mode) & 1) continue;
                int nxtD = d + (mode == 5 ? 0 : (1<<mode));
                ll nxtY = y + add / 10 * (mode == 5 ? 10 : (9-mode));
                pq.push(dat(nxt, nxtD, nxtY));
            }
        }
    }

    scanf("%d", &q);
    while(q--){
        int S; ll price[5];
        scanf("%d %lld %lld %lld %lld %lld", &S, &price[0], &price[1], &price[2], &price[3], &price[4]);
        ll ans = 1e18;
        for(int d=0; d<32; d++){
            if(dist[S][d] > 1e17) continue;
            bool able = 1;
            for(int i=0; i<5; i++) if(((d>>i)&1) && price[i] == -1) able = 0;
            if(!able) continue;

            ll option = dist[S][d];
            for(int i=0; i<5; i++) if((d>>i)&1) option += price[i];
            ans = min(ans, option);
        }
        if(ans > 1e17) puts("-1");
        else printf("%lld\n", ans);
    }
}

[BOJ 27291] D. Grapevine (2:40)

트리 문제를 잘 다룰 수 있는지 묻는 문제다. Centroid Decomposition과 dfs ordering을 이용한 세그먼트 트리를 잘 굴리면 된다. 이 알고리즘들을 모두 안다면 쉽게 풀 수 있다. 다만 구현이 매우 길어서 실수할 구석이 많다. 나도 이 문제에서 1시간 반 이상을 소비한 것 같다. 시간 복잡도는 $O(N \log N + Q \log^2 N)$ 쯤 일 것이다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segmentTree{
    int SZ;
    vector<ll> tree, lazy;

    void init(int n){
        SZ = n;
        tree.resize(n*4+1), lazy.resize(n*4+1);

        init(1, 1, n);
    }

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

    void propagate(int i, int l, int r){
        tree[i] += lazy[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void add(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        add(i*2, l, m, s, e, v);
        add(i*2+1, m+1, r, s, e, v);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    ll query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return 3e18;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }

    ll query(){
        return query(1, 1, SZ, 1, SZ);
    }
} tree[100002];

struct Line{
    int nxt, idx;
    Line(){}
    Line(int nxt, int idx): nxt(nxt), idx(idx){}
};

int n, q;
int ex[100002], ey[100002];
ll len[100002];
vector<Line> link[100002];
bool on[100002];

namespace HLD{
    struct Fenwick{
        int n;
        ll tree[100002];

        void init(int _n){
            n = _n;
            for(int i=1; i<=n; i++) tree[i] = 0;
        }

        void _add(int x, ll v){
            while(x<=n){
                tree[x] += v;
                x += x&-x;
            }
        }

        void add(int s, int e, ll v){
            _add(s, v);
            _add(e+1, -v);
        }

        ll _sum(int x){
            ll ret = 0;
            while(x){
                ret += tree[x];
                x -= x&-x;
            }
            return ret;
        }

        ll sum(int x){
            return _sum(x);
        }
    } tree;

    int par[100002];
    int in[100002], out[100002], depth[100002], inCnt;
    int LCADB[100002][20];

    void dfs(int x, int p=-1){
        in[x] = ++inCnt;
        for(Line y: link[x]){
            if(y.nxt == p) continue;
            par[y.nxt] = x;
            depth[y.nxt] = depth[x] + 1;
            dfs(y.nxt, x);
        }
        out[x] = inCnt;
    }

    void init(){
        dfs(1);
        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];

        tree.init(n);
        for(int i=1; i<n; i++){
            int x = ex[i], y = ey[i];
            if(depth[x] < depth[y]) swap(x, y);
            /// x가 더 아래에 있는 정점
            tree.add(in[x], out[x], len[i]);
        }
    }

    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];
    }

    ll query(int a, int b){
        int c = getLCA(a, b);
        return tree.sum(in[a]) + tree.sum(in[b]) - tree.sum(in[c])*2;
    }

    void update(int x, ll v){
        tree.add(in[x], out[x], v);
    }
}

bool centroidUsed[100002];
int centroidRoot, centroidPar[100002], centroidDepth[100002];
int subtreeSize[100002];
int sz[100002], in[100002][20], out[100002][20], depth[100002][20];
int canFindEdges[100002][20];

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

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

void eulerTourDfs(int x, int p, int d, int c){
    in[x][d] = ++sz[c];
    for(auto y: link[x]){
        if(y.nxt == p || centroidUsed[y.nxt]) continue;
        depth[y.nxt][d] = depth[x][d] + 1;
        eulerTourDfs(y.nxt, x, d, c);
    }
    out[x][d] = sz[c];
}

void putLengthDfs(int x, int p, int d, int c){
    for(auto y: link[x]){
        if(y.nxt == p || centroidUsed[y.nxt]) continue;
//        printf("Put %d-%d in %d\n", ex[y.idx], ey[y.idx], c);
        canFindEdges[y.idx][d] = c;
        tree[c].add(1, 1, sz[c], in[y.nxt][d], out[y.nxt][d], len[y.idx]);
        putLengthDfs(y.nxt, x, d, c);
    }
}

int findCentroid(int x, int d = 0){
    getSubtreeSize(x);
    x = getCentroid(x, -1, (subtreeSize[x] + 1) / 2);
    centroidUsed[x] = 1;
    centroidDepth[x] = d;

    depth[x][d] = 0;
    eulerTourDfs(x, -1, d, x);
    tree[x].init(sz[x]);

    putLengthDfs(x, -1, d, x);

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

ll getAnswer(int x){
    int c = x;
    ll ret = 1e18;
    while(c){
//        printf("C: %d, X: %d: XtoC %lld, Cval %lld\n", c, x, HLD::query(c, x), tree[c].query());
        ret = min(ret, HLD::query(c, x) + tree[c].query());
        c = centroidPar[c];
    }
    assert(ret <= 1e17);
    return ret;
}

void changeVertex(int x){
    int c = x;
    ll v = (on[x] ? 1e18 : -1e18);
    on[x] = !on[x];
    while(c){ /// 센트로이드를 돌아다니며 +, - 해주기
        int d = centroidDepth[c];
        tree[c].add(1, 1, sz[c], in[x][d], in[x][d], v);
        c = centroidPar[c];
    }
}

void changeEdge(int idx, ll v){
    /// HLD 데이터 수정
    assert(idx);
    int x = ex[idx], y = ey[idx];
    if(HLD::depth[x] < HLD::depth[y]) swap(x, y);
    HLD::update(x, v - len[idx]);

    for(int d=19; d>=0; d--){ /// 센트로이드 데이터 수정
        if(!canFindEdges[idx][d]) continue;
        int x = ex[idx], y = ey[idx], c = canFindEdges[idx][d];
        if(depth[x][d] < depth[y][d]) swap(x, y); /// 이제 x가 더 아래에
        tree[c].add(1, 1, sz[c], in[x][d], out[x][d], v - len[idx]);
//        printf("After changing c %d: query ans %lld\n", c, tree[c].query());
    }

    len[idx] = v;
}

int main(){
    map<pair<int, int>, int> mpEdge;
    scanf("%d %d", &n, &q);
    for(int i=1; i<n; i++){
        int x, y; ll w;
        scanf("%d %d %lld", &x, &y, &w);
        ex[i] = x, ey[i] = y, len[i] = w;
        link[x].push_back(Line(y, i));
        link[y].push_back(Line(x, i));
        mpEdge[make_pair(x, y)] = mpEdge[make_pair(y, x)] = i;
    }
    centroidRoot = findCentroid(1);
    HLD::init();

    int grapeCnt = 0;
    while(q--){
        int qt;
        scanf("%d", &qt);
        if(qt == 1){ /// Seek the nearest
            int x;
            scanf("%d", &x);
            if(!grapeCnt) puts("-1");
            else printf("%lld\n", getAnswer(x));
        }
        else if(qt == 2){ /// 정점 업데이트
            int x;
            scanf("%d", &x);
            grapeCnt += (on[x] ? -1 : 1);
            changeVertex(x);
        }
        else{
            int a, b; ll w;
            scanf("%d %d %lld", &a, &b, &w);
            changeEdge(mpEdge[make_pair(a, b)], w);
        }
    }
}

 

[BOJ 27289] B. Gym Badges (4:01)

처음 봤을 때는 쉬울 줄 알았는데, 그렇지 않아서 당황한 문제다. 끝나고 찾아보니 BOJ 15773 (Touch The Sky)와 같은 문제라고 한다. 옛날에 풀었는데 기억이 안 났다. 일단 Full Task를 풀려면 제곱 풀이를 아는 게 좋다.

 

문제를 다음과 같이 바꿔 표현한다. 점수 $S$가 있고, 순서쌍 $(A_i, B_i)$가 있다. $S \le B_i$인 경우 $S += A_i$를 시행할 수 있다. 한 순서쌍은 한 번만 시행할 수 있다. 가능한 시행의 최대 횟수를 구하는 것이 목표이다.

 

Observation 1. 먼저 두 순서쌍 $(A_i, B_i)$와 $(A_j, B_j)$를 모두 시행에 사용할 때, 그 순서를 고려해 보자. 두 시행을 모두 하기 전의 $S$값을 $L$로 놓고, 시행이 가능할 조건에 대한 두 가지 식을 정리하고 나면, $A_i + B_i < A_j + B_j$일 경우 첫 번째 순서쌍을 먼저 쓰는 것이 이득임을 알 수 있다. 따라서 먼저 이 순서대로 모든 순서쌍을 정렬한다, 더불어, $A_i + B_i = A_j + B_j$일 경우, 무엇이 앞에 오든 큰 상관이 없다.

 

이제 여기서 자명한 DP 하나를 생각할 수 있다. $DP[i][j]$는 $i$번 순서쌍까지 총 $j$번의 시행을 했을 때의 최소 높이이다. 높이가 작을수록 더 좋다. 이대로 DP를 해 나가면 쉽게 $O(N^2)$로 풀 수 있다. 이렇게 하면 Subtask 1, 3을 풀 수 있다.

 

이제 이 DP를 최적화할 방법을 찾는다. $DP[i]$의 값들을 보면 $j$가 커질수록 증가한다. 인접한 값들의 차이에 주목하면, 이 차이 역시 증가함을 알 수 있다. 증명은 귀납법을 이용하는데, $DP[i][j+1] - DP[i][j] := D_j$로 놓고, 순서쌍이 하나 추가될 때 어떤 기준으로 이 $D_j$ 수열이 변하는지를 관찰하면 된다. $D$ 수열의 의미, 그리고 제곱 점화식을 생각해 보면 두 가지 경우가 있음을 알 수 있는데, 먼저 이번에 본 수열의 $A_i$값이 $D$ 수열의 특정 위치에 끼어들어가 오름차순이 유지되는 사건이 반드시 일어난다. 여기에 추가로 만약 시행 전 $D$값의 합, 즉 $DP[i][j]$의 최댓값이 $B_i$ 이하였다면, 마지막 $D$값이 탈락된다. 이 현상은 직접 시뮬레이션을 여러 번 해 보면 납득된다. 증명 역시 어렵지 않을 것 같다.

 

그래서 남은 것은 이 $D$값을 어떤 자료구조로 관리해 주면 된다. 처음에 풀이를 전부 알기 전 세그먼트 트리로 구현하는 바람에 세그를 썼는데, 그냥 힙 하나만 들고 다녀도 충분할 것 같다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    ll tree[2000002];

    void add(int i, int l, int r, int x, ll v){
        if(l==r){
            tree[i] += v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) add(i*2, l, m, x, v);
        else add(i*2+1, m+1, r, x, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    int rightest(int i, int l, int r){
        if(l==r) return l;
        int m = (l+r)>>1;
        if(tree[i*2+1]) return rightest(i*2+1, m+1, r);
        return rightest(i*2, l, m);
    }
} tree;

int n;
pair<ll, ll> arr[500002];
pair<ll, int> datas[500002];
int loc[500002];
ll val[500002];
ll sum;
int ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i].first);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i].second);
    sort(arr+1, arr+n+1, [&](pair<ll, ll> A, pair<ll, ll> B){
        if(A.first + A.second != B.first + B.second) return A.first + A.second < B.first + B.second;
        return A.second < B.second;
    });

    for(int i=1; i<=n; i++){
        datas[i] = make_pair(arr[i].first, i);
    }
    sort(datas+1, datas+n+1);
    for(int i=1; i<=n; i++){
        loc[datas[i].second] = i;
        val[i] = datas[i].first;
    }

    for(int i=1; i<=n; i++){
        bool rep = (sum > arr[i].second);
        sum += arr[i].first;
        ans++;
        tree.add(1, 1, n, loc[i], arr[i].first);
        if(rep){
            int r = tree.rightest(1, 1, n);
            sum -= val[r];
            tree.add(1, 1, n, r, -val[r]);
            ans--;
        }
    }

    printf("%d", ans);
}

 

[BOJ 27290] C. Towers (29점)

처음에 문제를 보고 쉽게 풀릴 것 같았는데 결국 끝까지 풀지 못했다. IOI 2021 Park가 생각나는 어려운 문제인 것 같다.

 

Subtask 4까지 풀었는데, Subtask 1, 2는 그냥 브루트포스고 3은 네 꼭짓점에 타워를 설치하며 사각형 크기를 점점 줄여 나가면 된다. Subtask 4는 왼쪽부터 x좌표를 보며 행 내의 모든 점을 색칠하는데, 만약 색칠 도중 한 y좌표에 세 점이 색칠되면 가운데 점 색칠을 해제해 주는 식으로 풀면 된다.

 

(푸는 중)

 

[BOJ 27292] E. Fruits (35점)

이 문제는 엄청 어려울 것 같다는 느낌이 있었고 실제로도 그런 것 같다. Subtask 1, 2는 쉽기 때문에 설명을 생략한다.

 

Subtask 4를 풀려면 제곱 DP를 만들면 된다. $DP[i][j]$를 $i$번 market까지 방문했고 최댓값이 $j$인 상태에서 최대 이익이라고 정의한다. $DP[i] \rightarrow DP[i+1]$의 전이를 $O(N^2)$에 하면 세제곱에 Subtask 3을 풀 수 있다. 전이를 $O(N)$에 하는 것도 조금만 머리를 써 주면 된다. $DP[i+1][j]$의 값을 고를 때 $DP[i][0] \cdots DP[i][j]$ 중 최댓값을 보면 되니까, $j$를 올려 주면서 저 최댓값을 저장해 주는 식으로 하면 된다. 이렇게 하면 $O(N^2)$이 풀린다.

 

(푸는 중)