UCPC 2020 참가 후기

팀 구성

RUN(KAIST의 알고리즘 동아리) 슬랙에서 UCPC 팀을 구하는 채널이 생겼고, 온라인으로 알던 분 두 분이 팀원을 구한다고 해서 같이 팀을 구성하게 되었다. 팀원은 Juney와 minfe였다.

예선

그럭저럭 무난히 풀었다. I번은 쉽지만 재밌는 문제라 Appendix에 풀이를 간략히 적어둘듯 하다. 7솔브/2446min.으로 24등을 하며 무난히 본선에 진출했다. 사진은 예선 대회 치는 우리의 모습

 

TOZ 회의실에서 대회를 치는 모습이다.

본선

첫 팀대회 본선이라 설렘도 있었고, 그와 동시에 부담감과 두려움도 있었다. 어찌되든 그 또한 경험이라 생각하며 마음을 비우고 대회를 쳤다.

타임라인

0 min. 대회가 시작하고, 팀원들이 각자 문제를 배분해서 보기 시작했다. minfe님이 A~D, Juney 님이 E~H, 내가 I~L을 맡아서 봤다.

 

4 min. 다른 팀원들은 문제를 읽기 바쁜 와중, minfe님이 A번을 짜서 AC를 받았다.

 

스코어보드를 관람하던 중, B와 C가 많이 풀리길래 이 두 개를 잡기로 했다. minfe님이 B를 잡고, 나와 Juney 님이 C를 잡았다.

 

35 min. minfe님이 B를 짜서 AC를 받았다.

 

39 min. 나와 Juney님 사이에서 나온 cycle detection을 통한 풀이를 Juney 님이 구현해서 AC를 받았다.

 

D와 J가 비교적 쉬워보여서 이 두 가지에 대한 논의를 논의해봤다. D는 DP 풀이가 나왔고, L은 피자의 크기가 최대 100이라는 사실에 착안한 풀이가 나왔다.

 

123 min. Juney 님이 L의 풀이를 코딩해서 AC를 받았다.

 

184 min. minfe 님이 D의 풀이를 코딩해서 맞았다.

 

이후, 여러 문제에 대해 풀이가 나왔으니 구현하지 못하고 대회가 끝났다.

총평

예선에는 나름 고른 기여가 있었으나, 본선에는 내가 강한 스타일의 문제가 안나와서 그런지 몰라도, 내 기여가 적었다는 점이 다소 아쉬운 동시에 잘 해준 팀원들에게 고마웠다. ICPC 때는 더 잘 하도록 내가 노력해야 겠다는 생각이 들었다.

 

결국 5솔브 / 385 min. 으로 마무리하며 전체 18위를 하게 되었다. 15위 까지 시상하는데, 통한의 5솔브 벽을 넘지 못했다는 점이 다소 아쉽긴 했지만, 더 보완하면 ICPC 때는 더 좋은 결과를 낼 수 있지 않을까 조금은 기대하게 되는 것 같기도.

UCPC 2020 스코어보드 사진이다. 나의 팀 버스탑니다^^7은 전체 18등이다.

뒷풀이

wookje님, junie님, Juney님과 함께 Gravekper님 방송을 보며 가볍게 뒷풀이를 했다. 파스타와 오징어 튀김을 먹었는데 꽤나 맛있었다.

Appendix

예선 I번 풀이

이런 류의 구성적인 문제는 전형적이게도 수학적 귀납법을 생각해볼 수 있다. 나는 명제를 "크기가 $n$이고, 차수가 2, 1인 정점이 연속해서 나오는 DUDUDUNGA 트리를 만들 수 있다."로 강화후, 아래 그림과 같은 induction step을 이용하여 문제를 풀었다. (사실 이 부분이 나는 굉장히 straightforward 하다고 생각하는데, 다른 분들의 난이도 평가를 보면 그러지 않은 것 같기도 하다.)

 

Base case는 총 8개 만들면 되는데, 이 부분은 minfe님이 D번 코드 + 왼전탐색을 이용하여 수행해주셨다.

Induction step을 나타내는 이미지이다.