2020 UCPC 본선 후기

Little Piplup (어쩌면) 마지막 official한 대회가 생각보다 아쉬운 성적으로 마무리되었다. 내 트롤링이 좀 있었지만, 그래도 스스로 변호를 좀 하자면 트롤링이 페널티를 좀 깎아먹긴 했어도 등수가 별로 바뀌진 않았을 것이다.

항상 그렇듯 대회 끝나고 적는 후기. 이 글을 보는 사람이 solved.ac를 모를 가능성은 별로 없지만, 본문 중 '난이도'를 롤 티어처럼 언급해놓은 것은 모두 solved ac 기준이다.

 

-1. 대회 준비 + 팀연습에 대해

작년 본선은 놀라운 난이도의 대회로, 4문제가 대회 중 풀리지 않는 기염을 토했다. 원래는 작년 대회와 비슷한 난이도의 셋으로 팀연습을 하려고 했는데, 2019 UCPC는 13문제중 solved 기준 5루비 3다이아로, 이정도 난이도의 셋은 Petrozavodsk camp나 ICPC world final에서나 볼 수 있을 법한 수준일 뿐더러 우리 입장에서는 대회중의 루비문제는 빠르게 거르는것 외에는 별로 해볼수 있는게 없다. 그래서 이보다 살짝 낮으면서, 문제 고르는 선구안을 적당히 다듬을 수 있는 CERC 2017로 마지막 팀연습을 했다.

CERC 2017은 다이아와 플레로 떡칠된 셋으로, 나는 다음과 같은 생각들을 하며 팀연습을 했다.

- 현실적으로, 대회 중 다이아 이상의 문제를 여러개 푸는것은 우리팀에게는 무리다.

- UCPC 대회는 '아마도', 플레 미만이 2~3문제, 플레가 2~3문제, low 다이아가 2~3문제, 나머지는 그 이상으로 채워질 것이다. 설마 작년보단 조금 쉬워지겠지.

1과 2를 조합하면, 우리가 할 수 있는 것은 플레 이하의 모든 문제를 밀고, low 다이아 하나를 셋이 같이 attack하는 것이다. 팀연습을 통해 느낀것과 + 우리보다 훨씬 경험이 많은 동기의 조언에 의하면, 우리 팀은 개개인의 실력에 비해 같이 관찰을 쌓아가며 풀 때 시너지가 상당히 좋은 편이기 때문에, 한명한명이 5시간 내에는 생각하기 어려운 것도 하나정도는 비벼볼만 하다. 실제로, 팀연습 또는 팀 대회에서 그런 경험을 많이 해 봤다. 

저 흐름에서 의외의 난제는 attack 할 다이아 하나를 찾는 부분이다. 스코어보드를 보면 되긴 하겠지만, 의외로 우리 팀은 편중이 심하기 때문에 (편중이 심하다기보다는, 자료구조에 약점이 있다는 말이 정확할것 같다), 스코어보드상 많이 풀린 문제와 우리가 비빌 문제가 항상 같다는 보장도 없고, 결정적으로 ICPC때 금광-Strike Zone처럼 우리만 모르는 웰노운 때문에 망할 위험이 높다. 그래서 그걸 연습할 필요를 느낀 것도 있다. 

CERC 2017 팀연습 후기는 적다 말아서 나중에 올릴 계획이다. 재밌었다.

 

0. 대회 세팅

예선과 같은 장소에서 모였다. 본선도 설마 서버가 터지겠냐는 무서운 농담을 하면서 시간을 보냈다. 문제지가 뜨면 ABCD / EFGH / IJKL로 나눠 읽기로 했다. 본선은 어차피 고난도 문제가 포진해 있으므로 초반 버스트는 별로 의미가 없고, 앞서 말한 '플랜' 을 성공적으로 수행할 수 있느냐가 가장 중요하다.

 

1. [A, C] : 구현 트롤링 (~12시)

내가 읽은 문제 중에는, A는 그럭저럭 쉬워 보였고, B는 구현이 빡셀거같았고, C는 뭔가 어 뭐지? 하는 생각이 들었고, D는 여러 비슷한 문제가 떠오르긴 했었다. 스코어보드를 보고, A를 수많은 팀들이 풀었다는 사실과, 각 팀원들이 Report한 문제별 감상(?) 을 토대로 A-C-L 정도를 봐야 한다는 판단을 했다. 참고로 Coffeetea는 그냥 모든 문제가 개어렵다는 얘기를 했는데, 끝나고 보니 그렇더라(...)

 

A. 전단지 돌리기

Solve : DHDroid, Gratus907

Code : Gratus907

A번은 간단한 트리 순회 문제였다. 트리의 한 정점에 서서, $D$ 거리까지 전단지를 뿌릴 수 있을 때, 최소한으로 움직여서 모든 정점에 전단지가 닿게 하고 돌아오는 데 걸리는 시간, 즉 지나야 하는 edge 수에 대한 문제. 자명하게, 어떤 노드의 서브트리 높이를 보면서, 더이상 깊이 들어갈 필요가 없으면 그만 가고 돌아감으로써 간단히 문제를 해결할 수 있다. 

이 문제를 DHDroid에게 설명했는데, 문제는 내가 '루트 정점으로 돌아와야 한다' 라는 조건을 읽으면서 빼먹었다. 그 결과, 우리는 '어떤 경로가 최선인가' 를 고민하기 시작했고, '내 서브트리를 모두 돌고 나한테까지 돌아오는 시간' 을 저장하는 Tree DP를 하려고 시도했다 (사실 이것도 필요 없긴 한데, 이땐 약간 스코어보드에 쫒겨서...). 그런데 사실 평소 UCPC도 아니고, 이 시점에 수십 팀이 이런 Tree DP를 코딩해서 맞출 수 있다는건 약간 의외라서 (이번엔 본선 진출팀이 엄청 많다) 이상하다는 생각을 하고 있었다.

문제를 제대로 독해한 후에도 내가 트리를 다시 안 만들고 그 위에서 뭔가 하려다가 계속 귀찮게 구현이 꼬였다. 스코어보드에 쫓기기 시작하면 구현이 심하게 말리는 경향이 있는 내 약점이 그대로 나타난것 같다. :( 

아무튼, 여차저차 해서 무려 이 문제를 AC 받는데 1시간이 걸렸다. 다행히, 중간부터는 나도 로직에는 아무 이상이 없고 구현 문제임을 확신했기 때문에 DHdroid와 Coffeetea에게 C번을 풀어야 한다고 전달하고 혼자 멘탈과 사투했다.

 

C. 함수 복원

Solve : DHDroid, Coffeetea

Code : (사실 고통받느라 누가 짜고 있는지도 몰랐는데, 코드를 보니 Coffeetea가 짰네..)

처음에는 좀 어려워 보였는데, 결국은 쉬운 문제. 함수 $f$를 이용, $i$ 와 $f(i)$ 를 edge로 이은 그래프에서 도달가능성 표가 주어질 때 $f$로 가능한 함수의 개수를 찾는 문제이다. Cycle을 찾고, 그 Cycle을 이용해서 쉽게 셀 수 있다. 

자세한 풀이는 내가 A번 코딩 사투하느라 전혀 참여하지 못했기 때문에, 나중에 업솔빙하게 되면 서술할 예정.

 

2. [B, L] : Pacing up (~13시 30분)

L. 피자 배틀

Solve : DHDroid

Code : DHDroid

DHDroid가 거의 혼자 DP임을 관찰하고 거의 혼자 쳐낸걸로 기억한다. 확실히 DP 문제에 강한 듯..

무려 2*1000*1000*100 테이블을 만들어서 했는데, 제한시간이 5초라서 크게 상관 없었던 것 같다. 경우의 수를 많이 나눠서 그냥 계산하는 식으로 해도 되고, 특히 처음에 어떤 조각을 먹었는지에 따라 사실상 선형으로 펴도 되기 때문에 조심스럽게 나누기만 하면 된다.

 

B. 던전 지도

Solve : Coffeetea, Gratus907

Code : Gratus907

풀이가 말로 쓰기 매우 어렵고, 문제는 더 어렵다.

특정 층에서 보스방에 도달 가능한 좌표는 $[a, b]$ 구간으로 나타남을 관찰한다. 이때, '아래 층' 에서, '이 층' 의 $[a, b]$ 로 올 수 있는 모든 점은 결과적으로 보스방에 도달 가능하다. 생각해 보면, R과 U밖에 없기 때문에, 올라갈 수 있는 위치들이 한정적이게 되고, 아래 층에서 '어디를 타고 올라와야' 하는지를 따라가면서 찾으면 된다. 풀이 슬라이드 거의 그대로이므로 참고.

풀이 슬라이드에 나온 풀이는 단조성을 이용, inchworm을 적용하여 한칸씩 왼쪽으로 밀면서 풀었고, Coffeetea가 처음 제안한 것도 이 방식의 구현이었지만, 뭔가 구현이 까다로울 것 같아 비슷한 시점에 나는 "현재 위치에서, 왼쪽/오른쪽으로 가장 가까운 U의 위치" 와 "내 왼쪽에서 출발해서 나한테 도달하는 가장 왼쪽 지점의 좌표"를 모조리 Preprocessing하고 이걸 이용하여 Jump뛰면서 (결과적으로는 훨씬 복잡하게) 찾았다. 어차피 시간 복잡도도 같고 상관은 없다.

구현이 상당히 힘들었다. 한줄짜리 케이스 / 아예 올라갈수가 없는 케이스 등등이 계속 걸려서 2번 틀렸고, 자명한 $O(NM)$ DFS 풀이가 있어서 Stress Test로 쉽게 디버깅을 해보려고 했으나 그게 아무 문제에서나 되는게 아님을 배우게 되었다. ㅋㅋ

구체적으로는, Edge 케이스가 나오기 쉬운 이런 유형의 문제에서는 랜덤 테스트가 그런 경계 케이스를 잡아주기가 훨씬 힘들다. 그래도 구현 중에 느낀 절망감에 비해서는 빠르게 AC를 받았다.

 

3. [D (실패)] : Shock and Awe (~16시)

이 시점까지 우리는 대회가 비교적 계획대로 진행되고 있다는 느낌을 받았다. 스코어보드로 추측해 보건대 D가 플레 이상, 어쩌면 다이아 레벨의 문제고, 나머지 모든 문제는 다이아 이상인 것으로 보였기 때문에, D를 풀 수 있으면 우리 계획은 성공한 것이며, 남은 시간이 무려 2시간 30분이고 3명 모두 생각 Queue가 빈 상태이기 때문에, 설령 D가 다이아 4~5 정도 문제더라도 충분히 해볼만하다는 느낌이 들었다.

 

결과적으로 *우리가 이걸 풀 수 있을 것이다* 외의 거의 모든 생각이 맞아떨어졌다. ㅋㅋㅋ;;;

 

대략적인 문제 설명을 하자면, '위'에 $(U_i, L)$ $N$개와 '아래'에 $(D_j, 0)$ $M$개가 있는데, 이들을 모두 $N+M-1$개의 선분으로 연결한다. 단, 이때 연결선끼리 교차할 수 없다. 이때, 모든 정점 간의 '거리'의 합을 최소화하게 연결하고 싶은데, 여기서 거리는 '연결 선분' 만 타고 이동했을 때, 이동한 연결 선분의 길이의 제곱의 합 (합의 제곱이 아니다!) 으로 정의한다.

 

작년 UCPC M번 등등 여러 풀었던 문제를 떠올리면서, 다양한 DP 점화식을 구상하고 많은 사실을 관찰했지만 어떤 경우도 다음 스텝으로 넘어가기에 충분하지 않았다. 크게 생각했던 것들을 떠올려 보면...

- $U_i$ 와 $D_j$를 연결하는 간선에 대해, 이 간선을 지나는 횟수를 세는 방법으로 합을 구한다 (실제 필요한 과정)

- $U_i$ 와 $D_j$를 연결하는 간선이 있다면, $U_{i-1}$과 $D_j$를 연결하거나, $U_i$와 $D_{j-1}$을 연결해 주어야 하는게 아닌가? 이걸 이용해서, 마지막에 추가한 정점이 위인지 아래인지에 대해 DP

- 사실 뭔가 기하적인 관찰이 있는게 아닐까?

- 분할 정복?

- 아래에 있는 $M$개의 점이 각각 위에 있는 점들 중 어떤 '구간' 을 가져간다고 생각할 수 있고, 그러면 이웃한 구간들 간의 교집합이 하나여야 한다. 이걸 이용해서, dp[i][j] = i번째 '위 점' 이 j번째 교점일 때 ~ 를 만들자

아무튼 이런걸 수없이 많이 생각해 봤지만 이 다음으로 진행하지 못했고, 2시간 반 동안 고통받다가 대회가 끝났다.

끝나고 보니 작년 M번과 비슷한, 연결 상황을 격자로 바꾸는 DP였다. 작년 문제를 다시 제대로 업솔빙하지 않은게 좀 아쉬웠고, 아직도 '이게 그렇게 2시간 반동안 우리가 같이 생각해도 모를 만한 거였냐?' 라는 질문에 대해서는 딱히 답이 없다.

---

대회가 끝나고 별로 스코어보드를 보고 싶지 않아서 롤토체스를 하면서 남은 문제를 읽었다. 엄청 어려워 보이고 딱히 뭔가 D 대신 잡았을만한게 없었다. 사실 2시간 반 고통받고 나서는 A번 줬어도 못 풀었을거 같긴 하다 ㅋㅋ!

 

끝나고 회사 동료들과 UCPC를 뛰고 온 dlwocks31과 고기를 먹으며 병특 얘기, 신세 한탄 , (우리 결과에 의해 나올 수밖에 없는) 문제 욕 등을 했다. 앞으로 연습할 때 CP보다는 PS 느낌을 살려서, 어려운 문제를 한두개만 잡고 정말 오래 고민해 보는 시간을 많이 가질 필요가 있다는 얘기가 나왔는데, 그것도 나름 재밌을 것 같다.

 

아무튼 프로그래밍 대회 치르기 어려운 상황에서도 비대면으로 어떻게 어떻게 대회가 잘 치러졌고, 우리 결과는 아쉽지만 많은 것을 배울 수 있는 기회가 되었다. ㅋㅋ;;