UCPC 2018 출제 후기

0. 잡담

ucpc 본선이 끝나고 나서 후기를 쓰려고 다짐했지만, 그 사이에 일이 너무 많아서 2주나 지난 지금에서야 씁니다.

 그동안 프로그래밍 대회에 문제를 한 번 내보고 싶었는데, 큰 대회는 문제를 못내고, 코포나 탑코더는 레이팅이 걸려있어서(..) 가장 부담이 적어보이는 ucpc에다가 문제를 만들어 넣었습니다. 결과적으로 매우 만족스러운 문제들이 나왔기 때문에, 올해 국내대회중에서는 가장 좋은 대회가 되지 않을까 합니다.

 쓸 내용이 중요하지도 않고 해서, 생각나는대로 써보려 합니다. 

1. 인터넷 예선

1) 문제

 데이터를 만드는 일은 매우 쉬울 수도 있고, 매우 어려울 수도 있습니다. 그 차이는 매우 심해서, 30분만에 데이터가 만들어지는 문제가 있는가 하면, 하루 내내 만들어야 겨우 완성되는 경우도 있습니다. 가끔 하루 내내 만들어야 하는 문제를 30분만에 뚝딱하는 경우도 있는데, 이 경우 정해보다 쉽고 느린 코드가 통과되기도 합니다. 그래도 이번에는 데이터를 만들기 어려운 문제는 그리 많지 않은 것 같아 다행입니다.

 예선에서 데이터를 힘들게 만들어야 하는 문제는 &+ +&, 트리와 색깔 정도가 있습니다.

(1) &+ +&는 랜덤으로 대충 만들면 +&쪽에서 답이 0이 나와서 매우 위험합니다. 물론 공식 데이터에는 대부분 0이 아닙니다.

(2) 트리와 색깔은 쿼리문제기도 하고, 랜덤으로 하면 O(QN)에서 쉬운 커팅인 "subtree만 순회"같은 알고리즘이 뚫리는 경우가 있습니다.

2) 난이도

 인터넷 예선의 목표는 본선 진출팀 45팀을 고르는 것입니다. 때문에 당연히 상위권이라고 생각되는 팀들은 무시합니다. 단순히 45등 근처를 자르기 때문에 커트라인이 3문제에 박히거나, 올솔브에 걸리는 말도 안되는 일만 일어나면 됩니다. 때문에 질 좋은 문제를 본선에 내고, 상대적으로 떨어지는 문제를 예선에 낼 수 있었습니다.

 ICPC 인터넷 예선은 상황이 조금 다릅니다. 잘 하는 대학에서 절반을 구별해야 되고, 평범한 대학들을 구별해야 하고, 못하는 대학들도 구별해야 합니다. 규칙이 꽤나 복잡하기 때문에 예선 난이도 선정이 힘들 것 같습니다. 그래도 문제가 12문제인데 커트라인이 3문제에 걸리는 건 아니지 않나 싶습니다...

(이유는 잘 하는 대학에서는 대학 내 참가자 중 절반을, 평범한 대학은 평범한 커트라인을, 못하는 대학은 추가합격자가 있기 때문입니다. )

 제가 생각했던 45등팀은 기초적인 알고리즘과 약간의 구현력 정도만 있는 정도를 예상했습니다. 코포로 따지만 라임 정도? 하지만 커트라인은 예상을 넘어선 6문제에서 걸렸습니다. 제가 PS를 한 4년동안 세상이 많이 바꼈다는 것과, 지금도 빠르게 바뀌고 있다는 것을 느끼고 있습니다.

3) 문제별 잡담

 아래 적힌 내용은 기억력의 한계 때문에 사실 관계가 맞지 않을 수 있다는 점, 양해 부탁드립니다.

(1) 수학은 체육과목입니다. (184팀)

 가장 쉬운 문제입니다. 가장 쉬운 문제가 필요한 이유는, "ucpc라는 게 있다는데 나가볼래?" 하는 입문자들을 위한 문제입니다. 입문자들이 문턱에서 좌절하지 않도록, 쉬운 문제를 제공해주어야 한다고 생각합니다.

(2) 카드 합체 놀이 (169팀)

 모든 팀이 맞왜맞을 외친 문제일 것입니다. 사실 이정도로 많이 풀릴지는 상상도 못했는데, 169팀이나 맞은 걸 보면 다들 감이 좋은 것 같습니다.

 출제진에 풀이가 2일 전에 도착하기도 했고 검토를 했는데도 이상한 부분이 꽤 있었지만, 작은 데이터에서 전수조사와 같았고 맞는 풀이 같아서 일단 출제했습니다. 끝나고 출제자의 증명을 boj slack에서 모두가 보완한 결과, 그래도 풀이는 맞다는 것을 증명할 수 있었습니다.

(3) UCPC는 무엇의 약자일까? (167팀)

 ntopia님이 예선 전날? 가장 쉬운 문제를 준비하려고 했습니다. 하지만 사람들이 단어의 개수 문제에서 엄청나게 삽질을 하고 있다는 것에서 볼 때, 문자열 입력 및 처리는 수학 문제보다 어려운 것 같습니다. 그 결과 이 문제가 3번째 문제가 되었습니다.

 보통 문제 출제는 C언어는 금방 배우거나, 배운 지 n년은 지난 사람들이 하게 됩니다. 때문에 매우 쉬운 문제는 난이도 평가가 쉽지 않은 것 같습니다.

(4) 나무 탈출 (121팀)

 쉬운 게임 문제입니다. 문제를 어느정도 풀어본 사람이 아니라면 어려울 법한 문제이지만, 그래도 121팀이나 해결하였습니다.

 dfs/bfs를 구현할 수 있어야 하고, 동시에 높이 합의 홀짝성만이 중요하다는 것을 알아차려야 문제를 해결할 수 있습니다. 두 가지 능력을 모두 가진 팀이 121팀이나 된다는 것에서, 실력이 뛰어난 팀이 점점 많아지고 있다는 것을 알 수 있습니다.

(5) 잘못 구현한 에라토스테네스의 체 (88팀)

 저는 수식이 많은 문제를 꺼려하기 때문에 이런 문제를 매우 싫어합니다. 그와는 별개로 좋은 문제긴 합니다..

 제가 풀 때는 어떻게든 루트로 비볐는데, 그것보다 더 쉽고 좋은 방법이 많이 있는 것 같습니다. 때문에 88팀이 해결한 것은 꽤 놀라웠습니다.

 

 TMI) 잘못 구현한 디닉 문제와 이름이 비슷한 문제입니다.

(6) 트리와 색깔 (48팀)

 커트라인에 걸린 문제입니다. 저에게는 자료구조 양산형 문제로 느껴집니다만, 처음 보는 분들에게는 매우 좋은 자료구조 연습문제입니다. 다만 검색하면 답이 나오지 않을까 하는 우려를 했습니다.

 간단한 자료구조를 다루지 못하면 본선 진출이 어려웠다는 면에서 아쉽긴 하지만, F를 틀린 팀들 중 다른 문제를 풀어 진출한 팀도 꽤 되는 면에서는 다행입니다.

 초기 정해는 HLD였지만, 자료구조 문제가 다 그렇듯 의도한 것보다 쉽게 풀리는 경우가 매우 많습니다.

(7) 피아의 아틀리에 ~신비한 대회의 연금술사~ (36팀)

 트리와 색깔과 함께, 본선 진출을 하기 위해서는 자료구조를 알거나, 코딩을 열심히 하거나 2지선다를 거는 문제였습니다. 물론 고인물들은 10분~15분만에 코딩해버리는 문제지만, 커트라인에 걸리는 팀들에게는 꽤나 도전적인 구현 문제가 될 것 같습니다. 제가 생각하는 가장 뇌를 안쓰는 방법은 9중반복문입니다. 물론 함수로 묶어야 덜 귀찮습니다.

 제가 기억하기로는 ainta님 코드가 0.2초에 돌았지만, 제한시간을 3초로 했습니다. 함수 내부에 vector<int>를 선언하면, 생성자-소멸자 호출때문에 시간초과가 나는 것으로 알고 있습니다.

+) 문제 규칙은 기존 게임과는 전혀 다른 형태입니다. 실제 게임 규칙은 과하게 복잡하기도 하고, 이미 알고 있는 사람에게 유리할 수 있습니다. 문제에 낼 만큼 쉽고,  게임에 맞게 변형해서 새롭게 만든 문제입니다.

 팀대회에서 코딩이 오래 걸리는 문제를 잡기에는 리스크가 큽니다. 문제 생각은 3명이 다같이 할 수 있지만, 코딩은 1명밖에 못하기 때문입니다. (이번 예선은 컴퓨터 3대였기 때문에 다르긴 합니다.) 때문에 잘하는 팀들은 코딩 노가다 문제를 최대한 많은 문제를 푼 뒤 코딩을 시작하게 되고, 상대적으로 느리게 풀리게 됩니다. 심지어 최상위권 잘하는 팀들에게는 이 문제보다 소각로가 더 쉬울수도 있어서 소각로를 먼저 풀기도 합니다. 하여튼, 코딩만 귀찮은 문제(ex. 17ICPC 대전 B)는 상위권을 믿으면 안됩니다. 그렇다고 팀대회에서 코딩 문제를 절대 계획 없이 코딩하지 말아주세요(중요).

(8) &+ +& (19팀)

 이제부터는 통과하신 분들 심심하지 말라고 출제한 느낌의 문제들입니다. 이 문제는 16 ucpc에 출제된 Xor of Sums과 아이디어가 비슷합니다. 각 자리를 따로 처리하고, 그 부분을 머지소트와 슬라이딩 윈도우로 처리합니다. 많은 분들이 시간초과로 고생하셨던 것 같습니다. (시간초과: 131회) 

 O(N lg^2 N)을 막기 위해 N이 10^6, 시간제한도 1.5초입니다. 대회에 많이 나가다보면 요구되는 능력 중 하나로 "알고리즘의 정확한 시간 맞추기"가 있습니다. 잘 하는 팀들은 O(N lg^2 N)의 시간초과를 예측했던 것 같지만, 대부분의 팀은 예측하지 못한 것 같습니다. 거기다가, lg^2에서 lg로 줄이는 것도 할 것이 매우 많아서 정해애 도달하는 사람은 많지 않았습니다.

(9) Split and Merge (17팀)

 저는 simple DP라고 생각했지만, 적게 풀린 것을 보면 쉬운 문제는 아니었던 것 같습니다. 조합론적 개념과 문제를 단순화하는 능력이 필요하기 때문으로 추측하고 있습니다. 문제를 바꾸고 바꾸면 0101.. -> 1010..의 가짓수를 구하는 문제(와 약간의 조합론)로 바뀌는데, 이게 문제로 나왔으면 더 많이 풀렸을 것 같습니다.

 처음 문제를 봤을 때는 2*1 2개가 붙어있을 수 없다?는 조건이 있었지만, 출제자 실수로 밝혀져 삭제됐습니다. 그래서 이 문제를 처음 봤을 때의 느낌은 어떤지 잘 모르겠습니다. (저 조건이 있어도 풀리긴 합니다만, 없는 것이 더 쉽고 좋은 문제입니다)

(10) 소각로 (13팀)

 가장 어려운 문제입니다. 같은 원소를 구간으로 관리한다는 흔한 테크닉과, 테크닉을 적용하기 위한 자료구조 기술을 보유하고 있으면 해결할 수 있습니다. 다만, 대회시간 3시간 이내에, 9문제를 풀고 남은 시간동안 이 문제를 푸는 것은 프로그래밍에 매우 익숙해져야 가능할 것입니다. 하지만 고인물들에게는 쉬웠는지, 퍼솔은 문제 (7)보다 먼저 나왔습니다.

 원래는 수호랑을 태우는 문제였나? 하지만 도덕적으로 옳지 않아서 수정하신 것 같습니다. 

2. 오프라인 본선

1) 문제

 예선에 비해 검수에 든 노력이 적어졌다는 느낌이 있었습니다. TV 동물농장은 ainta님이 대회 중에 검수를 끝냈고, 나머지들도 2명 이상 검수한 경우는 없었습니다. 하지만 결국 모든 문제에 검수가 붙었고, 터진 문제도 없는것으로 보아 다행입니다.

 대회에 나오는 12문제는 균형잡혀있어야 합니다. 난이도는 쉬운 문제부터 어려운 문제까지, 겹치는 분야는 없어야 하고, 코딩만 하거나 풀이만 생각하는 경우는 없었으면 좋겠습니다. 그런 면에서 ucpc에 나온 12문제는 꽤 만족스러운 균형을 이루고 있다고 자신할 수 있습니다.

 팀대회는 코딩이 하이리스크인 만큼 데이터가 뚫리는 일이 적긴 합니다만, 뚫리기 쉬운 문제가 있었던 것 같습니다. 대회중에 문제를 뚫으신 분들 제보를 받습니다.

 

2) 난이도

 본선은 난이도를 매우 고르게 주어야 합니다. 오프라인인 만큼 50팀이 모두 즐길 수 있어야 하고, 특히 수상권인 상위권은 등수를 확실하게 나눌 수 있어야 합니다. 난이도 배정을 상위권 문제를 4개, 나머지 문제들을 선형으로 잘 나눠서 한 것 같은데, 꽤 성공적인 것 같습니다. 한 가지 아쉬운 점은, F 문제를 n <= 500으로 했다면 대회가 더 재밌어지지 않았을까 싶습니다.

 출제진에서는 마지막날까지도 난이도를 조절했습니다. 대표적인 이유가 저와 ainta님의 난이도 평가 미스때문이지만, 그래도 제한을 늘리지 않고 참은 문제가 2개나 있습니다. 

3) 문제

(1) 아기 석환 뚜루루 뚜루 (50팀)

 ntopia님이 모든 팀이 풀 만한 문제를 만들어 넣었습니다. 아무도 낙오되지 않아 다행인 것 같습니다.

(2) 더위 피하기 (48팀)

 좌표 제한이 매우 크지만, T가 매우 작다는 것을 이용하면 쉽습니다. 좌표 제한이 매우 크지만, 필요한 것은 100정도? 하지만 그냥 map을 쓰면 시간초과가 난다는 소문이 있습니다. 문제에 "주어지는 모든 좌표의 위치는 서로 다르다"가 있었지만, 모르고 질문하신 분이 몇 팀 있었습니다.

 아쉽게 풀지 못한 2팀이 있지만, 그래도 대부분의 팀이 해결하였습니다.

(3) Thinking Heap (47팀)

 아이디어가 필요한 문제입니다. 조건을 만족하는 heap을 하나 만든 다음, 작은것부터 하나씩 추가하면 되겠습니다. 아이디어는 쉽지만, 그 아이디어를 생각하기는 경우에 따라 매우 어렵다고 느낄 수 있습니다.

 아쉽게 풀지 못한 3팀이 있지만, 그래도 대부분의 팀이 해결하였습니다. 출제진은 아이디어가 어려울 수 있다고 생각했지만, 참가자에게는 아니었던 것 같습니다. 때문에 풍선 개수가 모자라는 일이 발생했습니다.

(4) Make Similar (31팀)

 경우를 열심히 나누면 되는 문제입니다. 음수가 주어질 수 있다는 것이 문제에 숨어있기 때문에, 낚인 분들이 몇팀 있었습니다. 음수가 있기 때문에, 양수와 음수가 같이 있다면 0으로 만들 수 있다는 고찰을 해야만 쉽게 해결할 수 있습니다. 이 내용은 수학적 직감이 뛰어나면 찾을 수 있을지도?

 경우를 꽤 엄밀하게 나눠야 해서 어려운 문제가 되지 않을까 싶었지만, 예상외로 많은 팀이 풀어서 놀랐습니다.

(5) Piet (31팀)

 코딩노가다 문제입니다. 주어진 조건을 모두 구현하면 끝나는 문제입니다만, 역시나 대회시간 5시간 이내에 구현하는 것은 또 다른 문제입니다. 잘하는 팀들이 Piet을 늦게 잡았음에도 불구하고 퍼솔은 난이도에 맞는 순서에 나왔습니다.

 풀이가 막히면 그 사이에 이 문제를 코딩하면 되겠습니다. 특히 이번에는 풀이가 어려운 문제가 매우 많았기 때문에 계획을 잘 세우면 시간손해 없이 문제를 풀 수 있습니다.

(6) 성공 (24팀)

 최단경로 문제로 바꾼 뒤, 필요없는 연산을 줄이는 방식으로 문제를 해결해야 합니다. 언급한 두 단계 모두 난이도가 있기 때문에 어려운 문제입니다. 또한, 간선이 O(NMK) 정도인 BFS를 돌려야 하기 때문에 모든 간선을 만들면 시간초과나 메모리 초과가 날 수 있습니다. 그래도 확실히 예상보다 많이 풀린 문제입니다. 

 이 문제가 O(NM lg NM)으로 늘어나려다가 말았습니다. 처음 보면 신기하지만, 지금은 많이 쓰여서 익숙한 테크닉 하나를 쓰면 풀립니다.

(7) 간단한 문제 (14팀)

 퍼솔이 11분이었는데, 해결한 팀은 14팀이었습니다. 그만큼 많은 팀들이 이것때문에 시간 손해를 봤다고 생각할 수 있습니다. 이 문제는 IMO 1번에 나왔던 문제였고, 퍼솔팀은 문제를 알고 있었기 때문에 빨리 푼 것이었습니다. 출제자는 알았을 것 같지만 무시했고, 운영진은 아무도 몰랐기 때문에 이슈가 나오지 않았습니다. 수학적 귀납법으로 풀려는 시도를 하면 풀 수도 있지만, 수학경시 종류의 문제에 익숙하지 않다면 엄청나게 어려운 문제가 될 것입니다.

 스페셜저지가 약간의 이슈였는데, 아마 랜덤 소수 여러개로 분수들을 해싱해서 확인했던 것 같습니다. p*q^-1 (mod P)는 분수를 해싱하는 좋은 방법이고, 사칙연산도 성립합니다. (ex. 분수 2개를 더한 값의 해쉬값 == 분수 해쉬값 2개를 더한 값)

(8) 네트워크 해킹 (13팀)

 출제진에서는 간단한 트리dp라고 해서 쉬운 문제인 줄 알았지만, 전혀 쉬운 문제가 아니었습니다. 난이도 평가에서도 여론같은게 있어서 잘못 평가한 쪽으로 의견이 몰리는 경우도 꽤 있습니다. POI에 있는 문제였고, 때문에 쉽게 푼 팀이 꽤 있었습니다.

 간단한 트리dp치고는 경우가 너무 많았던 것 같습니다. 혹은 출제진쪽에서 문제를 대충 봤거나..

(9) 피아의 아틀리에 ~신비한 생명의 연금술사~ (6팀)

 고인물 테크닉 2개를 섞으면 풀리는 문제입니다. 2x2 합에 짝수/홀수 조건이 걸리는 문제는 자주 보이기도 하고, 잘 하는 팀들은 생각할 수 있는 내용입니다. 이 내용을 생각하고 조금 문제를 볶으면 offline dynamic connectivity로 풀립니다. 테크닉이 문제의 전부라서 모르면 못 푸는 문제가 되어버렸습니다.

 실제로 간선 추가-삭제가 일어나는 그래프에서의 offline dynamic connectivity에서는, 각 간선의 lifetime 구간을 구하여 문제를 해결합니다. 이 문제에서는 각 간선의 lifetime을 조건으로 주기 때문에 약간 쉬위지지 않았나 생각해봅니다.

 난이도를 높이기 위해 n을 10만으로 주는 것을 생각했지만, 문제가 너무 더러워지기 때문에 포기했습니다.

(10) 쉬운 최단경로 문제 (4팀)

 통곡의 벽인 B입니다. 제한부터 로그를 용납하지 않겠다는 N 5000, Q 10000 입니다. 원본 문제는 N^2Q로 풀렸지만, 난이도 조정 단계에서 convex hull이라는 조건을 쓰면 NQ로도 풀린다는 것을 발견하여 제한이 늘어났습니다. 때문에 lg를 붙인 팀들이 문제를 푸는 데 실패했습니다.

 문제가 크게 2개인데, 2개 모두 많은 노력을 해야만 O(N)으로 문제가 풀립니다. 때문에 기하에 익숙하지 않다면 풀 수 없는 문제가 되어버렸습니다. 하지만 퀄리티는 좋아서 기하의 최종 연습문제 정도로는 적당한 것 같습니다.

 

(11) TV 동물 농장 (1팀)

 우승팀을 가리는 문제가 되었습니다. 문제를 풀이에서 역산해서 만들었기 때문에 저는 난이도를 평가할 수 없었고, ainta님은 모 테크닉을 알고있다면 쉬운 문제라고 평가했습니다. 역추적은 최솟값 증명에 꼭 필요하기 때문에 추가했지만, 막상 대회에 들어가보니 역추적 부분이 매우 어려웠다고 합니다. 제가 의도한 풀이가 아니라면 구현이 어려워지거나, 문제를 풀지 못하는 것으로 보였습니다.

 우승팀은 이 문제에 10KB 넘게 코딩하고 AC를 받았습니다.

(12) Parentheses recover (0팀)

 첫 제출은 1시간 이내에 나왔고, 그 이후로도 73번의 "틀렸습니다"가 있습니다. 하지만 문제를 해결한 팀은 아무도 없었다는 것이 아쉬웠습니다. 개인적으로 많은 팀이 해결할 수 있을 것이라고 추측했지만, 완전히 빗나갔습니다. 문제를 잘 모델링하면 N^2에 쉽게 도달할 수 있을 것이라고 생각했지만, 모델링 부분이 너무 과하게 어려웠던 것 같습니다.

 N제한이 늘어난 문제입니다만, 늘리지 말았어야 했다고 생각하고 있습니다.

---

끝!