2021 SCPC 1차 예선 풀이

2021-07-17

들어가며

한참 PS에서 손을 떼고 있었지만, 오랜만에 키보드나 타볼까 싶어서 문제를 읽기 시작했다.

금요일 15시부터 24시간이기는 하지만 업무, 게임 등으로 금요일의 시간은 거의 못 썼고, 자고 일어나면 토요일 한참 지나 있을 것 같고 출제도 해야 해서 새벽에 많이 하려 했다.

이번에도 문제 아카이빙을 했고 2019년에 미뤄뒀던 것도 드디어 했다. <span>을 지워주는 것이 좋다.

</?span( class[^>]*)?>

한편 코드도 길고 4번 문제의 풀이도 길다 보니 오랫동안 미뤄 왔던 접기 기능을 블로그에 드디어 만들었다.

3. No Cycle

문제를 읽다가 1번은 그냥 구현이 귀찮았고 2번은 잘 안 떠올랐다. 3번도 확신은 없는 Branch&Bound 풀이가 하나 생각났는데 틀리면 그냥 접자는 생각으로 구현했다.

다행히도 Bound가 꽤 세게 잘 걸리는 것 같았고, 통과했다.

SCPC2021R1Q3.cpp 
#include<iostream>
using namespace std;
#include<cstring>
#include<vector>
int t,n,m,k,c[510],chk;
char out[2010];
vector<int> a[510];
pair<int,int> b[2010];
bool dfs(int p)
{
    int i,ret=0;
    c[p]=1;
    for(i=0;i<a[p].size();++i)
    {
        if(!c[a[p][i]])ret=ret|dfs(a[p][i]);
        else if(c[a[p][i]]==1)return true;
    }
    c[p]=2;
    return ret;
}
bool hasCycle()
{
    int i,ret=0;
    memset(c,0,sizeof(c));
    for(i=1;i<=n;++i)if(!c[i])ret=ret|dfs(i);
    return ret;
}
void back(int p)
{
    if(p>k)
    {
        out[p]=0;
        chk=1;
        return;
    }
    out[p]='0';
    a[b[p].first].push_back(b[p].second);
    if(!hasCycle())back(p+1);
    a[b[p].first].pop_back();
    if(chk)return;
    out[p]='1';
    a[b[p].second].push_back(b[p].first);
    if(!hasCycle())back(p+1);
    a[b[p].second].pop_back();
}
int main()
{
    int i,j,x,y;
    cin>>t;
    for(i=1;i<=t;++i)
    {
        cin>>n>>m>>k;
        for(j=1;j<=n;++j)a[j].clear();
        for(j=1;j<=m;++j)
        {
            cin>>x>>y;
            a[x].push_back(y);
        }
        for(j=1;j<=k;++j)cin>>b[j].first>>b[j].second;
        chk=0;
        back(1);
        cout<<"Case #"<<i<<endl<<out+1<<endl;
    }
    return 0;
}

5. 차이

2번 생각이 여전히 잘 안 나서 1번조차도 미뤄두고 일단 점수 긁기부터 해보기로 했다. 전체 문제는 별로 생각을 안 해 보았고, '모든 1번 종류 쿼리에서 차이 값이 0인' 그룹 점수 합이 51점이나 되면서도 풀이가 바로 눈에 보여서 잡았다. 그냥 disjoint set을 union-find로 묶어주면서 같은 집합에 있다면 0, 아니라면 NC이다.

SCPC2021R1Q5.cpp 
#include<iostream>
using namespace std;
#include<vector>
#include<stdio.h>
int t,n,k,p[100010];
int uf(int i)
{
    if(p[i]==i)return i;
    return p[i]=uf(p[i]);
}
int main()
{
    int i,j,x,y,z,w,flag;
    scanf("%d",&t);
    for(i=1;i<=t;++i)
    {
        scanf("%d%d",&n,&k);
        for(j=1;j<=n;++j)p[j]=j;
        printf("Case #%d\n",i);
        flag=1;
        for(j=1;j<=k;++j)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(x==1)
            {
                scanf("%d",&w);
                if(w)flag=0;
                else p[uf(y)]=uf(z);
            }
            else
            {
                if(!flag)printf("0\n");
                else
                {
                    if(uf(y)==uf(z))printf("0\n");
                    else printf("NC\n");
                }
            }
        }
    }
    return 0;
}

1. 친구들

문제에서 주어지는 조건대로 disjoint set을 union-find로 묶어주고 마지막에 집합의 개수를 세주면 된다. \(O(N \log N)\)

SCPC2021R1Q1.cpp 
#include<iostream>
using namespace std;
#include<algorithm>
#include<stdio.h>
int t,n,p[100010],out;
int uf(int i)
{
    if(p[i]==i)return i;
    return p[i]=uf(p[i]);
}
int main()
{
    int i,j,x;
    scanf("%d",&t);
    for(i=1;i<=t;++i)
    {
        scanf("%d",&n);
        for(j=1;j<=n;++j)p[j]=j;
        for(j=1;j<=n;++j)
        {
            scanf("%d",&x);
            if(j+x<=n)p[uf(j)]=uf(j+x);
        }
        for(j=1;j<=n;++j)uf(j);
        sort(&p[1],&p[n+1]);
        out=0;
        for(j=1;j<=n;++j)if(p[j]!=p[j-1])out++;
        printf("Case #%d\n%d\n",i,out);
    }
    return 0;
}

4. 예약 시스템

도저히 2번 생각이 안 나서 일단 자고 일어나서 잡았다. 처음에 문제 읽을 때는 지문이나 수식이 너무 복잡해 보인다고 생각했는데 다 이해하고 나니 상당히 재미있는 문제였다.

부분 문제가 나에게는 매우 큰 힌트가 되었다. 부분 문제를 함께 따라가며 풀이를 찾아보자.

1) 모든 \(l_i\) 가 짝수인 경우

일단 최대한 충돌을 줄이기 위해 같은 집합에 속한 예약자들은 덩어리로 붙여 놓는 것이 좋겠다는 생각을 할 수 있다. 그렇다면 아래와 같은 형태가 된다. (Markdown 특성상 첫 행이 <th>일 수밖에 없어 bold가 들어갔지만 MathJax 수식은 영향이 없다. 집합이 달라지는 부분을 Markdown에서 border로 표현하기가 어려워 집합에 색을 칠했고 큰 의미는 없다.)

예시로 \(l_x=6\), \(l_y=8\), \(l_z=6\) 인 경우이고 핵심은 한 집합의 사람들이 모두 모여 있다는 것이다.

\(S_x\) \(S_x\) \(S_x\) \(S_y\) \(S_y\) \(S_y\) \(S_y\) \(S_z\) \(S_z\) \(S_z\) \(S_w\) \(S_w\) …
\(S_x\) \(S_x\) \(S_x\) \(S_y\) \(S_y\) \(S_y\) \(S_y\) \(S_z\) \(S_z\) \(S_z\) \(S_w\) \(S_w\) …

이 경우 충돌을 표시해보면 다음과 같다.

\(S_x\) \(S_x\) \(S_x\) \(S_y\) \(S_y\) \(S_y\) \(S_y\) \(S_z\) \(S_z\) \(S_z\) \(S_w\) \(S_w\) …
\(S_x\) \(S_x\) \(S_x\) \(S_y\) \(S_y\) \(S_y\) \(S_y\) \(S_z\) \(S_z\) \(S_z\) \(S_w\) \(S_w\) …

그렇다면 충돌이 있는 방에는 최대한 스트레스 지수가 작은 사람을 배치해야 하겠다. 즉, 집합마다 스트레스 지수로 정렬하여 가장 작은 4명을 각 직사각형의 꼭짓점 위치에 배치한다.

또한, 집합의 순서를 살펴보면, 배치된 맨 왼쪽 집합과 맨 오른쪽 집합은 2개의 꼭짓점 위치만 충돌이 발생함을 볼 수 있다. 그렇다면 양 끝 집합은 각 집합에서 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 가장 큰 2개를 선택하면 된다.

2) 모든 \(l_i\) 가 홀수인 경우

1)과 비슷하게 배치한 모습을 살펴보자.

예시로 \(l_x=5\), \(l_y=7\), \(l_z=5\) 인 경우이고 이번의 핵심은 두 집합 단위로 수직선이 생긴다는 것이다.

\(S_x\) \(S_x\) \(S_x\) \(S_y\) \(S_y\) \(S_y\) \(S_z\) \(S_z\) \(S_z\) \(S_w\) \(S_w\) …
\(S_x\) \(S_x\) \(S_y\) \(S_y\) \(S_y\) \(S_y\) \(S_z\) \(S_z\) \(S_w\) \(S_w\) \(S_w\) …

이번에도 충돌을 표시해보면 다음과 같다. 주황색은 좌우로도, 상하로도 충돌이 발생함을 의미한다.

\(S_x\) \(S_x\) \(S_x\) \(S_y\) \(S_y\) \(S_y\) \(S_z\) \(S_z\) \(S_z\) \(S_w\) \(S_w\) …
\(S_x\) \(S_x\) \(S_y\) \(S_y\) \(S_y\) \(S_y\) \(S_z\) \(S_z\) \(S_w\) \(S_w\) \(S_w\) …

그렇다면 여기서 주황색의 경우 스트레스 지수가 2번씩 더해짐을 관찰할 수 있다. 따라서 집합에서 스트레스 지수가 가장 작은 사람을 해당 주황색 위치에 배치해야 한다. 나머지 3개 충돌 위치에는 스트레스 지수가 2-4번째로 작은 사람을 배치하면 된다.

1)과 같이 양 끝 집합은 각 집합에서 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 가장 큰 2개를 선택하면 된다.

이제 남은 부분 문제는 원래의 조건 외에는 제약조건이 없는 전체 문제이지만, 조금 더 나눠 생각해보자.

3) 4개 이상의 \(l_i\) 가 홀수인 경우

양 끝 집합을 선택하는 방법을 다시 떠올려보자. 각 집합에서 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 가장 큰 2개 집합을 \(S_x\), \(S_y\) 라고 할 때, 해당 집합의 \(l_i\) 에 따라 다음과 같이 배치할 수 있다.

a. \(l_x\), \(l_y\) 가 모두 짝수인 경우

ㅁ…ㅁ 형태로 배치한다.

\(S_x\) \(S_x\) \(S_x\) \(S_z\) … \(S_w\) \(S_y\) \(S_y\) \(S_y\)
\(S_x\) \(S_x\) \(S_x\) \(S_z\) … \(S_w\) \(S_y\) \(S_y\) \(S_y\)

b. \(l_x\), \(l_y\) 중 1개는 짝수, 다른 1개는 홀수인 경우

ㅁ…ㄴㄱ 형태로 배치한다. \(l_i\) 가 홀수인 집합이 최소 4개이므로 오른쪽에서 두 번째에 배치할 집합이 존재함을 알 수 있다.

\(S_x\) \(S_x\) \(S_x\) \(S_z\) … \(S_v\) \(S_w\) \(S_w\) \(S_w\) \(S_y\) \(S_y\)
\(S_x\) \(S_x\) \(S_x\) \(S_z\) … \(S_v\) \(S_w\) \(S_w\) \(S_y\) \(S_y\) \(S_y\)

예시는 \(l_x\) 가 짝수인 경우로, 표 형태는 위와 비슷하게 했다. 적절한 문자가 없어 한글 자음을 사용하다 보니 상하 반전된 모습이다.

c. \(l_x\), \(l_y\) 가 모두 홀수인 경우

ㄴㄱ…ㄴㄱ 형태로 배치한다. \(l_i\) 가 홀수인 집합이 최소 4개이므로 양 끝에서 두 번째에 배치할 집합들이 존재함을 알 수 있다.

\(S_x\) \(S_x\) \(S_x\) \(S_z\) \(S_z\) \(S_u\) … \(S_v\) \(S_w\) \(S_w\) \(S_w\) \(S_y\) \(S_y\)
\(S_x\) \(S_x\) \(S_z\) \(S_z\) \(S_z\) \(S_u\) … \(S_v\) \(S_w\) \(S_w\) \(S_y\) \(S_y\) \(S_y\)

a.-c.에서 모두 가능하다는 것을 확인하였으니 통합하여 계산할 수 있다.

4) 2개의 \(l_i\) 만 홀수인 경우

다시 3)과 같이 각 집합에서 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 가장 큰 2개 집합을 \(S_x\), \(S_y\) 라고 할 때, 해당 집합의 \(l_i\) 에 따라 다음과 같이 고려한다.

a. \(l_x\), \(l_y\) 가 모두 짝수인 경우

ㅁ…ㅁ 형태로 배치한다. 예시는 3) a.와 동일하여 생략한다.

b. \(l_x\), \(l_y\) 중 1개는 짝수, 다른 1개는 홀수인 경우

ㅁ…ㄴㄱ 형태로 배치한다. \(l_i\) 가 홀수인 집합이 2개이므로 오른쪽에서 두 번째에 배치할 집합이 존재함을 알 수 있다. 예시는 3) b.와 동일하여 생략한다.

c. \(l_x\), \(l_y\) 가 모두 홀수인 경우

이 경우가 가장 문제이다. 두 가지 가능성을 보고 둘 중 작은 값을 선택해야 한다.

하나는 앞에서 해왔던 것처럼 ㅁ…ㄴㄱ 형태로 배치하는 것이다. 가장 오른쪽에는 \(S_x\) 를 배치하고, 스트레스 지수가 3번째로 작은 사람과 4번째로 작은 사람의 스트레스 지수 값 합이 3번째로 큰 집합을 가장 왼쪽에 배치해야 한다.

또 다른 가능성은 \(S_x\) 와 \(S_y\) 를 양 끝에 배치하는 것이다. 이 경우에는 나머지 \(l_i\) 가 짝수인 모든 집합이 직사각형 형태로 배치될 수 없고, 스트레스 지수가 가장 작은 2명이 충돌이 2회 발생하는 것으로 계산해야 함을 알 수 있다.

이렇게 모든 경우에 대해서 살펴보았다. 경우들이 복잡했지만 구현은 꽤 간단한데, 단지 스트레스 지수의 범위상 답 계산에 8바이트 정수형 변수를 활용해야 함에 유의하여라. 시간복잡도는 \(M\) 에는 전혀 상관 없고, \(O(N \log N)\) 이다.

SCPC2021R1Q4.cpp 
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#include<stdio.h>
int t,n,m,cnt[2];
long long out,out2;
vector<int> a[20010];
pair<int,int> sum34[20010];
int main()
{
    int i,j,k,x,y;
    scanf("%d",&t);
    for(i=1;i<=t;++i)
    {
        scanf("%d%d",&n,&m);
        cnt[0]=0;
        cnt[1]=0;
        for(j=1;j<=n;++j)
        {
            scanf("%d",&x);
            cnt[x%2]++;
            a[j].clear();
            for(k=1;k<=x;++k)
            {
                scanf("%d",&y);
                a[j].push_back(y);
            }
            sort(a[j].begin(),a[j].end());
            sum34[j]=make_pair(a[j][2]+a[j][3],x%2);
        }
        sort(&sum34[1],&sum34[n+1]);
        out=0;
        if(cnt[0]==n||cnt[1]==n)
        {
            for(j=1;j<=n;++j)out=out+((a[j].size()%2)+1)*a[j][0]+a[j][1]+a[j][2]+a[j][3];
            out=out-sum34[n].first-sum34[n-1].first;
        }
        else
        {
            if(cnt[1]==2&&sum34[n].second==1&&sum34[n-1].second==1)
            {
                for(j=1;j<=n;++j)out=out+((a[j].size()%2)+1)*a[j][0]+a[j][1]+a[j][2]+a[j][3];
                out=out-sum34[n].first-sum34[n-2].first;
                out2=0;
                for(j=1;j<=n;++j)
                {
                    if(a[j].size()%2)out2=out2+2*a[j][0]+a[j][1];
                    else out2=out2+2*a[j][0]+2*a[j][1]+a[j][2]+a[j][3];
                }
                if(out2<out)out=out2;
            }
            else
            {
                for(j=1;j<=n;++j)out=out+((a[j].size()%2)+1)*a[j][0]+a[j][1]+a[j][2]+a[j][3];
                out=out-sum34[n].first-sum34[n-1].first;
            }
        }
        printf("Case #%d\n%lld\n",i,out);
    }
    return 0;
}

2. 이진수

처음에 2-SAT이 떠오른 것이 패인으로 보인다. 어렵게만 접근하고 있었고 결국 최소를 어떻게 찾을지 마지막 1시간까지도 생각이 나지 않아서 결국 \(N≤15\) 일 때 백트래킹만 돌려서 부분점수를 긁었다.

SCPC2021R1Q2.cpp 
#include<iostream>
using namespace std;
int t,n,k,chk,a[50010];
char b[50010],out[50010];
void back(int p)
{
    int i,x;
    if(p>n)
    {
        out[p]=0;
        for(i=1;i<=n;++i)
        {
            out[i]=a[i]+'0';
            x=0;
            if(i>k)x=x|a[i-k];
            if(i<=n-k)x=x|a[i+k];
            if(x+'0'!=b[i])break;
        }
        chk=i>n;
        return;
    }
    a[p]=0;
    back(p+1);
    if(chk)return;
    a[p]=1;
    back(p+1);
}
int main()
{
    int i;
    cin>>t;
    for(i=1;i<=t;++i)
    {
        cin>>n>>k>>b+1;
        chk=0;
        if(n<=15)back(1);
        cout<<"Case #"<<i<<endl<<out+1<<endl;
    }
    return 0;
}

결과

532/800, 이번에는 대회 화면에서 찍는 것을 깜빡했다.

결과
그림 1 결과

정말 오랜만에 문제 풀이를 했는데 4번 같이 재밌는 문제를 풀어서 즐거웠다. 2차 예선은 갈 수 있다고 믿고 (아니라면 그새 PS판 수준이 엄청나게 올라간 것이므로 빨리 접어야 한다) 2차 예선 일정 때 바쁘지 않아서 잘 칠 수 있으면 좋겠다.

돌아가기

댓글