대회후기: UCPC 2020 예선

UCPC 2020 예선 문항

올해는 예선/본선 모두 온라인으로 진행되는 까닭에 조금은 아쉽지만, 그래도 1년 전 [Syphon/Nyso/MathAmp] 팀이 출발하게 된 계기가 된 UCPC이기에 올해도 기대와 함께 출발하였다.

 

올해 우리의 팀명은 <TDP 60W 트리플 코어 저전력 자연어 컴파일러™>이다.

너무 잘 지은 것 같아서 만족스럽다. 솔직히 말해 작년의 팀명은 기억하기에는 너무 길었던 것 같다.

 

대회 시작 전부터 백준 서버가 터져서, 본선 진출 조건이 "4 솔브 팀 전부"로 완화되었다.

아쉽게도 긴장감이 다소 떨어지는 대회가 되어버렸다.

 

J를 제외한 문제 5개는 대회 문제지를 받아본 3시부터 6시 반까지 3시간 반 동안 설렁설렁 풀었다.

결국 J는 내가 밤에 구현하여 제출했다.

그럼 이제 문제 설명 시작..!

---

A: 수학은 비대면강의입니다

Trivial. 보자마자 나와 MathAmp가 동시에 구현했다. 전탐색으로 풀 수도 있지만, MathAmp가 연립방정식을 풀어서 $O(1)$ 코드를 제출했다.

---

H: 사과나무

나무 키의 총합이 3의 배수인지 판별하고, 홀수 키의 나무가 너무 많지 않은지만 판별해주면 된다. 내가 빠르게 구현해 제출했다.

---

D: ㄷㄷㄷㅈ / G: 루머

각각 Nyso와 MathAmp가 독립적으로 풀고 구현했다. 둘 다 어렵지 않은 그래프 문제인 듯 하다.

---

E: 감자 농장

어려운 문제로 의도하고 출제한 것에 비해서는 쉬웠다고 생각한다. 출발점의 위치가 양쪽 다 돌로 막혀있는지 / 한쪽만 막혀있는지 / 양쪽 다 뚫려있는지로 경우를 나누어 접근하는 방식을 처음부터 떠올렸다. 감자 위치를 적당히 전처리해 놓으면, 출발점을 기준으로 양쪽에 감자를 몇개씩 줍게 되는지는 어렵지 않게 판별 가능하다. 문제의 주인공은 양쪽 감자를 주우면서 그 사이를 오가게 된다. 이제 문제 해결의 관건은, 각 감자까지의 거리 합을 빠르게 구하는 것이다. 이는 감자의 인덱스 합을 저장한 세그트리를 이용해 해결하였다. 인덱스 합으로부터 현재 위치의 인덱스를 감자의 개수만큼 빼주면, 현재 위치로부터 감자들의 위치까지의 거리 합이 된다. 나중에 알았지만, 굳이 세그트리를 쓰지 않아도 누적합 배열 등을 이용해 인덱스 합을 계산할 수 있다.

 

팀원 세명이 함께 풀었다. Nyso는 현재 위치를 한칸씩 오른쪽으로 옮겨가며 감자 정보를 업데이트하는 풀이를 구상하였고, 위에 서술한 세그트리 풀이는 내 아이디어다. 그래서 결국 구현은 내가 맡았다. 양쪽이 돌로 막혀있는 경우를 이상하게 처리한 까닭에 WA를 엄청나게 띄웠다. 항상 버그는 이상한 곳에 있다;;

---

J: 역학 조사

낮에 계속 쳐다볼 때에는 풀이가 생각나지 않다가, 집으로 들어와서 문제를 붙잡자마자 풀이가 보였다.

가장 마지막 상태로부터, 최초 감염자일 수가 없는 사람들을 역추적하면 된다. 시간 역순으로 모임들을 살피며 최초 감염자일 수가 없는 사람들을 골라낸다. 이후 남은 사람들은 전부 다 최초감염자이어도 괜찮은 사람들이다. 이 사람들이 전부 다 최초에 감염되었다고 가정하고, 다시 시간순으로 모임들을 살펴 최종 결과와 일치하는지 살핀다.

 

진짜 우리 팀 빼고 다 푼 문제였어서, 아무리 이미 5 솔브였어도 그냥 둘 수가 없었다.

---

총평

재미는 있었다. 조금 더 집중해서 대회에 임했다면 스코어보드에서 조금 더 높이 위치했을 수 있다는 생각에 아쉬운 것 같다.

43등으로 마무리했는데, 그래도 작년의 55등보다는 발전한 것 같아 기분이 좋다. 본선에는 더 열심히 임해야지..!