Skip to content
Beside the Wheel

2020 중등부 정올 2차

알고리즘

처음이자 마지막 정올 경험이었던 2020 중등부 정올 2차 문제를 다시 풀어본다.

1. 종이접기

https://www.acmicpc.net/problem/20187

문제에 나온 내용 그대로, 종이를 접었을 때 구멍의 모양이 어떻게 되는지를 잘 구현하면 된다.

2. 등산 마니아

https://www.acmicpc.net/problem/20188

간선을 기준으로 지나가는 경로의 수를 계산한다.

  1. DFS를 사용하여 각 정점의 자식 노드 수(cnt)를 계산한다.
  2. 각 간선에 대해 다음 두 가지 경우를 계산한다.
    • 간선 아래쪽의 자식 노드들 중 두 개를 선택하는 경우: cnt*(cnt-1)/2
    • 간선 아래쪽의 자식 노드 하나와 그 외 정점 하나를 선택하는 경우: cnt*(n-cnt)
  3. 각 간선에 대해 2a와 2b를 더한 값이 그 간선을 지나가는 경로의 수이다.
#include <iostream>
#include <vector>
using namespace std;


int n;
vector<vector<int>> V;


long long res;
long long f(int x, int b) {
    long long ret = 1;
    for (int i=0;i<V[x].size();i++) {
        if (b != V[x][i]) {
            long long cnt = f(V[x][i], x);
            long long k = n-cnt;
            res += cnt*k + cnt*(cnt-1)/2;
            ret += cnt;
        }
    }
    return ret;
}


int main() {
    cin>>n;
    V.resize(n+1);
    for (int i=0;i<n-1;i++) {
        int a, b;
        cin>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    f(1, 1);
    cout<<res;
}

3. 버블버블

https://www.acmicpc.net/problem/20190

i번쨰 인덱스의 숫자를 아무 숫자로 바꿀 수 있을 때 배열을 버블소트로 정렬해 필요한 최소 스왑 횟수를 각각 출력하는 문제이다. 즉, 해당 숫자를 어떤 숫자로 바꿔야 스왑 횟수를 최소화할 수 있을지를 고려해야한다.

버블소트의 스왑 횟수는 inversion (i < j, a[i] > a[j]를 만족하는 쌍의 수)와 같다. 먼저 Fenwick 트리를 사용하여 주어진 수열의 inversion 수를 계산한다. 그 다음 구간 트리와 Lazy Propagation 기법을 활용하여 각 원소를 바꿨을 때의 최소 교환 횟수를 찾는다. 핵심 아이디어는 i번째 원소 A[i]를 바꿀 때, j < i 인 경우와 j > i 인 경우를 나누어 생각한다.

  • j < i 인 경우: A[i]가 [1, A[j]-1] 범위에 있으면 교환 횟수 +1
  • j > i 인 경우: A[i]가 [A[j]+1, 끝] 범위에 있으면 교환 횟수 +1

이를 위해 먼저 [A[i]+1, 끝] 구간에 +1을 레이지 업데이트한다. 그 후 i번째 원소부터 차례대로 구간 트리의 최솟값을 찾아 최소 교환 횟수를 계산하고 출력힌다. i번째 요소를 계산했다면, [1, A[i]-1] 구간에 +1, [A[i]+1, 끝] 구간에 -1 업데이트를 수행하고 다음 요소로 넘어간다.

이 문제에서 Fenwick 트리로 inversion을 계산한 것 같은 방식으로 #1517 버블소트 문제도 풀 수 있다.

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string.h>
#define MAX 300001
using namespace std;


long long tree[MAX*4];
long long lazy[MAX*4];
int arr[MAX+1];


int n;
int sum(int i) {
    int ret=0;
    while (i>0) {
        ret+=tree[i];
        i-=(i&-i);
    }
    return ret;
}


void update(int i, int d) {
    while (i<=n) {
        tree[i]+=d;
        i+=(i&-i);
    }
}


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


void update_tree(int l, int r, int x, int gl, int gr, long d) {
    lazy_update(l, r, x);
    if (r<gl||gr<l) return;
    else if (gl<=l&&r<=gr) {
        lazy[x]+=d;
        lazy_update(l, r, x);
    } else {
        int mid = (l+r)/2;
        update_tree(l, mid, x*2, gl, gr, d);
        update_tree(mid+1, r, x*2+1, gl, gr, d);
        tree[x]=tree[x*2]+tree[x*2+1];
    }
}


void update_range(int x, int l, int r, int gl, int gr, int d) {
    lazy_update(l, r, x);
    if (l>gr||r<gl) return;
    if (l>=gl&&r<=gr) {
        tree[x]+=d;
        if (l!=r) {
            lazy[x*2]+=d;
            lazy[x*2+1]+=d;
        }
        return;
    }
    int mid=(l+r)/2;
    update_range(x*2, l, mid, gl, gr, d);
    update_range(x*2+1, mid+1, r, gl, gr, d);
    tree[x] = min(tree[x*2], tree[x*2+1]);
}


int min_tree(int x, int l, int r, int gl, int gr) {
    lazy_update(l, r, x);
    if (l>gr||r<gl) return 1234567890;
    if (l>=gl&&r<=gr) return tree[x];
    else {
        int mid=(l+r)/2;
        return min(min_tree(x*2, l, mid, gl, gr), min_tree(x*2+1, mid+1, r, gl, gr));
    }
}


int sum_tree(int x, int l, int r, int gl, int gr) {
    lazy_update(l, r, x);
    if (l>gr||r<gl) return 0;
    if (l>=gl&&r<=gr) return tree[x];
    else {
        int mid=(l+r)/2;
        return sum_tree(x*2, l, mid, gl, gr) + sum_tree(x*2+1, mid+1, r, gl, gr);
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin>>n;
    vector<int> v;
    for (int i=1;i<=n;i++) {
        cin>>arr[i];
        v.push_back(arr[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i=1;i<=n;i++) {
        arr[i]=lower_bound(v.begin(), v.end(), arr[i])-v.begin()+1;
    }


    int s=0, e=n+1;
    long long bubble=0;
    for (int i=n;i>=1;i--) {
        bubble+=sum(arr[i]-1);
        update(arr[i], 1);
    }
    memset(tree, 0, sizeof(lazy));
    memset(tree, 0, sizeof(tree));


    for (int i=1;i<=n;i++) update_range(1, s, e, arr[i]+1, e, 1);
    for (int i=1;i<=n;i++) {
        update_range(1, s, e, arr[i]+1, e, -1);
        int a = min_tree(1, s, e, arr[i], arr[i]);
        int b = min_tree(1, s, e, s, e);
        cout<<bubble-a+b<<" ";
        update_range(1, s, e, s, arr[i]-1, 1);
    }
}

4. 화려한 정사각형

https://www.acmicpc.net/problem/20193

첫 접근이 어려워서 스위핑, 파라메트릭 서치, 세그먼트 트리라는 태그를 먼저 보고 풀이를 생각하기 시작했다.

일단 파라메트릭 서치적인 접근으로 한 변이 특정 길이를 가지는 정사각형에서 k개의 색 점을 포함할 수 있으면 범위를 작은 쪽으로, 그렇지 않으면 큰 쪽으로 좁히는 방식으로 탐색한다.

is_possible 함수에서 특정 길이를 가지는 정사각형에서 k개의 색 점을 포함할 수 있는지 여부를 확인한다. 이를 위해 세그먼트 트리에 ‘구간에 존재하는 색깔의 갯수’를 저장하도록 구현한다. 점이 정사각형에 포함되는 시점과 빠지는 시점에 트리를 갱신하고, 구간에 존재하는 색깔의 갯수가 k개인경우 true를 반환한다.

여기서 ‘구간에 존재하는 색깔의 갯수’를 저장할 때, 각 구간에 여러 색의 점이 포함되는 경우를 고려하기 위해 점을 색깔별로 multiset에 넣어놓고 동일한 색깔의 이전 점의 y좌표+1 부터 다음 점의 좌표까지 1을 더하거나 빼준다.

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define MAX 250001
constexpr int S=1<<18;
int tree[MAX*4],lazy[MAX*4];


void lazy_update(int x, int s, int e) {
    tree[x]+=lazy[x];
    if(s!=e){
        lazy[x<<1]+=lazy[x];
        lazy[x<<1|1]+=lazy[x];
    }
    lazy[x]=0;
}


void update(int gl, int gr, int v, int x=1, int l=0, int r=S-1) {
    lazy_update(x,l,r);
    if (gr<l||r<gl) return;
    if (gl<=l&&r<=gr) {
        lazy[x]+=v;
        lazy_update(x,l,r);
        return;
    }
    int mid=(l+r)/2;
    update(gl,gr,v,x*2,l,mid);
    update(gl,gr,v,x*2+1,mid+1,r);
    tree[x]=max(tree[x*2], tree[x*2+1]);
}


int query(int x=1, int s=0, int e=S-1) {
    lazy_update(x,s,e);
    return tree[1];
}


struct Event{
    int op,x,y,c;
    bool operator<(const Event &e) const {
        return tie(x,op)<tie(e.x,e.op);
    }
};


int n,k;
Event arr[MAX];
vector<Event> events;
multiset<int> st[MAX];


bool is_possible(int len) {
    memset(tree, 0, sizeof(tree));
    memset(lazy, 0, sizeof(lazy));
    for (int i=1;i<=k;i++) st[i]={0,S-1};
    events.clear();


    for (int i=1;i<=n;i++) {
        events.push_back({1, arr[i].x, arr[i].y, arr[i].c});
        events.push_back({-1, arr[i].x+len, arr[i].y, arr[i].c});
    }
    sort(events.begin(), events.end());


    for (int i=0;i<events.size();i++) {
        int op=events[i].op, y=events[i].y, c=events[i].c;
        if (op==1) {
            auto it=st[c].insert(y);
            int l=max(y,*prev(it)+len), r=min(y+len,*next(it));
            update(l, r-1, 1);
            if (query()==k) return true;
        } else {
            auto it=st[c].lower_bound(y);
            int l=max(y, *prev(it)+len), r=min(y+len, *next(it));
            update(l, r-1, -1);
            st[c].erase(it);
        }
    }
    return false;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>arr[i].x>>arr[i].y>>arr[i].c;
    int l=1,r=MAX;
    while (l<r) {
        int m=(l+r)/2;
        if (is_possible(m)) r=m;
        else l=m+1;
    }
    cout<<r-1;
}

소감

’종이접기라도 완벽하게 풀자!’며 작지만 최선의 결실을 내고자 했던 과거의 나를 위로하는 마음가짐으로 나머지 문제들을 풀어보았다. 마침 요즘 세그트리와 스위핑을 공부하고 있어서 후반 문제에 접근할 엄두를 낼 수 있었다. 비록 1솔로 장려상을 받았지만 나에겐 큰 의미가 있는 대회였다. 3년 반이 지난 지금와서 생각해봐도 확실히 쉽지 않은 문제들인 것 같다. 특히 대회에서 시간 제약을 가지고 풀기엔 더 그렇다.

2020 정올 후에 내가 그렇게 높은 위치가 아니라는 걸 알게되었다. 더 넓은 세상을 바라보고 더 달려야겠다는 생각을 했다. 그리고 뭐든지 끝까지 잡고 할 수 있는데까지는 파봐야겠다는 마음가짐을 가지게 되었다. 지금의 나는 그떄의 열정과 마음가짐을 계속 가지고 있다고 할 수 있을까. 나의 최선을 다하고 있을까.

최선을 다한다고 물리적으로 느끼는 것도 좋지만 고등학교 생활을 하면서 많은 것들을 배우고 경험했으니 지금의 나는 쌓여온 시간만큼의 힘을 낼 수 있는 사람이면 좋겠다. 쌓여온 노력으로 더 괜찮은 경험, 괜찮은 결과를 만들 수 있으면 좋겠다. 정올은 돌아오지 않지만 나에겐 해결해야할 많은 문제들이 있으니 앞으로도 화이팅..

관련글
자료구조LSM Tree자료구조Trie자료구조세그먼트트리알고리즘N Queen알고리즘Range GCD알고리즘가장 가까운 두 점