Uni-CODE 2021 출제/검수 후기

2021년 11월 27일 토요일 오후 1시부터 5시까지 4시간동안 제 3회 유니스트 알고리즘 프로그래밍 대회인 Uni-CODE 2021이 개최되었다. 출제, 검수진으로는 leejseo, queued_q, wbjeon2k, jh05013, koosaga, cs71107, junie 그리고 내가 참여했다.

문제는 여기에서 확인할 수 있다.

총평

우선 올해는 모든 문제를 영어로 출제하였다. 문제를 번역하는 과정이 제일 힘들었던 것 같다...

난이도는 예상보다 어려웠다. 그럼에도 참가자들이 모두 문제를 잘 풀어서, H를 제외한 모든 문제가 대회 중에 해결되었다. 문제 해결 분포도 꽤나 마음에 들었고, 당일 노쇼를 제외한 모든 참가자들이 적어도 1문제는 해결하였다. 다만, 작년에 비해 신청자 대비 참가율이 너무 낮았는데, 이를 끌어올릴 방법을 생각해야할 것 같다.

A. Guessing Answers (queued_q)

이 문제의 첫 아이디어는 정답과, 맞은 문제수가 주어질 때, 점수를 계산하는 문제였다. 그러나 조금 더 재미있는 문제를 내자는 의견과 함께, 정답과 맞은 문제가 주어질 때, 제출 답안을 재구성하는 문제로 바뀌었다. 다들 브론즈 1을 줬었는데, 그보다는 조금 어려운 실버 5로 티어가 매겨졌다. 내년엔 더 쉬운 문제를 내야할 것 같다...

 

여담으로 이 문제로 변경한 queued_q는 내년부터 A번 출제에 일절 관여하지 않는다고 한다(???).

 

 

풀이

간단하게, 1~5중에 정답으로 찍을 수 있는 수는 최소 2개이다. 가능한 수 중에 아무거나 찍으면 아무튼 재구성하는게 가능하다.

B. Physics Experiment (leejseo)

처음에 검수 코드를 올렸다가, 코딩 실수로 곤욕을 치루었던 문제이다. 간단하고 재밌는 문제였다. 처음엔 범위를 10만 자리로 주려고 했으나, 수를 string으로 받고, 다시 정수 배열로 바꾸는 것이 어려울 수 있다는 의견이 나와서 입력 범위가 조정되었다.

 

풀이

간단한 그리디 문제이다. 가장 낮은 자릿수부터 보면서, 자리올림을 할 수 있으면 모두 하면 된다.

C. Successful String (chunghan)

내가 출제한 문제이다. 처음에는 Successful String의 반대를 구하는 문제였다. 출제 당시 실버 3이라고 예상했으나, 문제가 달라지면서 예측 너무 잘못했다. 그럼에도 대회 당시에서 사람들이 꽤 많이 해결한 문제 중 하나다.

 

풀이

어떤 위치 i를 잡고, i 이전에 나타나는 연속한 두 문자가 같은 위치중 가장 오른쪽에 있는 것을 p라 하자. 그럼 왼쪽 끝은 p이전이라면 어디든지 가능하다.

또는, Successful String이 아닌 것들의 개수를 구하고, 전체 substring의 수에서 빼는 풀이도 존재한다.

D. Subnumber Sum (chunghan)

내가 출제한 문제이다. 문제 출제나 검수 과정에서 크게 어려운 점은 없었던 것 같다. DP가 꽤나 재미있다고 생각했는데, 실수하기도 좋은 문제였고, 대회 당시에는 E와 비슷하게 풀렸던 것으로 기억한다.

 

풀이

DP테이블을 다음과 같이 정의하면 문제를 해결할 수 있다.
D[i][j] = 오른쪽에서부터 i번째까지의 digit들에 대해, j개와 i-j개를 선택해서 만든 부분수의 합의 최대

E. Miswritten DFS (queued_q)

트리 DP를 이용해서 해결할 수 있는데, 그렇게 쉽지는 않았던 것 같다. 전체 방문 횟수가 $2^{100000}$까지 갈 수 있는 반면에, 입력 K는 $10^{18}$까지라, 이를 잘 처리해줘야하는게 제일 까다로운 문제이다. 이것 때문에 다들 많이 틀렸다 ㅎㅎ..

 

풀이

D[u] = u를 루트로 하는 서브트리에 방문한 횟수 라고 정의하면 이를 이용해서 어떻게 문제를 잘 해결할 수 있다. 사실 풀이를 글로 적기가 어려워서, 문제를 해결했던 코드로 대체한다.

ll solve(ll u, ll cnt) {
    if (cnt == 1) return u;
    cnt--;
    int l = chd[u][0], r = chd[u][1];
    if (cnt <= D[l]) return solve(l, cnt);
    cnt -= D[l];
    if (cnt <= D[l]) return solve(l, cnt);
    cnt -= D[l];
    if (cnt <= D[r]) return solve(r, cnt);
}

F. Two Dots (chunghan)

내가 출제한 문제이다. facebook에서 Two Dots광고를 보고 아이디어를 얻어 출제했다. 검수 과정에서 앳코더에 기출 문제가 있다는 것이 밝혀졌고 식은땀을 뻘뻘 흘렸다.

 

풀이

색이 같은 두 점이 모두 경계에 있는 경우만 걸러서 생각해주면, 괄호 매칭문제와 똑같이 해결할 수 있다. 자세한 증명이나 설명은 생략한다(앳코더 풀이를 찾아보면 도움이 될지도...)

G. Vertex Merge Game (wbjeon2k, queued_q)

이 문제를 검수 하면서 너무 재밌는 문제라고 생각했다. 문제에서 사용하는 알고리즘이나, 그 형태의 특징을 정확히 이해하지 않으면 풀 수 없는 문제라고 생각한다.

 

풀이

Maximum spanning tree(MST)를 먼저 구하자. 그러면 정점을 어떤 두 그룹으로 나누더라도 그 두 그룹을 잇는 MST의 간선이 항상 존재한다. 웅배가 항상 최대 점수를 얻을 수 있으므로, 윤이의 전략 또한 자신의 점수를 최대화 하는 것이 이득이다.

H. Rock Paper Scissors Strategy (queued_q)

어려운 문제였고, 검수할때도 잔실수를 찾느라 정해를 짜는데 시간이 꽤 오래걸렸다.

 

풀이

각 사람의 전략을 $(ax + b) \mod 3$으로 수식화 할 수 있다. 두 사람이 비겼다면, $a_1 x_1 + b_1 - a_2 x_2 - b_2 = 0$, 어느 한 사람이 이겼다면 $a_1 x_1 + b_1 - a_2 x_2 - b_2 = 1$, 세사람이 모두 비겼다면 합이 0, 어느 한 사람 또는 두사람이 이겼다면, 두 사람이 겨루어서 이긴 식 두개로 표현할 수 있다.

 

이렇게 연립방정식으로 행렬로 표현해주고, mod 3에서 가우스 소거를 진행하여 rank를 구하면 답을 구할 수 있다.