엘리스 코드 챌린지 후기

이미 본선 대회도 끝나고 많이 늦었지만, 단순 기록용으로 글을 남긴다.

정말 말도 많고 탈도 많은 대회였던 것 같다.

문제는 아마 표절 관련 이슈로 내린 것 같아서, 간략하게 풀이와 느낀 점 정도만 적어두려고 한다.

(개인 제출 기록을 확인할 수 없어서, Day 1 ~ Day 3까지의 코드는 기억으로 복원했기 때문에 정확하지 않을 수 있다.)

---

Day 1) 목표량

수를 문자열로 보고, 다음 순서의 문자열을 구하면 된다.

코드

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;cin>>s;
    next_permutation(s.begin(),s.end());
    cout<<s;
    return 0;
}

+) 이 문제도 비슷한 문제가 있는 것 같다..

---

Day 2) 정리 정돈을 좋아하는 k씨

주어진 구간을 정렬해서 k번째 숫자를 찾으면 된다.

시간복잡도가 $O(nmlogn)$에 1초 제한이라 TLE면 counting sort를 해야 되나 싶었는데, 무리 없이 통과했던 것 같다.

코드

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m;scanf("%d%d",&n,&m);
    vector<int> k(n+1);
    for(int i=1;i<=n;i++)scanf("%d",&k[i]);
    while(m--){
        int l,r,x;scanf("%d%d%d",&l,&r,&x);
        vector<int> a(1,-1e9);
        for(int i=l;i<=r;i++)a.push_back(k[i]);
        sort(a.begin(),a.end());
        printf("%d\n",a[x]);
    }
    return 0;
}

---

Day 3) 문자열 압축 해제

pair의 second로 괄호(=-1)와 수(>=0)를 구분하고, first에 개수를 저장하면 된다.
v는 stack이라고 생각하면 되는데, 그냥 더 익숙해서 벡터로 구현했다.

이 반례가 생각나서 제출할 때 주석에 반례를 적어서 제출했던 것 같은데, 출제자 정해는 overflow를 고려하지 않은 코드였다. 지금 보니 이 문제도 비슷한 문제가 있었던 거 보면... 사람들은 이때부터 뭔가 이상함을 느낀 것 같다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

int main(){
    string s;cin>>s;
    vector<pll> v;
    for(auto c:s){
        if(c=='(')v.push_back({1,-1});
        else if(c==')'){
            ll x=0;
            while(v.back().second!=-1)x+=v.back().first,v.pop_back();
            v.pop_back();
            x*=v.back().second,v.pop_back();
            v.push_back({x,x});
        }
        else{
            v.push_back({1,c-'0'});
        }
    }
    ll ans=0;
    while(!v.empty())ans+=v.back().first,v.pop_back();
    printf("%lld",ans);
    return 0;
}

---

Day 4) 트리 위의 게임

상대의 이득을 최소로 만드는 자식을 찾아 답을 구해나가면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int>tree[100001];
bool ans[100001];

ll go(int node=1,int pa=-1,int d=0){
    ll ret=-2e18;
    for(auto nx:tree[node]){
        if(nx==pa)continue;
        ret=max(ret,-go(nx,node,d+1));
    }
    if(ret<-1e18)ret=0;
    ret+=node;
    if(d%2)ans[node]=ret>0;
    else ans[node]=ret>=0;
    return ret;
}

int main() {
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        tree[u].push_back(v),tree[v].push_back(u);
    }
    go();
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

---

Day 5) 수열 복원

부분 수열의 합 중 가장 작은 수는 항상 0이고, 그다음으로 작은 수는 원래의 수열 중 가장 작은 수 하나의 합으로 만들어진 수이다. 따라서 이 과정을 부분 수열의 개수가 2 이상인 동안 반복하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;scanf("%d",&n);
    multiset<int> se;
    for(int i=0;i<1<<n;i++){
        int x;scanf("%d",&x);
        se.insert(x);
    }
    while(se.size()>1){
        auto it=se.begin();
        int x=*next(it);printf("%d ",x);
        while(it!=se.end()){
            se.erase(se.find(*it+x));
            it++;
        }
    }
}

---

Day 6) 빨간 선과 파란 선

그리디에 사로잡혀서, 다익스트라로 풀 수 있다는 생각이 들기까지 오래 걸린 문제이다.

1) 가장 큰 덩어리 2개 합치기
2) 연결되지 않은 정점 2개(가장 작은 덩어리 2개) 합치기
3) 가장 큰 덩어리에 연결되지 않은 정점(가장 작은 덩어리) 합치기

위 3가지 경우 말고는 시도해볼 필요가 없다고 생각했고, N 제한이 30이라 직접 만든 테스트 케이스로 돌려보니 1초 안에 잘 돌아갔다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,vector<int>> piv;

int main() {
    int n;scanf("%d",&n);
    vector<int> e(n);
    for(int i=1;i<n;i++)scanf("%d",&e[i-1]);
    map<vector<int>,int> vis;
    priority_queue<piv,vector<piv>,greater<piv>> pq;
    pq.push({0,{}});
    while(!pq.empty()){
        auto [cnt,v]=pq.top();pq.pop();
        if(vis.count(v))continue;vis[v]=cnt;
        int sum=0,edges=0;
        for(auto i:v)sum+=i,edges+=i-1;
        int ones=n-sum,sz=v.size(),red=!e[edges];
        if(v.size()>=2){
            vector<int> nv=v;
            nv.pop_back(),nv.pop_back(),nv.push_back({v[sz-1]+v[sz-2]});
            pq.push({cnt+red*v[sz-1]*v[sz-2],nv});

            nv=v;reverse(nv.begin(),nv.end());
            nv.pop_back(),nv.pop_back(),nv.push_back({v[0]+v[1]});
            sort(nv.begin(),nv.end());
            pq.push({cnt+red*v[0]*v[1],nv});
        }
        if(ones>=2){
            vector<int> nv=v;
            nv.push_back(2);sort(nv.begin(),nv.end());
            pq.push({cnt+red*1,nv});
        }
        if(v.size()>=1&&ones){
            vector<int> nv=v;
            nv.back()++;
            pq.push({cnt+red*v.back(),nv});

            nv=v;reverse(nv.begin(),nv.end());
            nv.back()++;sort(nv.begin(),nv.end());
            pq.push({cnt+red*v[0],nv});
        }
    }
    printf("%d",vis[{n}]);
}

---

Day 7) 계기판 조작하기

매우 큰 숫자는 예외처리하고, 나머지는 찾는데 많은 시간이 걸리지 않으므로 모든 경우를 다 시도해보면 된다.

제한이 달라서 풀이는 전혀 다르지만, 이 문제도 거의 같은 문제가 있었다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,k;scanf("%d%d",&n,&k);
    if(k==10)return !printf("1023456789");
    else if(k==9)return !printf("102345678");
    else if(k==8)return !printf("10234567");
    else{
        while(1){
            n++;
            set<int> se;
            string s=to_string(n);
            for(auto i:s)se.insert(i);
            if(se.size()==k)return !printf("%d",n);
        }
    }
}

---

Day 8) 강림제

논란의 그 문제였다.

난 저 문제의 존재를 몰라서 못 풀고 있었는데, 무려 $300^4$에 비례하는 코드를 내고 간신히 통과했다.(...??)

Day 3 때 데이터가 약하다는 것을 알았고, 일단 통과했으니 넘어갔다. 그래서 이 코드는 정해가 아니다..

코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int sum[305],dp[301][301][301];//현재 시각, 남은 친구, 현재 기도중인 친구

int main() {
    int n,m,k,t;scanf("%d%d%d%d",&n,&m,&k,&t);
    vector<pii> v(m);
    memset(dp,-0x3f,sizeof(dp)),dp[0][k][0]=0;
    for(auto &[a,b]:v){
        scanf("%d %d",&a,&b);
        sum[a]++,sum[b]--;
    }
    for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
    for(int i=1;i<=n;i++)sum[i]=min(sum[i],t);
    for(int cur=0;cur<n;cur++)for(int r=0;r<=k;r++)for(int p=0;p<=k;p++){
        int need=t-sum[cur+1];
        int P=!need?0:p;
        for(int add=0;add<=min(r,need);add++)
            dp[cur+1][r-add][P+add]=max(dp[cur+1][r-add][P+add],dp[cur][r][p]+(P+add>=need));
    }
    int ans=0;
    for(int i=0;i<=k;i++)for(int j=0;j<=k;j++)ans=max(ans,dp[n][i][j]);
    printf("%d",ans);
}

---

Day 9) 격자 위의 ELICE

첫 번째 E와 5번째 E가 구분되지 않으므로, 두 E의 위치를 뒤집어서 다익스트라를 2번 돌리면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
typedef array<int,4> arr;
pii go[4]={{1,0},{-1,0},{0,1},{0,-1}};

int a[1001][1001];
int vis[32][1001][1001];
pii xy[5];

int dijkstra(int n){
    memset(vis,0x3f,sizeof(vis));
    priority_queue<arr,vector<arr>,greater<arr>> pq; pq.push({0,1,1,xy[0]==pii{1,1}});
    while(!pq.empty()){
        auto [d,x,y,idx]=pq.top();pq.pop();
        if(vis[idx][x][y]<1e9)continue; vis[idx][x][y]=d;
        if(idx==5)return d;
        for(auto [dx,dy]:go){
            int nx=x+dx,ny=y+dy;
            if(nx<1||nx>n||ny<1||ny>n)continue;
            int nidx=idx+(xy[idx]==pii{nx,ny});
            pq.push({d+a[x][y]+a[nx][ny],nx,ny,nidx});
        }
    }
}

int main() {
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
    for(auto &[x,y]:xy)scanf("%d%d",&x,&y);
    int ans=dijkstra(n);
    swap(xy[0],xy[4]);
    printf("%d",min(ans,dijkstra(n)));
}

---

Day 10) 계단 카드 뽑기

이때 순위를 좀 높여보려고 10시에 눈뜨자마자 풀었는데, 어떻게 푸는지 몰라서 세그먼트 트리+이분 탐색도 써보고, 시간초과도 줄여보려고 펜윅 트리로도 바꿔보고 별짓은 다해본 것 같다. 아마 이 문제도 데이터가 약해서 뚫렸던 것 같은데, 생일의 절반을 이 문제에 날려버려서 풀고도 기분이 이상했다. 아무튼, 그래서 정해가 아닐 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;
const int sz=1<<16;
int BIT[sz],n,cnt[sz];
int sum(int x){
    int ret=0;
    for(int i=x;i;i-=i&-i)ret+=BIT[i];
    return ret;
}
void update(int x,int val){
    for(int i=x;i<=n;i+=i&-i)BIT[i]+=val;
}
set<int> se;

int main() {
    scanf("%d",&n);
    vector<int> a(n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    int ans=1,l=0,r=-1;
    while(r+1<n){
        update(a[++r],1);
        if(++cnt[a[r]]==2)se.insert(a[r]);
        for(auto i:se){
            if(i>r-l+1)break;
            if(sum(i)<=i)continue;
            while(a[l]!=i&&sum(i)>i){
                update(a[l],-1);
                if(cnt[a[l]]--==2)se.erase(se.find(a[l]));l++;
            }
            if(sum(i)>i){
                update(a[l],-1);
                if(cnt[a[l]]--==2)se.erase(se.find(a[l]));l++;
            }
            break;
        }
        ans=max(ans,r-l+1);
    }
    printf("%d",ans);
}

---

후기

6일 차와 10일 차 문제가 꽤 어려워서 만점자가 많지 않을 거라 생각했는데, 결국 리더보드에 만점자 100명이 채워졌다.

이후 본선 진출자에게 오는 개별 연락을 받았으나, 이러한 이유로 가지 못했다. (만점자를 추첨이 아니라 모두 초대하고 싶어서 수요조사를 했다고 한다.)

음. 맛있다~

그래도 운 좋게 100+명중 50명에 당첨돼서 치킨을 받았다.

대회 끝나고 후기를 보는데, 의문의 문제 리스트가 올라왔다.

1. https://www.acmicpc.net/problem/15126
2. https://www.acmicpc.net/problem/2378
3. https://www.acmicpc.net/problem/3680
4. https://www.acmicpc.net/problem/3605

심지어 제출 기록이 거의 없는 이 문제들에, 의문의 백준 1솔브 유저가 본선 며칠 전에 위 리스트 중 2문제를 풀었다고 한다. (지금은 사라진듯하다.) 게다가 본선 수상자 모두가 ICPC WF 메달리스트라고 하니... 거의 뭐.. PS 괴담이다.

개인적으로 치킨을 받게 된 건 고맙지만, PS에 진심인 학생들이 바라는 건 이런 금전적인 부분은 절대 아니다.

이런 글을 썼는데도 본선에서 같은 논란이 생긴 것은 너무 유감스럽다. 현재 문제를 만드는 학생들이 출제나 검수에 걸리는 시간에 비해 받는 금액은 대부분 열정페이 수준이거나 심지어 적자를 보는 대학도 있다고 들었다. 나도 교내 대회 문제를 내봤기에 그것이 얼마나 힘든지 잘 알고 있고, 열심히 노력해도 끝내 찾지 못한 오류가 대회 중에 하나씩 드러난 경험이 있어서 올해 출제가 상당히 부담스럽다. 그런데 그런 노력을 복붙 딸깍으로 가져가는 것은... 너무 허무하다.

이번에 Elice에 쏠린 많은 관심이 좋은 피드백으로 이어져서, 앞으로 즐거운 마음으로 참여할 수 있는 대회가 많아졌으면 좋겠다.