2026 UCPC 예선 후기

오랜만에 새로운 소식으로 글을 작성하게 되었다.

 

대학 입시를 마치고 최종적으로 gist에 입학하게 되었다. gist 들어가서는 평범하게 대학생활하다가 ucpc를 나가보고 싶어 학교에서 팀원을 모아서 나오게 되었다. 

 

사진에 보이는 거처럼 에타에 구인글을 올렸다. gist 가 ps판이 활성화가 안되어 있다 보니 사람 찾는 게 힘들었고, 그래서 많은 사람들이 볼 수 있는 에타에 올렸다. (많은 분들이 칭찬을 해주셔서 기분이 좋았다 ㅎ)

 

그렇게 어찌저찌 팀원 3명을 모으게 되었다. 다른 친구들의 정확한 프로필을 알 수 없지만 정황상 내가 가장 잘하는 포지션에 있음을 알게 되었다. 그래서 혼자 다 풀 생각으로 대회에 임해야겠다고 생각을 했고, 시험이 끝난 직후 일주일 동안 DOJ와 ucpc 기출에서 골플 문제를 풀면서 최소 플래까진 풀 수 있도록 연습을 했다.

 

 

결과부터 말하면 60등을 했다. 148팀 중 60등이니 반타작..? 보단 더 좋은 결과를 받긴 했다.

 

타임라인 작성이 처음이라 무엇을 어떻게 작성해야될지 모르겠어 제출기록을 바탕으로 작성을 하겠다.

 

A [4:32, 2wa 1 solve]

대회에서 공인한 가장 쉬운 문제이기 때문에 상대적으로 못하는(?) 친구에게 풀라고 시켰고, 4분 32초쯤에 AC를 받았다.

문제를 읽지는 않아서 무슨 내용인지는 모르겠지만 에디토리얼에선 브론즈라고 하니 아마 쉬운 문제였을 것이다.

(그럼에도 2틀을 한 것에는 아쉬움이 있으며, 이는 팀연습이랑 개인 연습을 하면서 페널티를 최대한 안 받을 수 있도록 개선해 나갈 예정이다.)

 

C [8:30, 1wa 2 solve]

이 문제는 투스텝 문제였다. 투스텝은 정말 어렵거나 완전 쉽거나 둘 중에 하나로 나올 가능성이 높았기에 내가 풀까 생각을 하다가 시나엘 친구가 해준다고 해서 맡기고 읽지 않고 넘어갔다. 이후 8분 30초에 AC를 받았으며, 이 문제 역시 실버정도의 난이도로 대회에서 2번째로 쉬운 문제였다.

 

D [15:44,  3 solve]

시나엘 친구가 C를 푼 이후에 바로 D를 잡는다고 하였고, 내가 문제를 살펴봤을 때 그렇게 어러운 문제가 아니라고 생각해 맡기고 넘어갔다.

역시나 7분 만에 1트로 AC를 받아냈다.

 

E [28:58,  4 solve]

여러 문제 지문을 읽으면서 E가 가장 무난한 문제인 거처럼 보였고, 해당 문제를 15분경부터 잡기 시작했다. 문제는 전형적인 MST에서 추가로 간선에 비용이 있는 게 아닌 노드에 비용이 있고, 선택된 노드끼리는 완전 그래프가 만들어지는 형태의 문제였다.

초반에는 어떻게 풀어야 될지 고민을 하다가 결국 MST를 만들 때, 노드가 선택되었다면 이전 노드와 유니온 파인드로 연결해 주는 형태를 추가해 주면 끝나는 간단한 문제였다.

AC 받은 코드다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,u,v,w;
ll A[100010];
struct nd{
    ll u,v,w;
};
bool compare(nd A,nd B){
    return A.w<B.w;
}
vector<nd>graph;
ll lt=-1;
ll parent[100010];
ll fd(ll a){
    if(a==parent[a])return a;
    return parent[a]=fd(parent[a]);
}
ll uni(ll a,ll b){
    a=fd(a);
    b=fd(b);
    if(a==b)return 0;
    parent[b]=a;
    return 1;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++)parent[i]=i;
    for(int i=1;i<=m;i++){
        cin >> u >> v >> w;
        graph.push_back({u,v,w});
    }
    for(int i=1;i<=n;i++){
        cin >> A[i];
        graph.push_back({-1,i,A[i]});
    }
    sort(graph.begin(),graph.end(),compare);
    ll cnt=0;
    ll v=0;
    ll imsi=0;
    for(int i=0;i<graph.size();i++){
        nd T=graph[i];
        if(T.u==-1){
            if(lt==-1){
                imsi=T.w;
            }else{
                if(uni(T.v,lt)){
                    v+=T.w;
                    v+=imsi;
                    cnt++;
                    imsi=0;
                }
            }
            lt=T.v;
        }else{
            if(uni(T.u,T.v)){
                v+=T.w;
                cnt++;
            }
        }
    }
    cout << v;
}

 

I [1:03:28, 6wa 5 solve]

시나엘 친구가 D 이후 계속해서 트라이한 끝에 1시간 3분쯤에 해결하였다. 내가 이문제를 읽어봤을 때 엣코더에서 많이 본 익숙한 문제였고, 마침 시나엘 친구가 D를 AC 받았기에 넘기고 G를 풀러 갔다. 그러다 보니 자세한 사정을 알지 못하지만 사소한 부분에서 코드를 잘못 작성해 틀리고 있었다고 한다. 그렇게 오랜 사투 끝에 맞춰낼 수 있었다. (결과적으로 G를 풀지 못했기 때문에 G가 아닌 I를 도와서 빠르게 풀었어야 했는데, 그러지 못한 것에 대해 아쉬움이 남는다.)

 

J [2:46:52, 1wa 6 solve]

그 뒤로 오랫동안 조용했다. 나는 G를 잡다가 포기하고 B를 생각하다가 J로 넘어왔고, 시나엘 친구는 K를 잡았다. A를 풀었던 친구는 F, L에 대한 풀이를 생각하였지만 결과적으로는 풀지 못했다. 나는 B에서 풀이를 찾지 못해 2시간쯤에 J로 넘어와서 풀이를 찾기 시작했다.

문제는 어떠한 배열이 주어지고, 해당 배열에서 k개의 구간으로 나누는 입력이 들어온다. 이후 해당 구간별로 값들을 구간 내 최솟값과 최댓값 사이의 값으로 변경을 할 수 있는데, 이때 최종 변경된 형태가 오름차순의 형태를 갖추고 있어야 한다. 이때 값 x의 개수를 c_x라고 한다면 max(0, 이후 c_x - 이전 c_x )의 합이 최소가 되도록 하는 조합을 찾고 그때 해당 값을 구하는 문제였다.

 

설명이 조금 복잡해서 이해하는데 시간이 조금 걸렸다. 특히 문제에선 비내림차순이라고 설명하였기에 내림차순이 아닌 모든 형태를 의미하는 줄 알았는데 사실 같거나 증가하는 형태의 오름차순을 의미한 것이었다.

 

이 문제의 핵심은 c_x의 차이가 아닌 변경 이후의 값에 변경 전의 값을 뺀 값이라는 것인데, 이는 즉 특정 값의 개수가 줄어드는 건 상관없지만, 늘어나는 것은 최대한 최소로 돼야 된다는 말이다. 여기서 우리는 이미 존재했던 값들로 변경을 하면서 남은 값이 없을 경우 존재했던 값들 중 임의의 값 하나로 몰빵 해주면 된다는 것을 알 수 있다.

 

이러한 점을 모두 고려하면, 입력으로 들어온 값들을 우선순위 큐에서 오름차순으로 뽑아주고, 구간별로 하나씩 빼면서 구간의 max보다 우선순위 큐에 있는 값이 크다면 해당 구간의 남은 값들은 임의의 값으로 대체하는 형태로 코드를 구성해 주면 된다.

 

설명이 좀 이상하니 코드를 통해 이해하길 바란다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
ll A[200010];
vector<ll>B;
ll l[200010];
ll min(ll a,ll b){
    return a>b?b:a;
}
ll max(ll a,ll b){
    return a>b?a:b;
}
vector<pair<ll,ll>>st;
priority_queue<ll>pq;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> A[i];
        B.push_back(A[i]);
    }
    for(int i=1;i<=k;i++){
        cin >> l[i];
    }
    sort(B.begin(),B.end());
    B.erase(unique(B.begin(),B.end()),B.end());
    // for(int i=0;i<B.size();i++){
    //     cout << B[i] << ' ';
    // }
    // cout << "\n";
    for(int i=1;i<=n;i++){
        A[i]=lower_bound(B.begin(),B.end(),A[i])-B.begin()+1;
        pq.push(-A[i]); // 최솟값
    }

    ll mn=1e18,mx=-1;
    ll idx=1;
    for(int i=1;i<=k;i++){
        mn=1e18,mx=-1;
        for(int j=idx;j<idx+l[i];j++){
            mn=min(A[j],mn);
            mx=max(A[j],mx);
        }
        st.push_back(make_pair(mn,mx));
        idx+=l[i];
    }
    for(int i=1;i<k;i++){
        st[i].first=max(st[i].first,st[i-1].first);
    }
    for(int i=0;i<k;i++){
        if(st[i].first>st[i].second){
            cout << -1;
            return 0;
        }
    }
    ll ans=0;
    for(int i=0;i<k;i++){
        while(!pq.empty() && -pq.top()<st[i].first)pq.pop();
        for(int j=0;j<l[i+1];j++){
            if(pq.empty() || -pq.top()>st[i].second){
                ans+=l[i+1]-j;
                break;
            }else{
                pq.pop();
            }
        }
    }
    cout << ans;



}

처음에는 이러한 풀이를 내면서 세그먼트 트리를 활용하면 되겠다고 생각해서 세그먼트 트리를 구현하다가 다 구현해보고 보니 세그먼트 트리를 사용하지 않음을 깨닫게 되고 우선순위 큐만 활용한 코드롤 다시 작성하였다. 

 

남은 시간 동안은 B를 계속 생각해 보았지만 결국 풀지 못하였고, 대회 종료 후 에디토리얼을 보니 이분탐색을 이용한 문제였음을 알게 되며, 이 문제를 대회 중에 풀지 못한 것에 많은 아쉬움이 남는다.

 

에디토리얼에서 예상한 난이도이다. 

출제자의 예상 난이도이다 보니 실제와는 차이가 있지만 얼추 비슷한 거 같다. 내가 푼 J는 다른 참가자분들이 어려웠다고 하시는 거 봐선 플 4에서 높게 주면 플 3,2까지도 가능할 것으로 보인다. 이러한 점에서는 높은 티어의 문제를 풀었다는 점에서 기뻐할 수도? 있지만 정작 그보다 쉬운 B를 풀지 못한 것에 대해 많은 아쉬움이 있어 본선에 가서는 이러한 아쉬움 없이 후회 없는 결과를 만들고 싶다.

 

---

2026-06-29

 

ucpc 본선 진출자 명단이 공개 됐다. 

 

결과적으로 본선에 진출했다. 사실 학교 팀으로 출전한 것이기에 당연히 붙을 것이라고 예상은 했지만 성적이 그렇게 좋지는 않아 혹시나 떨어지지는 않을까 긴장하긴 했다.

(학교 팀은 일반 팀 40팀을 제외한 팀 중 같은 학교 인원으로 한 팀에서 선발하는 룰로, 학교당 1등 팀을 총 15팀 선발하는 제도이다. 즉 학교에서 1등 하더라도 학교팀으로 15등 안에 들지 못하면 본선에 못 간다는 소리다.)

 

 

번외로 이후 관계자이신 정휘 님이 말씀해 주시길, 우리 팀이 학교 1등 전형으로 올라온 팀 중 1등이라고 한다.

 

 

 

 

첫 ucpc였는데 결과에 만족하지는 않지만, 그래도 좋은 경험이었고 본선에서는 더 좋은 모습을 보여서 최종적으로 수상도 할 수 있도록 열심히 해보려고 한다.

 

모두들 UCPC 예선 수고 하셨고, 본선 진출자 분들은 7/12 카이스트에서 뵙겠습니다!