한국정보올림피아드(KOI 2022) 2차 시험 후기

총점: 100/100/14/34=248 (동상, 13.37%, 25위)

 

<세 줄 요약>

1. 1, 2번이 쉽지만은 않았던 시험

2. 마지막 득점 시간 "2시간 24분"

3. TC35에서 TLE

 

보통 KOI 2차 시험에는 1번, 2번에 조금의 노력만으로 100점을 받을 수 있는 문제가 나오고, 3번, 4번에 변별력 있는 서브태스크들을 가진 문제가 나온다. 그래서 수상권에서의 등수는 3번, 4번에서 부분점수를 얼마나 긁었느냐에 따라 결정된다. 그런데 최근 들어 1번, 2번의 문제 난이도가 심상치 않다. 물론 조금 고민하면 풀 수 있는 문제이긴 하지만, 문제를 처음 읽고 나서 조금 당황하게 되는 수준이다. 이에 따라 나는 집중력이 가장 높은 초반부에 3번, 4번 서브태스크들을 잡고, 조금 집중력이 떨어진 시기에 1번, 2번을 푸는 작전을 세웠다. 애초에 은상이 목표였기 때문에 긁어야하는 서브태스크들을 실수 없이 긁고 거기에 추가로 더 긁는다면 목표를 달성할 수 있을 것이라고 생각했다.

 

3번 문제는 이번 시험에서 가장 언급이 많이 되고 있는 문제인 <레벨 업>이다. 원래 기존 3번은 풀태스크가 불가능한 다4-다3 수준의 문제가 나오는 것이 일반적이었는데, 이번에 이례적으로 3번 문제의 정답자가 상당히 많이 나왔고 이 중 일부는 3번이 2번보다 쉽다는 의견을 제시하기도 했다. 아무튼 나는 3번이 절대 풀태스크를 할 수 없는 문제라고 생각하고 있었기 때문에 문제를 읽자마자 서브태스크 긁을 궁리부터 했다. 나이브하게 풀면 4점을 받고, K=1인 경우에 처리를 적절하게 하면 10점을 더 받는다. 40분 정도 투자하여 14점을 긁고 넘어갔다.

 

4번 문제는 <외곽 순환 도로> 문제이다. 이 문제 역시 읽자마자 서브태스크에 집중하였다. 1번 서브태스크부터 차례대로 6점, 8점, 5점, 15점, 57점, 9점이었다. 57점까지 긁는다는 것은 사실상 풀태스크를 하겠다는 것이기에, 4번 서브태스크까지는 어떤 일이 있어도, 무조건 긁어야겠다고 생각했다. 실제로 이는 어렵지 않았다. 1번 서브태스크는 쿼리의 시작점이 정해진 경우였고, 이는 1번 정점에 대한 다익스트라를 미리 돌려놓으면 된다. 2번 서브태스크는 성게 트리로, 1번 서브태스크에서 이어지는 내용이었다. "리프 사이클을 따라 회전" or "1번 정점을 거쳐가기"를 선택해야하므로 전자의 경우 누적합 전처리를 통해, 후자의 경우 1번 정점에 대한 다익스트라를 통해 해결할 수 있었다. 3번 서브태스크는 리프 사이클 간선의 가중치가 비정상적으로 크게 설정된 경우로, 트리 간선만 사용하는 경우였다. 이는 스파스 테이블을 기반으로 한 LCA를 통해 해결할 수 있다. 4번 서브태스크는 반대로 리프 사이클 간선의 가중치가 모두 0인 경우였고, 이는 "가까운 리프 거쳐가기" or "트리 간선만 이용하기" 중에 선택하라는 의미였다. 전자는 리프 정점들을 출발점으로 보고 다익스트라와 비슷하게 계산해줄 수 있고, 후자는 3번 서브태스크와 동일하다. 이렇게 40분 정도 투자하여 34점을 긁고 넘어갔다.

 

1번 문제는 <트리와 쿼리> 문제이다. 사실 문제 읽고 아이디어가 쉽게 떠오르지 않아 조금 당황했다. 개인적으로 아이디어 자체는 자명했던 2번보다는 어려운 문제라고 생각하는데, 전체적으로 제공된 정보가 1번이 더 많아서 사람에 따라 1번을 더 쉽게 느꼈을 수도 있을 것 같다. 1번 문제에서는 각 컴포넌트를 이루는 정점들의 수를 세기 위해서 먼저 1번 정점을 루트로 DFS를 돌려주었다. 그 다음 S에 속하는 정점을 깊이순 오름차순 정렬한 뒤, 자신의 부모가 S에 속해있다면 부모가 속해있는 컴포넌트로, 속해있지 않다면 새로운 컴포넌트로 배정하였다. 이 풀이가 성립하는 것은 상당히 직관적으로 확인할 수 있으며, 정렬까지 해서 총 시간복잡도는 O(QKlogK)가 된다. 20분 정도 투자하여 어렵지 않게 100점을 받았다.

 

2번 문제는 <식사 계획 세우기> 문제이다. 아이디어는 보자마자 자명한 문제이다. 우선 '사전 순'이라는 것에서 그리디 기반임이 자명하다. 그렇다면 언제 그리디를 포기해야하는가? 어쩔 수 없이 포기해야할 때 포기하면 된다. 이는 아직 방문하지 않은 식당이 M개일 때, 남은 식당 중 (M+1)/2개가 같은 종류의 음식을 판매하여 지금부터는 어쩔 수 없이 이 식당들을 2번에 1번 꼴로 방문해야하는 경우이다. 이걸 그대로 구현해주면 된다. 구현 과정에서 현재 가장 많이 남아있는 종류의 식당이 무엇인지 파악하기 위해 세그먼트 트리를 활용한 친구들이 많던데, 이는 크게 돌아가는 풀이이다. 현재 값들의 최댓값을 저장하고 싶다면, "C[i] : 현재 값들 중 i인 것의 개수"로 배열을 하나 잡아 이를 관리해줄 수 있다. 이를 통해 세그먼트 트리를 사용하지 않을 수 있으며, 이는 시간복잡도와 구현 시간을 모두 줄여준다. 나는 이를 알고 있었음에도 불구하고 더 쉬운 구현 방법이 없을까 고민했고, 없다는 것을 깨닫고 고민하다가 구현에서 실수를 많이 해서 시간을 날려먹었다. 40분 정도 투자한 끝에 100점을 받았다.

 

이렇게 해서 시험이 시작하고 2시간 24분이 지난 시점에 248점을 완성했다. 여기까지만 해도 문제 풀이의 순서를 바꾼 내 작전이 성공했다고 느꼈다. 하지만 내 점수를 자세히 본 사람들은 알 수 있듯이, 248점은 내 최종 점수이다. 그렇다면 나는 남은 2시간 6분 동안 무얼했는가?

 

4번 문제는 더 이상 긁을 서브태스크가 없다는 것을 알고 있었고, 3번이 풀태스크가 불가능하다는 것도 알고 있었다. 그렇다면 남은 서브태스크는 단 하나, 3번의 세 번째 서브태스크였다. 32점짜리였고, 맞히면 280점이기 때문에 여기서 은상 안정권이 갈릴 것이라고 생각했다. 그래서 남은 2시간 동안 이 서브태스크를 긁는 것에 올인하겠다고 다짐했다. 근데 하필이면 내가 이 서브태스크를 풀기 위해 장착한 도구가, 스플레이 트리이다. 1번부터 K번까지 1씩 더하는 것은 Lazy Propagation을 통해 처리해줄 수 있고, 그렇다면 크기 순서가 바뀌는 경우만 잘 처리해주면 된다. 그 순서가 바뀌는 것은 중앙부에 x+1 x+1 ... x+1 x x ... x 부분을 구간 뒤집기 쿼리를 통해 처리함으로써 해결된다. 어떤 구간을 뒤집을지 찾는 것도 함수를 이용해 적절히 탐색하며 찾을 수 있다. 그렇게 코드 작성만 1시간 30분을 하여 209줄짜리 스플레이 트리 풀이를 완성했다. 스플레이 트리 특성상 구현이 길어 오류가 엄청 나는데, 1시간 30분 정도면 아무 것도 보지 않은 상태에서 짠 스플레이 트리 코드치고 상당히 빠르게 완성된 편이다. 그리고 이 209줄짜리 코드는 TC35에서 TLE를 받았다. 시간복잡도는 O(MlogN)으로 원래 같았으면 통과가 되어야 정상이지만, 스플레이 트리의 상수가 너무 큰 나머지 1초라는 시간제한을 넘겼던 것 같다. 결국 더 이상 점수 받기를 포기했고, 248점으로 시험을 마무리하게 되었다.

 

사실 스플레이 트리를 시험에서 외워서 짜는 사람은 흔하지 않다. 나도 이번에 처음 짜봤고, 솔직히 짜기 시작할 때만 해도 내가 제대로 돌아가는 코드를 짤 수 있을 것이라고 생각하지 않았다. 스플레이 트리 지지자로서 시험 중에 스플레이 트리를 사용하는 시간복잡도가 보장된 풀이를 떠올려 이를 시간 안에 구현했다는 사실 자체가 굉장히 뿌듯했고, 재미있었다. 그 209줄의 실체와 자세한 코드가 궁금하신 분들을 위해 스플레이 트리 코드만 따로 첨부해두겠다. 비록 은상은 날아간 것 같지만 재미있는 시험이었다. 실제 이번 시험의 1등 점수인 334점이 10명이 넘어서 대상-금상-은상의 점수가 모두 같은 초유의 사태가 벌어질 것 같다고 하는데, 내 얘기는 아니니 팝콘 들고 지켜봐야겠다.

 

3-3 스플레이 트리 코드, TC35에서 TLE)

#include <bits/stdc++.h>
#define SIZE 100010
using namespace std;
struct node
{
    int id,al,lz;
    node *l,*r,*p;
    bool fl;
    node(int x,node *q){
        l=r=nullptr,p=q;
        id=x,al=1,lz=0,fl=false;
    }
};
int N,M,K,L[SIZE];
node *ptr[SIZE],*root;
void push(node *x)
{
    if(x->fl){
        swap(x->l,x->r);
        if(x->l)x->l->fl=!x->l->fl;
        if(x->r)x->r->fl=!x->r->fl;
        x->fl=false;
    }
    if(x->lz){
        x->id+=x->lz;
        if(x->l)x->l->lz+=x->lz;
        if(x->r)x->r->lz+=x->lz;
        x->lz=0;
    }
}
void upd(node *x)
{
    push(x);
    x->al=1;
    if(x->l){
        push(x->l);
        x->al+=x->l->al;
    }
    if(x->r){
        push(x->r);
        x->al+=x->r->al;
    }
}
void rot(node *x)
{
    node *p=x->p;
    node *b=nullptr;
    push(x);push(p);
    if(p->l==x){
        p->l=b=x->r;
        x->r=p;
    }
    else{
        p->r=b=x->l;
        x->l=p;
    }
    x->p=p->p;
    p->p=x;
    if(b)b->p=p;
    if(x->p){
        if(x->p->l==p)x->p->l=x;
        else x->p->r=x;
    }
    else root=x;
    upd(p);upd(x);
}
void splay(node *x,node *g=nullptr)
{
    while(x->p!=g){
        node *p=x->p;
        if(p->p==g){
            rot(x);
            break;
        }
        node *pp=p->p;
        if((p->l==x)==(pp->l==p)){
            rot(p);
            rot(x);
        }
        else{
            rot(x);
            rot(x);
        }
    }
    if(!g)root=x;
}
void kth(int k)
{
    node *x=root;
    push(x);
    while(1){
        while(x->l&&x->l->al>k){
            x=x->l;
            push(x);
        }
        if(x->l)k-=x->l->al;
        if(!k--)break;
        x=x->r;
        push(x);
    }
    splay(x);
}
node *gather(int s,int e)
{
    kth(e+1);
    node *tmp=root;
    kth(s-1);
    splay(tmp,root);
    return root->r->l;
}
void flip(int s,int e)
{
    if(s>=e)return;
    node *z=gather(s,e);
    z->fl=!z->fl;
}
node *F(int k,node *x)
{
    if(!x)return nullptr;
    push(x);
    if(x->id<k){
        if(x->r)return F(k,x->r);
        else return nullptr;
    }
    else{
        if(x->l){
            node *z=F(k,x->l);
            if(z)return z;
            else return x;
        }
        else return x;
    }
}
node *G(int k,node *x)
{
    if(!x)return nullptr;
    push(x);
    if(x->id>k){
        if(x->l)return G(k,x->l);
        else return nullptr;
    }
    else{
        if(x->r){
            node *z=G(k,x->r);
            if(z)return z;
            else return x;
        }
        else return x;
    }
}
void print(node *x)
{
    push(x);
    if(x->l)print(x->l);
    if(x->id>0&&x->id<2000000001)cout<<x->id<<' ';
    if(x->r)print(x->r);
}
void init()
{
    for(int i=1;i<=N;i++)ptr[i]=nullptr;
    root=new node(-1,nullptr);
    node *x=root;
    for(int i=1;i<=N;i++){
        ptr[i]=x->r=new node(L[i],x);
        x=x->r;
    }
    x->r=new node(2000000001,x);
    for(int i=N;i>=1;i--)upd(ptr[i]);
    splay(ptr[N+1>>1]);
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++)cin>>L[i];
    sort(L+1,L+N+1);
    cin>>M>>K;
    init();
    while(M--){
        node *z=gather(1,K);
        z->lz++;
        kth(K);
        int a=0,b=0;
        node *z1=F(root->id,root);
        node *z2=G(root->id-1,root->r);
        if(z1&&z2){
            if(z1->l)a+=z1->l->al;
            while(z1->p!=nullptr){
                node *p=z1->p;
                if(p->r==z1){
                    a++;
                    if(p->l)a+=p->l->al;
                }
                z1=p;
            }
            if(z2->l)b+=z2->l->al;
            while(z2->p!=nullptr){
                node *p=z2->p;
                if(p->r==z2){
                    b++;
                    if(p->l)b+=p->l->al;
                }
                z2=p;
            }
            flip(a,b);
        }
    }
    print(root);
}