UCPC 2020 본선 후기

"여기가월파2020인가요" "아뇨, 뚱인데요?"

D-7

 PS도 접었고 1인 대회에 나가기에는 구현 실력에 문제가 있어서 대회에 잘 출전하지 않고 있었는데, 몇 안되는 팀대회인 UCPC가 열리길래 dotorya, alex9801으로 팀을 만들었다. 이번 년도 UCPC는 온라인으로 열린 만큼 3대의 컴퓨터를 쓸 수 있었지만, 우리 팀은 (나때매) 컴퓨터 3대를 활용하기 힘든 팀이어서 불안했다. 그래서 alex9801이 팀연습을 하자고 했지만, PS를 너무 많이해서 질려버린 내가 극구 반대했기 때문에 결국 팀연습은 없었다. (ㅈㅅ!!)

 

 CafeMountain이 팀명을 여기가월파2020인가요로 지었다고 하길래, 말이 이어지도록 아뇨, 뚱인데요?로 팀명을 짓고 이론치를 하자고 했다. 사실 UCPC에 잘하는 팀이 너무 많아서 2등상은 어렵다고 생각한 게, 대회 전에 알아본 바에 따르면 다음과 같은 팀들이 있었다.

 

• 여기가월파2020인가요 : molamola., ainta, tlwpdus
• jihoon Ko Fan Club : moraeduji, ko_osaga, OnionPringles
• 정우팬클럽 : cubelover, kriii, tonyjjw
• 1211789 : khsoo01, namnamseo, gs12117
• Let Us Win UCPC 2020 : GyojunYoun, blackbori, dlalswp25
• 완전탐색 원툴 16등 도전합니다 : imeimi2000, TAMREF, jhhope1

 위 5팀은 실명이거나 팀 구성 과정에서 알고 있었고, imeimi 팀은 팀명만 몰랐다. 3LGM 팀은 못이기는 게 당연하고, 5팀을 모두 이기는 건 불가능하다고 생각해서 편하게 대회를 칠 수 있었다. 예선에서는 대회가 터진 틈새시장을 노려 2등에 안전히 주차하는 데 성공했지만, 본선은 그러지 않으리라고 생각하고 있었다.

 

~0:00:30

 거의 3년만에 VS로 대회를 쳤다. 리눅스면 Vim이나 VSCode, 윈도우면 VS를 쓰는데, 리눅스 컴퓨터를 쓰려면 세팅을 해야 하고, 디버깅은 VS가 더 편하기 때문에 VS로 쳤다. 고인물들이 에디터 부심을 부리는 건 재미로 그러는 거고, 에디터는 자신이 편한 거 쓰면 그만이다. Code::Block으로 누텔라 찍은 사람도 있고, Tourist는 아무도 모르는 이상한 에디터 쓴다.

 

 dotorya가 ADGJ, 내가 BEHK, alex9801이 CFIL을 읽기로 했다. ABCD/EFGH/IJKL으로 읽은 팀들은 A를 풀고 B를 잡았는데, 나는 바로 B를 풀기 시작해서 First Solve를 먹을 수 있었다.

 

~0:03:43 (A WA)

 운좋게 가장 쉬운 문제인 A를 배정받은 dotorya가 바로 코딩을 시작했고, 약간 뒤 alex9801이 C를 코딩하기 시작했다. 직후 dotorya가 A를 (AC여도 First Solve는 아닌 타이밍인) 3분 43초에 제출했지만 WA.

 

~0:05:13 (A AC)

 B를 생각하면서 A번 문제와 바로 옆에 있는 dotorya 화면을 보니, 틀린 점이 바로 보였다. 알려줘서 제출 후 A AC.

 

~0:13:49 (C AC)

 조용히 코딩을 하던 alex9801이 C 코딩을 끝내고 AC. B는 보스방으로 가는 방 분포가 매우 제한적일 것 같다는 생각이 들었고, 성질을 찾아보니 구간이었고, 구간 관리는 이진탐색으로 쉽게 된다는 생각을 하고 코딩을 시작했다.

 

~0:21:54 (B WA)

 B 예제가 나와서 제출했지만 WA.

 

~0:25:07 (B AC)

 B 반례를 찾은 뒤, 고쳐서 제출. 틀리면 dotorya한테 구현을 넘긴다는 생각으로 제출했는데 맞아서 다행이었다. 덕분에 B AC. 내가 대회에서 퍼솔을 받을 일이 없을 줄 알았는데, 알고보니 퍼솔이었다.

 

~0:30:47 (L WA)

 내가 B를 풀고 있는 사이에, dotorya가 L 풀이를 바로 떠올리는 데 실패해서 alex9801에게 풀이를 전달받아 구현에 들어갔었다. 공부를 계속 열심히 해 왔으면 쉬운 문제는 "풀어본 문제 DB"에 있어서 First glance에 바로 풀이가 나오는데, 최근에 문제를 거의 안풀어서 DB가 훼손됐나보다. 아무튼 그 사이에 L을 구현했으나 WA.

 

~0:39:24 (L AC)

다른 문제들을 읽어보는데 도저히 감이 안잡혀서 dotorya 코드나 보기로 했다. 풀이를 안듣고 코드만 읽었는데, 변수 범위가 잘못된 것이 보여서 알려줬다. 크기 N짜리 배열에 2N번째를 참조했던가 그랬다. 1WA 후 AC.

 

 다른 사람 코드 디버깅을 할 때 구체적인 알고리즘을 모르고 봐도 이상한 점이 나오는 경우가 꽤 있다. 예를 들어 변수 range가 배열을 넘어가던가, ij가 바껴있는 거처럼 생겼던가, 변수는 선언했는데 사용하지 않았다던가, 아무것도 안하는 코드가 적혀있던가, 코드의 대칭성이 안맞다던가 하는 것들이 있다. 나는 이런 게 보이면 여기가 이상하다고 말하는데, 이런 식으로 고친 적이 꽤 많다. 물론 이래도 모르면 풀이를 듣자.

 

~1:15:06 (F AC)

 이때쯤 D가 풀렸는데, 풀이는 모르겠고 다들 풀어서 하염없이 붙잡고 있었다. alex9801과 잠깐 F를 의논하여 풀이가 나와 alex9801이 F를 코딩하러 갔으나, 예상되는 구현 시간과 정확도가 애매해서 dotorya에게 넘겼다. 그와 동시에 alex9801은 K를 잡으러 갔다. N이 애매하게 커서 메모리 관리를 해야 해서 시간을 꽤 오래 소모했다. 그래도 첫 시도에 AC.

 

~1:35:49 (D AC)

 F AC 직후 I를 dotorya와 토론하여 바로 풀이를 만들고, 동시에 내가 D에서 깨달음을 얻고 모두 소리질러~ dotorya가 구현이 짧아보이는 D를 먼저 코딩했으나, 내 풀이에서 실수가 하나 나와서 WA를 하나 쌓고 AC.

 

~1:46:49 (I AC)

 직후 dotorya가 I를 코딩해서 바로 AC.

 

~2:08:35 (K WA)

 alex9801이 점들이 있을 때 삼각분할하는 코드가 필요하다고 해서, 내 github에 있는 Voronoi Diagram으로 Delauney Triangulation해주는 코드를 넘겨줬다. (덕분에 코드가 12KB가 되어버렸다.) 메뉴얼하게 삼각분할하는 것이 의도겠지만, 머 좋은게 좋은거라고 그냥 넘겼다. 예제가 나와서 제출했지만 WA. dotorya는 어쩔 수 없이 어려운 G를 풀러 떠났다.

 

~2:23:55 (K RE)

 K에서 WA를 고치고 나니 assert에 걸려 RE를 받았다. 그래서 나는 Data Generator를 만들러 떠났다. 이 때 K 풀이가 틀린 게 아닌지도 한참을 고민했다.

 

~2:35:44 (G WA)

 dotorya가 거의 40분을 코딩한 뒤 G를 처음 제출했으나 WA. 동시에 나와 alex9801은 수많은 assert의 늪에 빠지고 있었다.

 

~3:01:53 (K AC)

 제너레이터가 반례 데이터를 잡았고, 계산 결과 점 개수가 모자라 좌표가 80을 넘어가버린 거였다. 79면 여유롭겠다고 생각한 것이 실수였다. alex9801이 테두리를 살짝 고쳐서 AC.

 

~3:02:37 (G AC)

 dotorya가 1시간 전의 자신에게 왜 이렇게 짰는지를 원망하며 5번의 WA를 더 냈고, 그 후 간신히 AC.

 

~3:49:49 (E AC)

 dotorya가 천지창조 minor 버전인 J 코딩을 시작했고, 나와 alex9801이 E를 고민하러 갔다. K=1일 때는 min-cut이니까 그래프를 K개의 copy로 만들어 min-cut을 구하는 것이 가장 직관적인 풀이었고, 처음 보면 이상하지만 생각해보니 되는 풀이라서 dotorya에게 확인을 받은 뒤 alex9801이 E 코딩을 시작했다. 역추적이 있어 약간 더러웠지만 무난하게 E AC.

 

~4:31:49 (J WA)

 E AC 직후, alex9801과 나는 H를 시도할 지, J를 서포트할 지 골라야 했다. H는 최근 PS계에서 자주 보이지만, 대회에는 안나왔으면 좋겠다고 생각한 Dirichlet Convolution 문제였다.

 

 Dirichlet Convolution은 최근들어 snupc에도 나왔고, 최근 BOJ 유저 제작 문제들에 사용되는 등, 복잡한 이론이 들어간 수학 문제를 좋아하는 사람들 사이에서 이슈가 되고 있는 테크닉이었다. 그래서 대회 당시 고인물들은 한번쯤 들어봤거나 알고 있는 테크닉인데, 아는 사람들만 대회에서 문제 수 +1 하라고 만든 문제인 것 같았다. 내가 알기로는 gs12117님이 KMO 고등부 2차 금상을 받았던 거로 기억하는데, 그 실력으로도 모르면 못푸는 문제였나 싶었다.

 

 나는 PS를 접었기 때문에 당연히 자세한 내용은 몰랐고, 공부하고 풀기에는 리스크가 크다고 판단, alex9801은 J 문제 N^2을, 나는 체커를 짜서 반례 생성에 도움을 주기로 했다.

 

 dotorya가 J 구현을 하는데, 내가 만든 풀이의 마지막 단계가 CHT인 줄 알았지만 아니었고, 때문에 30분정도 풀이를 다시 생각해야 했다. 3명이 두뇌 풀가동을 한 결과 Money For Nothing이랑 완벽하게 같은 문제라는 것을 깨달았다. 모두 코딩한 뒤, 약간의 디버깅 후 제출했으나 WA.

 

~4:50:25 (J AC)

 (ho94949의 훈련소에서 온 전화도 끊어버리면서) 20분동안 3명이 광란의 디버깅을 했다. 체커에서 반례는 바로 나왔는데, 이걸 디버깅할 수 있도록 작게 만드는 과정에서 약간 헤멨다. 약 15분 정도를 남기고 n=5, q=1, 가중치 100 이하인 작은 반례를 만들 수 있었다. 반례를 받은 dotorya가 5분동안 디버깅 후 틀린 점을 찾아 제출. 동시에 시간복잡도가 log^3일 수 있다는 생각에 alex9801이 마지막 부분을 codeforces에서 가장 빠른 코드로 바꿔서 제출. 다행히 5분정도 뒤 첫 번째 제출이 맞으면서 AC.

 

~5:00:00

 그렇게 간신히 시간 안에 11문제로 마무리.

 

5:00:00~

 끝나고 같이 스코어보드 중계를 봤다. "jihoon Ko Fan Club" 팀은 당연히 풀었어야 할 것 같은 K를 틀렸고, "완전탐색 원툴 16등 도전합니다" 팀은 풀었을 것이라 예상한 J를 틀렸고, "정우팬클럽" 팀은 마지막 순간에 K를 말렸던 것 같다. 덕분에 "여기가월파2020인가요" 아래 "아뇨, 뚱인데요?" 를 주차하는 데 성공했다.

 

 PS를 오랫동안 안했는데도 실력이 별로 줄진 않았나보다 싶기도 하고, 팀전이라 대회도 재밌게 쳤고, 결과도 이론치 최고점이라 매우 만족스러운 대회였다. 받은 상금은 오마카세였나 엄청 비싼 스시집에 모두 쓰고 깔끔하게 끝내기로 했다.

 

끝!