2023 4주차 멘토링 일지

COI 2022 (크로아티아) 를 돌아 네 문제 중 세 문제를 풀어 334점을 받았다. 400점을 받아야 했을 셋인 것 같은데 아쉽다.

 

[BOJ 25447] D. Vingete (00:18)

화성 지도 세그를 알면 매우 쉽게 맞을 수 있다. 사실상 이 세그먼트 트리를 아는지 물어보는 문제기 때문에 더 이상 설명하지 않는다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
    int s, e, l, r;
    Edge(){}
    Edge(int s, int e, int l, int r): s(s), e(e), l(l), r(r){}
};

struct segTree{
    int cnt[2000002], sz[2000002], sum[2000002];

    void init(int i, int l, int r, int *arr){
        cnt[i] = sum[i] = 0;
        if(l==r){
            sz[i] = arr[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, arr);
        init(i*2+1, m+1, r, arr);
        sz[i] = sz[i*2] + sz[i*2+1];
    }

    void update(int i, int l, int r, int s, int e, int v){
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            cnt[i] -= v;
            sum[i] = (cnt[i] ? sz[i] : sum[i*2] + sum[i*2+1]);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        sum[i] = (cnt[i] ? sz[i] : sum[i*2] + sum[i*2+1]);
    }

    int query(){
        return sum[1];
    }
} tree;

int n, m, k;
int arr[300002];
vector<Edge> link[100002];
vector<int> stp;

int ans[100002];

void dfs(int x, int p){
    ans[x] = tree.query();
    for(Edge e: link[x]){
        if(e.e == p) continue;
        tree.update(1, 1, k, e.l, e.r, 1);
        dfs(e.e, x);
        tree.update(1, 1, k, e.l, e.r, -1);
    }
}

int main(){
    scanf("%d %d", &n, &m);
    stp.push_back(1), stp.push_back(m+1);
    for(int i=1; i<n; i++){
        int x, y, l, r;
        scanf("%d %d %d %d", &x, &y, &l, &r);
        stp.push_back(l), stp.push_back(r+1);
        link[x].push_back(Edge(x, y, l, r));
        link[y].push_back(Edge(y, x, l, r));
    }
    sort(stp.begin(), stp.end());
    stp.erase(unique(stp.begin(), stp.end()), stp.end());
    k = (int)stp.size() - 1;
    for(int i=1; i<=k; i++) arr[i] = stp[i] - stp[i-1];
    for(int i=1; i<=n; i++){
        for(Edge &edge: link[i]){
            edge.l = lower_bound(stp.begin(), stp.end(), edge.l) - stp.begin() + 1;
            edge.r = lower_bound(stp.begin(), stp.end(), edge.r + 1) - stp.begin();
        }
    }
    tree.init(1, 1, k, arr);

    dfs(1, -1);

    for(int i=2; i<=n; i++) printf("%d\n", ans[i]);
}

 

BOJ 25445. Mensza (2:14)

(아직 BOJ에 업로드가 안 되었다. 언젠간 올라오지 않을까)

 

Three-step 문제이다. 두 수 A, B ($A \neq B$, $A, B \le N = 5 \times 10^5$) 가 있다. 안나는 $A$를 보고 길이 $L$ 이하의 배열을 만든다. 브루노는 $B$를 보고 길이 $L$ 이하의 또 다른 배열을 만든다. $L=20$이다. 주최자는 두 배열을 모은 뒤, 각 수가 등장한 횟수만을 뽑고 셔플해 크리스에게 전달한다. (예를 들어, 두 배열이 $[1, 2, 3]$과 $[1, 1, 3, 4]$면 크리스는 $[1, 1, 2, 3]$을 받을 수 있다.) 크리스는 이 배열을 보고 $A$와 $B$ 중 무엇이 더 큰지 맞혀야 한다.

 

Subtask 2까지는 제한이 조금 더 여유롭고, 다른 방식으로 풀린다. Full Task 역시 어렵지 않다. 관건은, $A<B$면 두 배열에 겹치는 원소가 있게 하고, $A>B$면 그런 원소가 없게 하자는 아이디어이다. $B$에 해당하는 배열은 수 $B$를 이진수로 나타냈을 때 앞에 있는 비트부터 취한 접두사들로만 구성한다. 예를 들어, $B=19=1011_{(2)}$면, 배열은 $[16, 18, 19]$를 리턴한다. 이제 $A$에 대한 배열을 어떻게 만들어야 할까? $A<B$일 경우, $A$와 $B$가 처음으로 달라지는 비트들이 있다. 이들 비트로 가능한 지점에 대응되는 값을 모두 넣어준다. 예를 들어, $A=17=1001_{(2)}$면, $1010$, $1100$, $10000$, $100000$, $\cdots$ 등을 넣어준다. 각각 $2^1, 2^2, 2^4, 2^5, \cdots$ 비트에서 처음으로 B가 A보다 커질 때 B의 배열에 등장할 수 있는 배열들이다.

 

이렇게 구현하면 문제를 맞을 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int L, st;
int q;
char str[15];

int main(){
    scanf("%d", &L);
    st = (L==200 ? 1 : L==110 ? 2 : 3);
    scanf("%d", &q);
    while(q--){
        scanf("%s", str);
        if(str[0] == 'a'){
            int x;
            scanf("%d", &x);
            vector<int> v;
            for(int i=0; i<19; i++){
                if((x>>i)&1) continue;
                v.push_back((x+(1<<i)) >> i << i);
            }
            printf("%d ", (int)v.size()); for(auto x: v) printf("%d ", x); puts(""); fflush(stdout);
        }
        else if(str[0] == 'b'){
            int x;
            scanf("%d", &x);
            vector<int> v;
            int T = 0;
            for(int i=18; i>=0; i--) if((x>>i)&1) T+=(1<<i), v.push_back(T);
            printf("%d ", (int)v.size()); for(auto x: v) printf("%d ", x); puts(""); fflush(stdout);
        }
        else{
            int len;
            scanf("%d", &len);
            vector<int> v(len);
            for(int i=0; i<len; i++){
                scanf("%d", &v[i]);
            }
            printf("%c\n", *max_element(v.begin(), v.end()) == 2 ?'B':'A');
        }
    }
}

 

BOJ 25444. Mađioničar (2:47)

이 문제도 거의 Manacher 알고리즘을 아는지 물어보는 문제다. 그런데 인터랙티브 방식이라 구현할 때 $2N$ 이하의 횟수로 문제를 풀기 위해서 조금 신경써 줘야 할 부분들이 많다. 이 문제도 더 이상 설명할 게 없다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[200002];
int ans;

bool query(int l, int r){
    assert(l%2 == r%2);
    if(l%2==0) return true;

    printf("? %d %d\n", (l+1)/2, (r+1)/2);
    fflush(stdout);
    int x;
    scanf("%d", &x);
    return x;
}

int main(){
    scanf("%d", &n);
    n = 2*n-1;
    int maxV = 0, maxMid = 0;
    for(int i=1; i<=n; i++){
        if(maxV < i){ /// 바깥쪽이라 알 수 없는 경우
            for(int l=1; i+l<=n+1 && i-l>=0; l++){
                if(!query(i-l, i+l)) break;
                arr[i] = l;
            }
        }
        else{ /// 안쪽인 경우
            int m = maxMid, mlen = arr[m];
            int l = maxMid-mlen, r = maxMid+mlen;
            int q = i, p = m+m-q, plen = arr[p];
            if(p-plen > l) arr[q] = arr[p];
            else if(p-plen < l) arr[q] = r-q;
            else{
                arr[q] = p-l;
                for(int l=arr[q]+1; i+l<=n+1 && i-l>=0; l++){
                    if(!query(i-l, i+l)) break;
                    arr[q] = l;
                }
            }
        }
        if(maxV <= i+arr[i]) maxV = i+arr[i], maxMid = i;
        ans = max(ans, arr[i]);
    }

    printf("! %d", ans);
}

 

BOJ 25446. Povjerenstvo (34점)

Subtask 1, 2는 크게 어렵지 않다. 1은 나가는 edge가 없는 것부터 위상 정렬 하듯이 봐주면서, 어떤 정점 $x$에 대해 $x \rightarrow y$의 간선이 있고 $y$가 이미 색칠된(commitee에 포함된) $y$가 있는 경우 색칠하지 않고, 그런 $y$가 없는 경우 색칠하면 된다. 2는 각 연결 성분에 대해 체스판 색칠을 해 주면 된다.

 

34점 이후부터는 나름 할만하다고 생각됐는데, 방향 그래프에서 SCC가 아닌 BCC로 접근하고 코딩하는 바람에 폭망했다.

 

Subtask 3부터는 SCC에 대한 관찰을 해야 한다. 모든 노드가 하나의 SCC이고, 노드가 한 개 이상이라고 가정해 보자. 홀수 사이클이 없으므로, 그냥 인접한 정점을 서로 다른 색으로 색칠하면 문제 조건을 만족할 것이다.

 

(작성중)