UCPC 2020이 어제(8월 1일) 성공적으로 개최되었습니다.
저는 Call for Tasks를 통해 문제를 출제하였고, 문제 출제와 관련된 후기와 풀이를 정리하고자 합니다.
서론
대학생이 아니라서 대회에 참가하지 못하는 아쉬움을 달래기 위해 Call for Tasks를 통해 문제를 출제했습니다.
제가 출제한 문제는 본선 K. 데이터 제작입니다.
문제는 간단합니다.
정점 $N$개, 간선 $M$개, 면이 $K+1$개인 평면 그래프를 만드는 문제
평면 그래프를 단순히 만들기만 하면 재미가 없으니까 좌표 범위 제한을 빡세게 줬습니다.
대회에서는 5팀, Open Contest에서는 0팀이 풀었습니다ㅠㅠ
출제 계기
지난 겨울에 동아리 프로젝트를 할 때 성능 테스트를 위해 평면 그래프 데이터가 필요한 적이 있었습니다. 그 당시에 저는 평면 그래프를 이쁘게 만들 방법이 딱히 떠오르지 않았고, 그래서 결국 점을 랜덤하게 찍고 들로네 삼각분할을 했었습니다.
그때부터 이 문제를 생각하고 있었고, 결국 UCPC에 출제했습니다.
위에서 언급했듯이 평면 그래프를 그냥 만들기만 하면 문제가 너무 쉽고 재미도 없습니다. Call for Tasks 제출 당시에는 좌표 범위 제한을 2000으로 줬는데 검수 도중 좌표를 1부터 79까지만 쓰는 풀이가 나와서 문제가 더 어려워졌습니다.
구데기인가?
저는 Constructive 문제를 혐오합니다.
그래서 그런지 제 문제가 구데기라고 욕 먹고 채택이 되지 않을 것이라고 생각했고, 본선 문제로 채택되었다는 이메일을 받게 되어서 놀랐습니다.
대회 종료 후에도 주변의 평가가 꽤 좋았던 것으로 보아 구데기는 아닌 것 같네요.
문제 세팅
당연히 데이터는 만들기 쉽습니다.
- generator에서는 정수 3개 찍고
- validator에서는 정수 3개 검증하고
- 코너 케이스도 빽빽한 그래프랑 간선 얼마 없는 그래프만 몇 개 넣어주면 됩니다.
checker에서는 문제에 나와있는 6개의 조건만 검사해주면 됩니다. $O(M^2)$ 정도에 Naive하게 하면 됩니다.
제 절망적인 작문 실력때문에 디스크립션 작성이 제일 힘들었습니다. 도와주신 운영진 및 검수진분들 정말 감사합니다…
풀이
self loop와 multi edge가 없는 평면 그래프에서는 $V-E+F=C+1$이 성립합니다. $N=V,M=E,K=F-1$이므로 $N-M+K=C$가 성립합니다.
$C = 1$이라면 열심히 Connected Graph를 만들어주면 되고, $C \neq 1$이라면 $C-1$개의 정점을 제외한 나머지 정점들로 Connected Graph를 만든 뒤 $C-1$개의 정점을 다른 곳에 뿌려주면 됩니다.
self loop와 multi edge가 없는 평면 그래프에서는 $E \leq 3V-6$이 성립합니다. 그리고 등호는 모든 Face가 삼각형일 때 성립합니다. Connected Graph를 만드는 것은 $3000$개의 정점과 $9000-6$개의 간선으로 이루어진 그래프를 만든 뒤, 정점과 간선을 적절히 지우는 것으로 구현할 수 있습니다.
즉, 적당히 큰 삼각형을 만들고 삼각형 내부에 $3000-3$개의 점을 더 찍고, 삼각형으로 다 쪼개주면 됩니다.
범위 제한 = 2000
원래는 범위 제한이 2000이였습니다. 이 경우에는 아래 그림처럼 작은 삼각형을 하나 만든 뒤, 하나씩 확장하는 방식으로 구현해주면 됩니다. 점 3개 당 범위가 2씩 늘어나기 때문에 2000 이내에 모든 점을 넣을 수 있습니다.
범위 제한 = 79
$(1, 1), (1, 79), (29, 2)$에 점을 찍어서 큰 삼각형을 만들어줍시다.
- $y = 78$인 점은 1개
- $y = 77$인 점은 2개
- $y = 76$인 점은 3개
- …
- $y = i$인 점은 79-i개
의 점을 삼각형 내부에 넣어줄 수 있고, 점의 최대 개수는 $\frac{78 \times 79}{2}+3 = 3084$로 3000개의 점을 넣기에 충분합니다.
간선은 아래 그림처럼 넣어주면 됩니다.
점 3000개 찍고 보로노이(or 들로네 삼각분할)를 돌린 팀도 있었습니다.
난이도
풀이 방송을 보시면 아시겠지만, 저는 처음에 Gold 1을 예상했습니다. 검수진분들은 Diamond 4~5라는 의견을 내셨고, 8월 2일 오전 1시 26분 기준 solved.ac 난이도는 Diamond 3입니다.
역시 출제자의 난이도 의견은 믿을게 못 됩니다.
기타
이번 UCPC 운영을 지켜보면서 대회 운영이나 문제 세팅, 출제와 관련해서 많은 것을 배웠습니다. 나중에 제가 직접 대회를 운영하게 된다면, 이번 UCPC의 기억을 되살려 원활하게 잘 운영을 할 수 있도록 노력해야겠습니다. (아직은 전대프연 회장 할 생각 없습니다ㅡㅡ)