2023 Sogang Programming Contest 검수 후기

11월 초에 열렸던 대회 후기를 이제서야 쓰는 게 좀 이상하지만, ICPC Seoul Regional 본선 + INU 코드페스티벌 2023 출제/운영 + 3학년 기말고사라는 말도 안 되는 일정 때문에 어쩔 수 없었다. 살면서 이렇게 바빴던 적이 없는 것 같다. (사실 글을 쓰는 지금도 기말고사가 안 끝났다...)

10월 10일에 검수진으로 선발되어 Discord 방에 들어갔는데, 다른 검수자분들 라인업(bnb2011, jk410, mjhmjh1104, snrnsidy, utilforever)을 보고 경악했다. 심지어 나는 검수 경험도 없었기 때문에, 내가 여기에 있어도 되는가.. 나를 왜 뽑으셨을까.. 등등 오만가지 생각을 하다가, '일반인의 시선이 궁금하신 거구나!' 라는 결론을 냈고 브실골 문제의 난이도 판독기가 되어 드리기로 결심했다. 검수는 10월 16일부터 시작됐고, 그동안 작년 기출문제를 풀며 기다렸다.

이미 공식 풀이가 잘 쓰여있어서, 검수하면서 느낀 점을 간략히 정리해두려고 한다.

---

Master Division

A. Knob

단순 구현 문제. 브론즈 문제는 뻔한 것을 요구해야 하면서도 이미 너무 많은 문제가 있어서, 문제 만들기 힘드셨겠다는 생각이 들었다.

B. donstructive

큰 수가 가운데로 오게 배치하면 되는 문제. 뭔가 Codeforces A~B번에 등장할 것 같은 문제였다.

C. 내 집 마련하기

$2xy<=x^2+y^2$임을 이용하면, 주어지는 구간을 정렬했을 때 최적이 된다.

D. 서로소 싫어

$x$ -> $xy$ -> $y$를 만들면 되는 문제. 처음에 홀짝성으로 접근하다 말려서 G5를 주었는데, 예상 난이도는 S2~1 정도였다.

E. 어? 금지

dp+이분탐색 문제. 개인적으로는 생소한 태그 조합이었는데, dp 경험이 많은 분들께는 전형적인 느낌의 문제였다고 한다. 역시 dp 연습을 많이 해야겠다...

F. Rush & Slash

Union-Find 문제. 잡초 위치의 중복 여부에 따라 답이 달라질 수 있어서 지문 수정 요청을 했던 기억이 있다. 사실 이런 건 내가 Codeforces Polygon을 사용할 줄 알았다면 눈치껏 스스로 수정할 수 있던 거였는데, 검수 당시에는 Polygon 사용법을 잘 몰랐다. (이런 툴이 있는지도 잘 몰랐다..)

G. 순열과 연산

애드 혹+case work 문제. 검수할 때 적당한 관찰로 case work 없이 거의 brute force에 가까운 풀이가 통과되는 것을 발견했는데, 이것도 정해로 두기로 결정됐다. 참가자분들이 이 풀이로 많이 AC를 받을 것 같아서 예상 난이도를 G1로 주었는데, 실제로는 P4가 매겨졌다..

H. 같은 풍경

기하학 문제. solved.ac 8각형 지표에서도 기하학이 제일 움푹 파여있는데, 의외로 이 문제는 답이 빨리 보였다. 이런 문제는 특히 부동 소수점 오차에 유의해야 하는데, 웬일로 한 번에 AC를 받길래 의심되어 반례를 열심히 찾았다. 이것도 Polygon에서 Stress를 돌려보면 쉽게 찾을 수 있었지만, 이런 기능을 몰라서 다른 검수자분의 AC 코드와 섞어서 로컬에서 반례를 찾았다.

대충 이런 코드를 써서 찾았다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second
#define minn(a,b) a=min(a,b)
#define maxx(a,b) a=max(a,b)

ll ccw(pii a,pii b,pii c){
    ll x[3]={a.x,b.x,c.x},y[3]={a.y,b.y,c.y};
    return x[0]*y[1]+x[1]*y[2]+x[2]*y[0]-(y[0]*x[1]+y[1]*x[2]+y[2]*x[0]);
}

double meet(pii a,pii b){
    double ret=a.first;
    ret-=(double)(a.x-b.x)/(double)(a.y-b.y)*(double)a.y;
    return ret;
}

struct point{
    ll x,y;
    void input(){
        cin>>x>>y;
    }
};
const ll INF=(ll)9e18;
ll ccw(point a,point b,point c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
ll myFloor(ll a,ll b){
    if (b<0){
        a=-a;
        b=-b;
    }
    if (a%b==0)
        return a/b;
    if (a<0)
        return a/b-1;
    return a/b;
}
ll myCeil(ll a,ll b){
    if (b<0){
        a=-a;
        b=-b;
    }
    if (a%b==0)
        return a/b;
    if (a<0)
        return a/b;
    return a/b+1;
}

int get_ans(int n,int m,vector<pii> tree, vector<int> woojin,pii hoyoung){
    sort(tree.begin(),tree.end(),[&](pii a,pii b){return ccw(a,b,hoyoung)>0;});
    double mx=2e9,mn=-2e9;
    for(int i=1;i<tree.size();i++){
        pii a=tree[i-1],b=tree[i];
        int x=a.x-b.x,y=a.y-b.y;
        if(!y)continue;
        if(ccw(a,b,hoyoung)*(y/abs(y))<0)mx=min(mx,meet(a,b));
        else mn=max(mn,meet(a,b));
    }
    int ans=0;
    for(int i=0;i<m;i++){
        ans+=mn<woojin[i]&&woojin[i]<mx;
    }
    return ans;
}

point HY;
point P[100001];
int get_ans2(int n,int m,vector<pii> tree, vector<int> woojin,pii hoyoung){
    HY={hoyoung.x,hoyoung.y};
    for (int i=1; i<=n; i++)
        P[i]={tree[i-1].x,tree[i-1].y};
    sort(P+1,P+n+1,[&](point a,point b)->bool{
        return ccw(HY,a,b)<0;
    });
    ll l=-INF,r=INF;
    for (int i=1; i<n; i++){
        ll tmp1=P[i].x*P[i+1].y-P[i+1].x*P[i].y,tmp2=P[i+1].y-P[i].y;
        if (!tmp2)
            continue;
        if (tmp2>0)
            maxx(l,myFloor(tmp1,tmp2));
        else
            minn(r,myCeil(tmp1,tmp2));
    }
    int ans=0;
    for(auto x:woojin)
        ans+=(l<x&&x<r);
    return ans;
}

int main(){
    ll cnt=0;
    std::random_device rd;
    std::mt19937 gen(rd()),gen2(rd()),gen3(rd()),gen4(rd());
    std::uniform_int_distribution<int> dis(2,2);
    std::uniform_int_distribution<int> xx(-1e9,1e9);
    std::uniform_int_distribution<int> yy(1,1e9);
    while(1){
        pii hoyoung={0,-1};
        int n=dis(gen4),m;
        vector<pii> tree(n);
        for(int i=0;i<n;i++)tree[i]={xx(gen4),yy(gen4)};
        vector<int> woojin;
        double MM=meet(tree[0],tree[1]);
        if(abs(MM)>1000000005.0)continue;
        int M=MM;
        for(int i=max(-1000000000,M-2);i<=min(1000000000,M+2);i++)woojin.push_back(i);
        for(int i=0;i<3;i++)woojin.push_back(xx(gen4));
        m=woojin.size();
        int a=get_ans(n,m,tree,woojin,hoyoung);
        int b=get_ans2(n,m,tree,woojin,hoyoung);
        if(a!=b){
            printf("%d %d %d %d\n",n,m,hoyoung.x,hoyoung.y);
            for(auto [x,y]:tree)printf("%d %d\n",x,y);
            for(auto i:woojin)printf("%d ",i);
            return 0;
        }
        else {
//            printf("\n-----------------------------\n");
//            printf("%d %d %d %d\n",n,m,hoyoung.x,hoyoung.y);
//            for(auto [x,y]:tree)printf("%d %d\n",x,y);
//            for(auto i:woojin)printf("%d ",i);
//            printf("\n-----------------------------\n");
//            printf("%d %d %d\n",a,b,++cnt);
            if(cnt%1000000ll==0)printf("%lld\n",cnt);
            cnt++;
        }
    }
    return 0;
}

---

Champion Division

A. 내 집 마련하기

Master Division C번과 같은 문제.

B. 댄스타임

출제 의도는 수학이었지만, dp 풀이가 더 쉽게 보였던 문제였다.

C. 심심한 마루

기하학+누적합 문제. 누적 합을 안 쓰는 풀이도 통과돼서, 난이도 의견이 B1~G5로 분분하다.

D. 삼월 초하루

BFS+구현 문제. 원래 정해는 constructive를 의도하셨고, Hard 버전으로 $N=500000$을 생각하셨다는데... 나는 Hard 나왔으면 못 풀었다. 지금 버전도 구현이 꽤 까다로운 편이었다. 뭔가 코딩테스트에 나올 것 같은 느낌의 문제였다.

E. 김밥천국과 도로지옥

dijkstra 응용문제. 12를 가지고 무언가 해야 한다는 생각을 계속하고 있었으면서도, 푸는 데 가장 오랜 시간이 걸렸던 문제였다. 왜 그랬을까..?

F. 재미없는 문제

약 팔기와 비슷한 문제. 지문에 수열 $A$가 정수라는 조건이 없어서 추가 요청을 했다. 이런 게 사소하면서도 자칫하면 채점이 잘못되어 억울한 사람이 생길 수 있어서, 검수할 때 지문을 평소보다 꼼꼼히 읽었던 것 같다. 개인적으로 약 팔기 문제에 구현 한 스푼이 추가된 거 같은데, 왜 난이도가 P5로 같은지 모르겠다.

G. 직각삼각형의 동생은?

segment tree+offline query 문제. 나는 정해 태그와 다르게, 점 $(a_i, b_i)$를 $(a_i, \frac{a_i}{b_i})$ 와 같이 ($x$좌표, 기울기)로 바꾼 후 무지성 2D segment tree를 써서 풀었다. Master H번 문제와 마찬가지로 부동 소수점 오차가 생길 것 같아서 로컬에서 반례를 찾아봤는데, 하루종일 돌려도 반례가 안 나와서 도움을 요청했더니 다행히 출제자분께서 찾아주셨다.

H. 렉시오

열심히 풀어봤지만.. 내 실력으로는 역부족이었다.

---

대회 당일

생각보다 집에서 멀지 않아서 바로 놀러 갔다. 코로나+입대로 오프라인 행사에 참여해본 적이 없어서 랭커분들을 직접 뵙고 싶은 마음도 있었고, 12/2에 열릴 교내 대회 운영도 처음 해보는 거라 실제로 오프라인 대회가 어떻게 돌아가는지 눈으로 직접 보고 싶었다.

조언을 믿고 일단 오르막을 무작정 올랐는데, 주말이라 그런지 정문 빼고 입구가 다 잠겨있어서 5분 정도 헤맸다. 도착하니 다들 반갑게 맞이해주셨고, 간식으로 준비해주신 빼빼로를 먹으며 기다리다 대회가 시작됐다.

문제가 풀릴 때마다 푸신 분 자리에 풍선을 달아 드렸는데, 초반에 제출이 많아 일손이 모자라서 대신 열심히 풍선을 달아 드렸다. 대회 중반에도 질문이 종종 올라왔는데, 질문을 최소화하기 위해서는 지문을 최대한 친절히 써야겠다는 생각이 들었다. 후반에 Master 1위분이 압도적인 폼으로 All solve를 하셨는데, 내가 옆자리에 있었다면 수많은 풍선에 기가 눌려 힘들었을 것 같다.

---

느낀 점

확실히 대회 역사가 깊어서 그런지, 운영이 되게 체계적이라는 느낌이 들었다. 디스코드에서 문제마다 채널을 나눠서 소통하고, 데이터는 Codeforces Polygon, 검수 현황은 Google Spreadsheet, 풀이 슬라이드 작성은 Overleaf, 대회 중 질문은 Discord Webhook으로 관리하는 등 정해진 틀이 있어서 정말 편했다. 대횟날에 스코어보드가 프리즈된 후 여유가 생긴 틈에 이런 대회 운영 방법들이나 예산, 상금 규모, 풍선 가격, 특별상 가격 등등 이것저것 여쭤봤는데 친절하게 알려주셔서 교내 대회 운영에 정말 많은 도움이 되었다.

여담으로 대회가 끝나고 뒤풀이에서 출제진 분들께 "혹시 절 왜 뽑으셨나요..?"라고 물어봤는데, 사실 마지막까지 나와 다른 분 중에서 고민하시다가 '경력 없는 신입은 어디서 경력을 쌓나?'라는 마음으로 날 뽑아주셨다고 한다...ㅠㅠ 이 얘기를 듣고 정말 감동했다.

좋은 경험 시켜주신 서강대학교 출제진 여러분, 감사합니다!