UCPC 2020 후기

스포일러를 피하기 위해 문제 풀이 글을 별도로 작성했습니다. 저희 팀이 푼 문제들의 풀이 과정이 궁금하다면 UCPC 2020 문제 풀이 글을 참조해 주세요.

작년 4월에 처음으로 나(한동규), 이재혁, 박원 세 명으로 구성된 PS 팀을 꾸렸다. UCPC에 나가기 위해 UNIST 컴퓨터 동아리 HeXA의 슬랙에서 팀원을 구했고, 그 해 처음으로 UCPC 본선에 진출했다. 이번 UCPC 2020은 이 팀으로 참가하는 두 번째 UCPC다.

아직 공식적으로 정한 팀명은 없다. 작년에는 ACM-ICPC 월드 파이널에 진출한 팀 789의 짝퉁 버전인 171819 팀으로 출전했다. 팀원들의 학번이 각각 17, 18, 19였기 때문이다. 올해는 Team 112🚨 라는 이름으로 출전했다. 팀원들의 이름이 1동규, 박1, 2재혁이기 때문이다.

COVID-19의 영향으로 올해는 예선과 본선 모두 온라인으로 진행했다. 우리 팀은 디스코드를 통해 실시간으로 대화하면서 문제를 풀었다.

예선

문제 보러가기 / 스코어보드

해결한 문제: A, C, D, G, H, I, J (7문제 해결, 25위)

대회 시작과 동시에 백준 온라인 저지 서버가 터져서 대회 시간이 다음 날 낮 12시까지로 연장되었다. 사고를 수습하느라 고생하셨을 운영진 분들께 안타까움과 감사의 마음을 표한다. 한편 나에게는 좋은 기회이기도 했는데, 어렵고 재밌는 문제들을 오랜 시간 붙잡고 풀어볼 수 있었기 때문이다. 2시간쯤 뒤 서버가 복구되었지만 팀원들은 각자 일정이 있었기 때문에 아쉽게도 대회에 오래 참여하지는 못했다. 원이와 재혁이가 각각 A (수학은 비대면강의입니다)와 H (사과나무)를 풀고 내가 나머지를 풀었다.

올해 UCPC도 대회 문제의 퀄리티가 좋았다. 특히 사전지식보다는 논리적인 접근을 요구하는 J (역학 조사) 문제가 가장 마음에 들었다. J를 푼 시점에서는 이미 다섯 문제를 풀어서 본선 진출 확정이었지만, 다른 문제들도 궁금해서 C와 I를 추가로 풀었다.

C (삼항 연산자)의 경우 온갖 시도 끝에 성공해서 기분이 좋았던 문제다. 비록 첫 시도는 시간 초과를 받았지만, 나름 흥미로운 아이디어로 접근했다고 생각하니 관심 있는 사람은 문제 풀이 글을 참조하자. 고민 끝에 완성한 내 풀이는 출제진 풀이와 다른데, 출제진 풀이의 발상도 재미있었다.

C를 풀고 새벽 1시 반쯤 E를 고민하다가 재혁이가 I (인버스 ㄷㄷㄷㅈ)를 시도하고 있길래 함께 봤고, 그럴듯한 접근을 떠올렸다. 노트 두 페이지를 꽉 채워가며 시행착오 끝에 푸는 데 성공했다! 문제를 풀고 나니 새벽 4시가 되었다. 피곤했지만 기분 좋게 잠들었다.

비록 C, I번 문제를 비효율적으로 접근했지만 의미 없는 접근은 아니었다고 생각한다. 풀이를 찾는 과정에서 새로운 가능성을 익혔고, 시야를 넓힐 수 있는 좋은 경험이었다.

본선

문제 보러가기 / 스코어보드

해결한 문제: A, C, L (3문제 해결, 89위)

원이가 전날 연습 때 HLD를 써서 문제를 푼 기억이 강렬하게 남았는지, A (전단지 돌리기)를 HLD로 풀었다고 한다. 물론 본선 문제 중 가장 많이 풀린 문제인 만큼 훨씬 간단한 풀이가 있다. 올해는 shortest code 특별상이 있었는데, 대신 longest code 특별상이었다면 조금 기대를 할 수 있었을지도 모르겠다(?)

팀원들이 L (피자 배틀)을 고민하는 동안 내가 C (함수 복원)을 잡기로 했다. 처음에는 조금 복잡한 풀이로 접근했고 틀렸다. 스코어보드를 보니 C와 L이 A 다음으로 많이 풀린 문제길래, 복잡한 풀이를 디버깅하는 것보다 간단한 풀이를 찾는 것이 빠를 것 같아서 고민하기 시작했다. 결국 쉬운 풀이를 떠올려서 코딩하고 제출했지만 여전히 틀렸다. 일단 포기하고 팀원들과 같이 L을 고민하기로 했다.

L은 처음에 생각의 방향을 잘못 잡아서 한참 고생했다. 결국 대회 끝나기 30분 전이 되어서야 올바른 풀이를 떠올렸는데, 이번에도 틀렸습니다 판정을 받았다. C와 L 둘 다 소위 "맞왜틀 (맞았는데 왜 틀렸지)" 상태가 된 것이다.

대회가 끝나기까지 얼마 남지 않아서, 다른 문제를 보고 있던 팀원들을 모아 C와 L의 코딩 실수를 잡기로 했다. 재혁이가 C의 반례를 찾아냈고, 살펴본 결과 변수 v를 써야 할 곳에 u를 써서 틀린 것이었다. 수정하고 나니 맞았습니다 판정을 받았다. 대회 종료 10분 전이었다.

L도 비슷하게 변수 j를 써야 할 곳에 i를 썼고, 배열 초기화도 안 해서 틀린 것이었다. 수정하고 나니 맞았습니다 판정을 받았다. 대회 종료 2분 전이었다. 자칫하면 한 문제밖에 못 푼 상태로 마무리할 뻔했는데 간신히 시간 내에 3솔브를 달성한 것이다! 긴장이 풀리고 환호성을 질렀다. 작년과 동일한 3솔브로 마무리했다.

작년보다 팀원들의 실력이 많이 향상되었는데, 본선에서 향상된 실력을 충분히 발휘하지 못해 아쉬움이 남았다. 문제들이 작년보다 어렵기도 했고, 코딩 실수가 너무 컸던 것 같다. 실수만 없었다면 B까지 총 4문제를 풀 수 있었을 것이다.

팀의 약점을 보완하려면

이번 UCPC를 통해 우리 팀의 약점을 확실하게 알 수 있었다. 우선 나의 경우 최근에 코딩 실수가 잦다. UCPC를 대비하기 위해 세 차례의 팀 연습을 진행했는데, 그 중 두 번 코딩 실수로 맞왜틀한 문제가 있었고 팀원들이 실수를 찾아줬다. 또, 엣지 케이스를 자주 놓친다. 아무래도 구현이 깔끔하게 떨어지는 문제만 선호해서 그렇지 않은 문제에 적응이 덜 된 것 같다. 마음을 급하게 먹지 말고, 코드를 작성하는 매 시점마다 올바르게 작성하고 있는지 돌아봐야 할 것 같다. 한동안 놓고 있었던 코드포스에도 다시 자주 참가해서 빠르고 정확한 구현 연습을 길러야겠다.

한편 우리 팀원들은 종종 틀린 접근에 확신을 갖는다는 문제점이 있었다. 예컨대 로컬 옵티멈에 빠질 수 있는 그리디로 접근하거나, 최적해가 부분 최적해에 의존하지 않는 DP식을 세운다거나 하는 경우다. 나는 풀이가 성립하는 이유를 설명할 수 있을 때에만 코딩에 돌입하는 성향이라서, 비슷한 경험이 적다 보니 개선 방법에 대해서는 고민해 봐야 할 것 같다. 우선 주간 팀 연습에 접근 방법을 헷갈리기 쉬운 문제들을 종종 가져와 보기로 했다.

작년에는 3솔브를 했고, 올해는 아쉽게 4솔브를 놓쳤으니 내년에는 5솔브 이상을 노려 보고 싶다. SCPC, ICPC 등 올해 남은 대회들도 열심히 참가하고, 팀원들과 함께 꾸준히 연습하면서 다음 1년동안 실력을 키워봐야겠다.