2024 SCPC 2차 예선 후기 및 풀이

 

 

기분 좋게 12시쯤 일어나서 디스코드를 보니 9시에 SCPC가 시작해 있었다.

---

1. 연속 1

0과 1로 이루어진 문자열이 주어진다. $S$의 비용을 지불하고 0을 1로, $E$의 비용을 지불하고 1을 0으로 바꿀 수 있을 때, 연속된 1이 한 묶음 이내가 되게 하는 최소 비용을 구하는 문제이다.

 

각 인덱스에 대해, 이 인덱스 이전을 00...0011...11로 만들 수 있는 최소 비용과, 이 인덱스 뒤를 11...1100...11로 만들 수 있는 최소 비용을 DP로 구한 다음, 더해서 최솟값을 찾는다. 이후 전부를 0으로 만드는 비용과 비교하여 출력하면 된다.

 

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;

int t, n, s, e;
int arr[300005];
ll l[300005], r[300005];

int main(){
    scanf("%d", &t);
    for(int f=1;f<=t;f++){
        scanf("%d %d %d", &n, &s, &e);
        for(int i=1;i<=n;i++) scanf("%d", &arr[i]);
        ll res = 0;
        for(int i=1;i<=n;i++){
            if(arr[i]==1) res += e;
        }
        int prv = 0;
        ll tmp = 0;
        ll all = 0;
        for(int i=1;i<=n;i++){
            if(arr[i]==1){
                l[i] = min(l[prv]+tmp, all);
                all += e;
                tmp = 0;
                prv = i;
            }
            if(arr[i]==0) tmp += s;
        }
        prv = n+1;
        r[n+1] = 0;
        tmp = 0;
        all = 0;
        for(int i=n;i>=1;i--){
            if(arr[i]==1){
                r[i] = min(r[prv]+tmp, all);
                all += e;
                tmp = 0;
                prv = i;
            }
            if(arr[i]==0) tmp += s;
        }
        for(int i=1;i<=n;i++){
            if(arr[i]==1) res = min(res, l[i]+r[i]);
        }
        printf("Case #%d\n%lld\n", f, res);
    }
}

 

2. 라운드 로빈

자연수가 적힌 공 $N$개가 주어진다. 이들을 모두 큐에 넣고, 큐에서 공을 하나 뺀 뒤 적힌 수를 1 줄여 다시 넣는 시행을 반복한다. 이때 0이 되면 다시 넣지 않는다. 이때 쿼리가 주어지는데, $X$번째로 큐에서 뽑히는 공의 번호(적힌 수가 아닌 처음 들어온 순서)를 출력하는 문제이다.

 

몇 번째 주기에서 큐에 들어 있는 공이 1개 줄어드는지는 정렬을 이용하면 쉽게 구할 수 있다. 이후 이분 탐색을 통해 $X$번째로 큐에서 공이 빠질 때 큐에 들어 있던 공의 개수를 알 수 있다. 이를 $M$이라 하자. $N$부터 $M+1$개의 공이 큐에 들어 있는 동안 지나간 턴 수는 미리 구해놓을 수 있고, 남은 턴 수가 $Y$라 하면 큐에 남아 있는 공 중 들어온 처음에 순서대로 $Y%M$번째에 위치한 공이 답이 된다. 이를 구하기 위해서 나는 처음 들어온 순서대로 세그먼트 트리에 넣어 두고 공이 하나 빠질 때마다 해당 위치를 제거하는 방법을 사용했다. 그러면 이분 탐색을 통해 남아 있는 공 중 $Y%M$번째가 무엇인지 알 수 있다. 이때 오프라인 쿼리를 이용해 $X$가 작은 것부터 처리해야 AC를 받는다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pi;

int t, n, q;
ll x;
pi arr[100005];
int tree[400005];
pi qu[100005];

void init(int node, int s, int e){
    if(s==e){
        tree[node] = 1;
        return;
    }
    int m = (s+e)>>1;
    init(node<<1, s, m);
    init(node<<1|1, m+1, e);
    tree[node] = tree[node<<1]+tree[node<<1|1];
}

void update(int node, int s, int e, int l, int v){
    if(l<s||e<l) return;
    if(s==e){
        tree[node] += v;
        return;
    }
    int m = (s+e)>>1;
    update(node<<1, s, m, l, v);
    update(node<<1|1, m+1, e, l, v);
    tree[node] = tree[node<<1]+tree[node<<1|1];
}

int query(int node, int s, int e, int l, int r){
    if(e<l||r<s) return 0;
    if(l<=s&&e<=r) return tree[node];
    int m = (s+e)>>1;
    return query(node<<1, s, m, l, r)+query(node<<1|1, m+1, e, l, r);
}

int main(){
    scanf("%d", &t);
    for(int f=1;f<=t;f++){
        scanf("%d %d", &n, &q);
        for(int i=0;i<n;i++){
            scanf("%lld", &x);
            arr[i] = pi(x, i+1);
        }
        sort(arr, arr+n);
        vector<ll> vec;
        vec.push_back(0);
        ll prv = 0;
        for(int i=0;i<n;i++){
            vec.push_back((n-i)*(arr[i].first-prv));
            prv = arr[i].first;
        }
        for(int i=1;i<vec.size();i++) vec[i] += vec[i-1];
        vec.push_back(1e18);
        for(int i=0;i<q;i++){
            scanf("%lld", &x);
            qu[i] = pi(x, i);
        }
        sort(qu, qu+q);
        int idx = 0;
        init(1, 1, n);
        ll res = 0;
        for(int i=0;i<q;i++){
            while(vec[idx+1]<qu[i].first){
                update(1, 1, n, arr[idx].second, -1);
                idx++;
            }
            int s = 1;
            int e = n;
            ll u = (qu[i].first-vec[idx]-1)%(n-idx)+1;
            while(s^e){
                int m = (s+e)>>1;
                if(query(1, 1, n, 1, m)>=u) e = m;
                else s = m+1;
            }
            res += s;
        }
        printf("Case #%d\n%lld\n", f, res);
    }
}

 

3. 방범 시스템

좌표평면에 $N$개의 정점과 가중치가 주어지고, 쿼리로 정점이 주어진다. 이때 $N$개의 정점 모두에 대해 택시 거리와 가중치를 곱한 것의 합을 출력하는 문제다.

 

택시 거리이므로 $x$축과 $y$축을 나눠서 생각할 수 있다. 한 축에 대해, 쿼리로 들어온 좌표가 $a$라고 하자. 이때 좌표 $b$에 위치한 가중치 $c$의 정점은 $a<b$일 때 $-ca+bc$, $a \geq b$일 때 $ca-bc$를 답에 더해주게 된다. 이는 $a$에 대한 일차함수 형태이고, 오프라인 쿼리를 이용하면 케이스의 변환이 최대 한 번 일어나므로 답을 구할 수 있다.

 

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> pi;

int t, n, m, x, y;
pi arr[5][100005];
double brr[100005];
double out[100005];

int main(){
    scanf("%d", &t);
    for(int f=1;f<=t;f++){
        scanf("%d", &n);
        for(int i=0;i<n;i++){
            scanf("%d %d", &x, &y);
            arr[0][i] = pi(x, i);
            arr[1][i] = pi(y, i);
        }
        for(int i=0;i<n;i++) scanf("%lf", &brr[i]);
        scanf("%d", &m);
        for(int i=0;i<m;i++){
            scanf("%d %d", &x, &y);
            arr[2][i] = pi(x, i);
            arr[3][i] = pi(y, i);
            out[i] = 0;
        }
        sort(arr[0], arr[0]+n);
        arr[0][n].first = 1e7;
        sort(arr[2], arr[2]+m);
        double slope = -1;
        double base = 0;
        for(int i=0;i<n;i++) base += arr[0][i].first*brr[arr[0][i].second];
        int prv = -1;
        for(int i=0;i<m;i++){
            while(arr[0][prv+1].first<arr[2][i].first){
                prv++;
                slope += 2*brr[arr[0][prv].second];
                base -= 2*arr[0][prv].first*brr[arr[0][prv].second];
            }
            out[arr[2][i].second] += slope*arr[2][i].first+base;
        }
        sort(arr[1], arr[1]+n);
        arr[1][n].first = 1e7;
        sort(arr[3], arr[3]+m);
        slope = -1;
        base = 0;
        for(int i=0;i<n;i++) base += arr[1][i].first*brr[arr[1][i].second];
        prv = -1;
        for(int i=0;i<m;i++){
            while(arr[1][prv+1].first<arr[3][i].first){
                prv++;
                slope += 2*brr[arr[1][prv].second];
                base -= 2*arr[1][prv].first*brr[arr[1][prv].second];
            }
            out[arr[3][i].second] += slope*arr[3][i].first+base;
        }
        printf("Case #%d\n", f);
        for(int i=0;i<m;i++) printf("%lf\n", out[i]);
    }
}

 

4. 수열 탈집중화

길이 $N$의 수열 $A$가 주어질 때, 구간의 모든 수를 해당 구간의 최댓값, 혹은 최솟값으로 만드는 시행을 하여$\sum \limits _{i \leq i, j \leq N} (A[i]-A[j])^{2}$를 최소화하는 문제였다. 이때 가능한 답 중 최소 시행인 것을 아무거나 출력해야 한다.

 

구간의 모든 수를 최솟값 혹은 최댓값 중 하나로 만들고, 개수를 최대한 비슷하게 맞추면 된다고 생각했다. 따라서 2번 이내의 시행으로 할 수 있는 것 같지만, 구현이 더러울 것 같아 패스했다.

 

5. 보물찾기

$N$개의 정점, $M$개의 간선으로 이루어진 무방향 그래프가 주어진다. 이때 각 정점을 $A$ 혹은 $B$가 소유한다. 몇 개의 정점에는 보물이 묻혀 있다. 아래와 같은 게임을 반복하여, 보물이 위치한 정점에 무한히 반복할 수 있으면 $A$가, 아니면 $B$가 이긴다. 이때 출발점에 따라 누가 이기는지 출력하는 문제이다.

게임 : 처음에 한 정점에 말을 놓는다. 말이 놓인 정점을 소유한 사람이, 연결된 정점 중 한 곳에 말을 옮긴다. 이를 반복한다.

 

우선 바로 승패가 결정되는 조건을 생각해보았다. 만약 출발점에서 $A$가 소유한 정점 둘이 연결되어 있고, 둘 중 하나라도 보물이 있다면 둘을 왕복하는 것을 반복하여 $A$가 이긴다. 여기에 $A$가 소유한 정점만으로 열결되어 있는 정점을 출발점으로 하는 경우에 대해서도, 역시 $A$가 이긴다. 만약 $B$가 소유한 정점 둘이 연결되어 있고, 둘 모두에 보물이 없다면 둘을 왕복하는 것을 반복하여 $B$가 이긴다. 여기에 $B$가 소유한 정점만으로 연결되어 있는 정점을 출발점으로 하는 경우에 대해서도, 역시 $B$가 이긴다.

 

위 경우를 잘 생각해보면 같은 소유자를 가진 연결된 정점끼리 유파를 이용해 union하는 것이 자연스럽다. 유한 시간 내에 소유자의 마음대로 말을 이동시킬 수 있기 때문이다. 이렇게 묶인 묶음들을 $A$묶음, $B$묶음이라 하자.

 

이제 남은 묶음을 분류하면 다음과 같다.

1. 보물이 단 한 개도 없는 $A$묶음

2. 보물이 있는 크기 1의 $A$묶음

3. 임의의 연결된 두 정점에 대해, 적어도 한 정점에 보물이 있는 $B$ 묶음

 

같은 소유자를 가진 정점은 모두 union되었으므로 $A$묶음은 $B$묶음과만, $B$묶음은 $A$묶음과만 연결되어 있다. 이 시점에 승패가 확실한 묶음은 모두 소유자가 승자이므로 1, 2, 3 케이스에서 이 시점에 승패가 확실해진 묶음으로 말을 이동시키는 전략은 없다. 따라서, 우리는 1, 2, 3 케이스만 남았다고 생각해도 좋다.  각 케이스를 분석해보자.

 

분석하기 전에, 어떤 이동에 대해서 상대방이 이를 계속 원상복귀시켜도 상대방이 이긴다면 이는 의미 없는 이동이 된다는 점을 기억하자. 또한, 묶음의 크기가 2 이상일 때 묶음 내에서 말을 계속 순환시키면 진다는 것 역시 기억하자.

 

1번의 경우, 3번 묶음으로 언젠가는 말을 이동시켜야 한다. 이때, 이동한 정점에 보물이 없다면, $B$가 말을 무한히 원상복귀시켜 이긴다. 이동한 정점에 보물이 있다면, $B$는 말을 무한히 원상복귀시킬 수 없다. 따라서 $B$는 말을 다른 묶음으로 이동시켜야 하게 된다.

 

2번의 경우, 3번 묶음으로 말을 이동시켜야 하는데, 만약 이후에 $B$가 말을 무한히 원상복귀시킨다면 $B$는 진다. 따라서 $B$는 말을 다른 묶음으로 이동시켜야 하게 된다.

 

3번의 경우, 2번 묶음에 말을 이동시킨다면 $A$가 무한히 원상복귀시켜 이긴다. 1번 묶음으로 이동하기 전의 정점에 보물이 있다면 $A$가 무한히 말을 원상복귀시켜 이긴다. 따라서 $B$는 말을 보물이 없는 정점에서 1번 묶음으로만 이동시킬 수 있다.

 

이렇게 유의미한 이동을 모두 파악한 상태에서, 각 묶음을 정점으로, 말을 이동시킬 수 있는 묶음끼리의 관계를 단방향 간선으로 나타낸 그래프를 생각해보자. 이때 다른 묶음으로 갈 수 없는 모든 묶음은 소유자의 패배로 승패가 결정된다. 또한, 묶음 $U$에 대해, $U$에서 $U$의 소유자의 승리로 승패가 결정된 묶음으로 갈 수 있다면 묶음 $U$는 소유자가 승리한다. 마지막으로, 묶음 $U$에 대해, $U$에서 갈 수 있는 모든 묶음이 $U$의 소유자의 패배로 승패가 결정된다면, 묶음 $U$는 소유자가 패배한다.

 

위 관찰을 통해 묶음들의 승패를 최대한 결정했다고 하자. 그러나 아직 승패가 결정되지 않은 묶음이 존재할 수 있다. 이런 묶음을 애매한 묶음이라고 하자. 한 묶음에서 갈 수 있는 모든 묶음의 승패가 결정되었다면 해당 묶음은 애매할 수 없다. 이때 애매한 묶음 하나에서 말을 출발시켜보자. 애매한 $B$ 묶음의 경우, 여기서 갈 수 있는 묶음 중 승패가 결정된 묶음은 $A$가 승리하는 묶음밖에 없다. 따라서 애매한 $A$ 묶음으로 말을 이동시키는 것이 최선이다. 이때, 애매한 $A$ 묶음에서 다른 애매한 $B$ 묶음으로 말을 넘기면, 이 과정이 반복된다. 애초에 $A$묶음에서 $B$묶음으로 "갈 수 있다"고 정의되기 위해서는 출발점 혹은 도착점에 보물이 있어야 하므로, 이렇게 무한히 사이클을 돌리면 $A$가 이기게 된다. 따라서 모든 애매한 묶음은 $A$의 승리이다.

 

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int t, n, m, x, y;
char whos[100005];
char tre[100005];
int prv[100005];
vector<int> adj[100005];
int res[100005];
vector<int> uadj[100005], ruadj[100005];
bool vis[100005];
int cnt[100005];

int fnd(int a){
    if(prv[a]==0) return a;
    return prv[a] = fnd(prv[a]);
}

void unin(int a, int b){
    if(fnd(a)==fnd(b)) return;
    prv[fnd(a)] = fnd(b);
}

int main(){
    scanf("%d", &t);
    for(int f=1;f<=t;f++){
        scanf("%d %d", &n, &m);
        scanf("%s", whos+1);
        scanf("%s", tre+1);
        for(int i=1;i<=n;i++){
            prv[i] = 0;
            adj[i].clear();
            uadj[i].clear();
            ruadj[i].clear();
            vis[i] = false;
            cnt[i] = 0;
            res[i] = 0;
        }
        while(m--){
            scanf("%d %d", &x, &y);
            adj[x].push_back(y);
            adj[y].push_back(x);
            if(whos[x]==whos[y]) unin(x, y);
        }
        for(int i=1;i<=n;i++){
            for(auto j: adj[i]){
                if(whos[i]=='A'&&tre[i]=='T'&&whos[j]=='A') res[fnd(i)] = 1;
                if(whos[i]=='B'&&tre[i]=='.'&&whos[j]=='B'&&tre[j]=='.') res[fnd(i)] = 2;
            }
        }
        for(int i=1;i<=n;i++){
            if(res[fnd(i)]) continue;
            for(auto j: adj[i]){
                if(res[fnd(j)]) continue;
                if(whos[i]=='B'||whos[j]=='A') continue;
                if(tre[i]=='.'){
                    if(tre[j]=='.') uadj[fnd(j)].push_back(fnd(i));
                    else uadj[fnd(i)].push_back(fnd(j));
                }
                else uadj[fnd(i)].push_back(fnd(j));
            }
        }
        for(int i=1;i<=n;i++){
            sort(uadj[i].begin(), uadj[i].end());
            uadj[i].erase(unique(uadj[i].begin(), uadj[i].end()), uadj[i].end());
        }
        vector<int> uvec;
        for(int i=1;i<=n;i++){
            if(res[fnd(i)]) continue;
            if(fnd(i)==i) uvec.push_back(i);
        }
        for(auto i: uvec){
            for(auto j: uadj[i]) ruadj[j].push_back(i);
        }
        queue<int> que;
        for(auto i: uvec){
            if(res[i]) continue;
            if(uadj[i].size()==0){
                if(whos[i]=='A'){
                    res[i] = 2;
                    que.push(-i);
                }
                else{
                    res[i] = 1;
                    que.push(i);
                }
                vis[i] = true;
            }
        }
        while(!que.empty()){
            int u = que.front();
            que.pop();
            if(u>0) res[abs(u)] = 1;
            else res[abs(u)] = 2;
            if(whos[abs(u)]=='A'){
                if(u>0){
                    for(auto v: ruadj[u]){
                        cnt[v]++;
                        if(cnt[v]==uadj[v].size()) que.push(v);
                    }
                }
                else{
                    for(auto v: ruadj[-u]){
                        if(vis[v]) continue;
                        vis[v] = true;
                        que.push(-v);
                    }
                }
            }
            else{
                if(u>0){
                    for(auto v: ruadj[u]){
                        if(vis[v]) continue;
                        vis[v] = true;
                        que.push(v);
                    }
                }
                else{
                    for(auto v: ruadj[-u]){
                        cnt[v]++;
                        if(cnt[v]==uadj[v].size()) que.push(-v);
                    }
                }
            }
        }
        printf("Case #%d\n", f);
        for(int i=1;i<=n;i++){
            if(res[fnd(i)]==2) printf("B");
            else printf("A");
        }
        printf("\n");
    }
}