대회후기: UCPC 2020 본선

UCPC 2020 본선 문항

더 늦어지기 전에 본선 후기를 남긴다. 이미 뒷북 후기...

---

A: 전단지 돌리기

짧은 문제 description이었지만, 거리 $D$ 이하의 모든 노드에 전단지를 돌릴 수 있다는 말이 무슨 뜻인지 이해가 되지 않아 반복해 여러 번 읽어야 했다.

결국 가볼 필요가 없는 노드들을 찾아내기만 한다면, 나머지 노드들을 전부 포함하는 subtree의 모든 간선 길이를 왕복으로 지나가게 되므로, 간단하게 정답을 구할 수 있다. 갈 필요가 없는 노드들을 제외하는 동시에 필요한 간선 길이들을 세기 위해서, 모든 leaf node로부터 출발하여 루트(출발지)를 향해 거꾸로 올라오며 거리 $D$ 이상 올라온 시점부터 간선들의 길이를 더해주기 시작했다. 같은 간선을 두번 세 주지만 않으면 된다.

파이썬으로 풀었다.

---

B: 던전 지도

이번 문제도 description이 난해해서 해석에 시간이 많이 들었다. 문제를 해석한 이후, 풀이를 떠올리기까지는 그렇게 오래 걸리지 않았던 것 같다.

던전의 행 개수가 최대 $200000$이므로, 행의 개수에 대해 $O(n log n)$ 이하로 문제를 풀어내면 되었다. 따라서 이 문제는 바로 위의 행의 던전 도달 가능성 정보를 기반으로 그 아래 행의 던전 도달 가능성 정보를 $O(log n)$ 시간 이내로 찾아내는 문제가 되는데, 이는 한 행 내에서 던전 도달 가능 지점들이 항상 연속한 구간의 형태로 존재한다는 통찰을 바탕으로 해결 가능하다. 적절한 전처리만 해둔다면, 바로 위 행의 구간으로부터 다음 행의 구간을 빠르게 구할 수 있다. 우리의 경우, U 문자들의 위치를 미리 저장해두고 이진 탐색을 통해 해결하였다.

우리가 이용한 방법 외에도 구간의 양 끝을 왼쪽으로 미끄러트리며 문제를 해결하는 $O(n)$ 풀이도 가능하다.

---

C: 함수 복원

Nyso가 원순열 경우의 수를 잠깐 물어보더니, 알아서 잘 풀어줬다. 주어진 조건으로 생성되는 그래프의 특성을 기반으로, 사이클들을 잘 처리하면 되는 듯 하다.

---

L: 피자 배틀

오늘 제일 아쉬운 문제이다. 한시간에서 두시간 사이를 이 문제만 붙들고 있었지만, DP로 해결해야 할 것 같다는 감 이외에는 별다른 진전이 없었다. 대회 끝나고 정해를 본 이후 Nyso와 MathAmp가 말하기를, 생각하던 방법과 유사한 방향으로 풀린다고 한다. 하지만 결국 대회시간 이내에 해결하지 못한 문제이다.

---

총평

일단 대회가 끝나고서는 전반적으로 팀의 분위기가 다운되어 있었다. 세 문제밖에 풀지 못했고, 76등을 했다.
그런데 파이썬 퍼솔 특별상이 있다는 얘기를 듣게 되었고, 올해에도 시상을 할 수 있는 가능성이 생겼다.

A 문제를 대회 시작 후 40분경에 파이썬으로 제출했었는데, 제출한 시간이 첫 문제 치고는 느려서 솔직히 못 받을 줄 알았다. 하지만 놀랍게도 작년에 이어 다시 한번 특별상을 받을 수 있었다. 상품은 <밑바닥부터 시작하는 딥러닝> 시리즈이다. 단순히 책값으로 따져본다면 3등상보다도 많은 금액이다..!

코딩은 망했지만, 기분은 나쁘지 않은 결과이다.