2023 UCPC 예선 후기

7월 1일에 봤던 대회인데 이제야 후기를 쓴다. 대회 이틀 후에 여름학기 중간고사가 있어 바로 벼락치기 on 해버렸고, 시험당일은 시험을 조진줄 알고 우울해서 안 썼고, 그 다음날은 내가 시험을 잘봤다는 것을 알게되어서 기분이 좋아져 놀아버렸다. 정말 변명이다..

---

# 대회 시작 전 : 팀 전략?

팀은 팀연습도 할겸? 올해 ICPC 나가기로 한 팀으로 나갔다. 팀 결성에 많은 이슈가 있었으나 최종적으로 옥테인, 서리와 하기로 했다. UCPC 신청 마감 약 3시간 전에 팀명 안아줘요, 닉네임 덤벼줘요 알려줘요 끝내줘요로 급조했다.
 
팀연습은 한번도 하지 않았고, 예선 시작 n분 전에 3k 번은 서리가, 3k+1은 옥테인이, 3k+2는 내가 맡기로 했다.
여기서 살짝 문제가 발생해버렸는데, 10문제일 것이라는 고정관념으로 옥테인에게 3k+1은 4문제라는 발언을 했다. 하지만 11문제가 나왔고, 마지막 문제인 K번은 원래 내가 맡았어야 되는 문제였지만.... 근데 어쨌든 모두가 다같이 착각을 해서 큰 문제는 발생하지 않았다. 미안!!
 
대회가 시작하기 직전에 옥테인이 자기는 수학 문제 하나 붙잡고 아 이거 할 수 있는데.. 하다가 끝날거라는 플래그를 세웠다.

---

# 대회 시작 : 옥테인의 미친 독주 (A, D번 AC)

대회가 시작되었고, 나는 B, E, H 문제를 깠다. 그렇게 버려진 K....
B를 읽고 있는데 옥테인이 A 브론즈임 하고 뚝딱하더니 맞혔다. 같은 팀이지만 너무 빨리 1솔해버려서 약간 압도되었다. 난 아직 문제도 하나도 못 읽었는데...
 
마음을 추스리고 문제를 찬찬히 읽어보니 엄청 쉬운 문제는 아닌 것 같고 적당히 풀만할 것 같아보였다. 문제를 잘못 이해하면 큰일이므로 예제도 꼼꼼히 테스트하고 있었는데 옥테인이 또 D를 풀어버리고 서리도 C번 대충 기하+MST임 이래서 점점 밥값해야된다는 생각이 들기 시작했다.
 
일단 B는 조금 생각을 해봐야 될 것 같아서 E랑 H를 대충 읽어봤다. E는 누가봐도 '나 수학이에요' 하는 문제였고, H는 규칙성 잘 찾으면 되겠지 싶은 문제였다. E는 슥 읽고 옥테인아 믿는다 외쳤는데, 나중에 다시 보니 내가 문제를 약간 잘못 이해하긴 했었다. (이래서 예제까지 꼼꼼히 테스트해봐야 된다..) 그래도 뭐 어쨌든 수학이라 결과적으로 옥테인이 잡긴 했다.
서리가 F번 시뮬레이션이라면서 문제를 요약해서 전달해줬다. 그치만 일단 내가 맡은 문제부터 풀자라는 생각이 강했다.

---

# B번 풀이

B, E, H 라인업을 보니(스코어보드를 봐도 마찬가지이고) B가 제일 쉬워보여서 B를 잡았다. 그래프라서 개인적으로 선호하기도 하고 심리적으로도 편한 것도 한몫했다.
 
일단 쉽게 떠올릴 수 있는 풀이는 K개의 회사에 대해 간선의 가중치가 높은 것부터 추가하면서 그 회사의 정점들이 연결되는 순간을 체크하는 문제로 변형하는 것이다. 연결의 유무 체크는 유니언 파인드를 써서 그래프를 관리해주면 쉽다. 시간복잡도는 O(M lg M + K(M+N)) 정도라서 당연히 터진다.
 
이제 이걸 줄이려면 K(M+N)에서 (M+N) 부분은 상식적으로 줄이기 힘들기 때문에 K를 줄여야 된다. K개의 회사에 대해 간선의 가중치 순으로 그래프를 생성하는 작업을 하는 것은 반복되며, 비효율적이다. 따라서 한번의 그래프 생성에서 답을 찾는 것을 목표로 생각해 보았다.
하나의 회사의 정점들만 관리하던 아까의 쉬운 풀이에서는 그냥 해당 회사의 정점 개수를 들고 유니언 파인드를 해주면 되었는데, 이제 여러 회사들에 대해 처리할 것이므로 각 그룹마다 모든 회사에 대해 정점 개수를 들고 다니면서 유니언 파인드를 해주면 되겠다는 생각을 했다. 당연히 그룹에 없는 회사의 정점 개수를 따져줄 필요는 없으므로 이부분은 map으로 관리해줬다. (log를 하나 떼고 싶다면 정점수를 기록하는 배열과 그 그룹에 있는 회사 목록을 관리하는 벡터로 처리해주면 될 것 같지만 시간복잡도 계산해보니 널널해서 빠른 구현을 위해 map을 썼다.)
 
이제 생각해야되는 것이, 유니언 파인드에서 그룹을 합치면서 모든 회사에 대해 정점 개수를 관리하려면 어차피 K가 곱해지는 거 아닌가?라는 부분이다. 그치만 우리에겐 이런 상황을 해결하는 유명한 방법이 있다. small to large라는 방법으로, 그룹의 크기가 작은 것을 큰 것에 합쳐주면 합치는 데 걸리는 전체 시간이 n lg n이 된다는 것이다. 아이디어도 간단하고 증명도 쉬운데 효과는 뛰어난 개쩌는 테크닉이다.
(증명을 쓰다가 너무 길어져서 분리했다)
이제 문제를 푸는 전체 시간복잡도는 O(M lg M + N + M lg^2 K)가 돼서 시간 안에 돌아간다. (라고 생각했으나 사실 우리가 만드는 것은 트리이기 때문에 M lg^2 K가 아니라 N lg ^2 K이다.)
 
라고 생각했다. 여기까진 좋다. 근데 사실 나는 small to large를 구현해 본 적이 없었다...!
그래도 뭐 구현이 어려운건 아니니까... 다시 한번 small to large가 잘 적용되는지 머릿속에서 빠르게 증명 돌려주고 구현을 시작했다.

---

# 순탄?한 대회 초반 : I, K, B번 AC

내가 B번을 구현하는 동안 우리팀은 스코어보드를 보면서 쉬운 문제를 공략했다. 서리가 I를 잡고 옥테인은 K를 잡았다.
 
서리가 I번에서 컴파일에러를 외쳐서 잠깐 대꾸해줬다.
잠시 후 서리가 이번엔 TLE를 외치면서 이게 안될리가 없다고 도움을 요청했다. 코드 좀 봐달라고 해서 봤는데 전체 맥락을 모르니 좀 이상하다는 생각은 들었지만 대충 맞겠지하고 넘겼다. 뭐 이분탐색이랑 세그가 어쨌다면서 봐달라고 했었는데, 아직도 그 코드는 뭐가 되고 싶었던 코드인지 이해 못했다.
결국 서리가 코파일럿이 잘못 짜줬다면서 고쳐서 맞았다. 그러게 왜 코파일럿을....
 
비슷한 시간대에 옥테인이 K에서 한번 틀렸다가 바로 고쳐서 맞았다.
초반부터 TLE, WA 상태라서 잠깐 불안했지만 다들 금방 고쳐서 안심했다.
 
서리랑 옥테인이 F를 같이 토의하기 시작했다. 서리가 F번을 구두로 전했는데, 내가 문제 잘못 전달됐을지 모른다는 우려를 표함으로써 플래그를 세워버렸다. 결국 그것은 현실이 되었음이 대회 종료 1시간쯤 전에 밝혀졌다. 뭔가 행렬이 어쩌니 하면서 얘기하길래 저것도 수학이야? 으악 하면서 둘에게 맡겼다.
 
서리는 C번을 잡았고 옥테인은 F를 조금 더 고민하다가 가능을 외쳤다. E번을 고민해보고 대회종료가 1시간 남은 시점이 되면 F 구현 시작하겠다고 했다.
 
아무튼 B번은 답 계산하는 부분에서 간선 가중치를 까먹고 안 곱한거 빼고는 오류없이 무난하게 구현을 마쳤다.
예제 돌리고 나니까 너무 실행이 잘 되어서 불안이 엄습했다. 처음 큰작 구현한 것인것도 있어서..
한 1분정도 코드를 확인하면서 큰작 첫 구현이라고 고백했다. 옥테인은 절규했고 서리는 큰작이 뭐야?라고 말했다... 대회가 끝나고 보니 우연인 것 같긴 하지만 각자 자기한테 맞는 문제를 잘 잡은 것 같다.
계속 코드만 들여다봐도 달라질건 없는 것 같아서 그냥 제출했다. 다행히 한번에 AC 띄웠다. 그렇게 오래 걸렸다고 생각 안했는데, 중간중간에 집중이 끊겨서 그런지 대회 시작 후 56분이 흐른 시점이었다.

---

# 잔잔?한 대회 중반 : C번 AC

이제 밥값했다는 생각이 들어서 마음에 여유가 생겨버렸다...
E번이 수학이지만 그래도 조금 생각은 해봐야겠다 싶어서 다시 문제를 봤다. 예제 돌려보니 내가 문제를 잘못 이해했다는 것을 깨달았고, 조금 더 고민하다가 옥테인을 믿기로 했다.
 
H번이 맞는 팀도 좀 나오고 있었기에 H를 잡았다. 그치만 긴장이 풀린 탓인지 머리를 팽팽 돌리지 않은 것 같다.
이런 문제는 보통 한 문자열을 다른 문자열로 바꾸려고 하기보다는 두 문자열에서 각각 시작해 삭제 연산을 통해 같은 어떤 문자(혹은 문자열)로 도달하게 만들어 푸는 경우가 많다.
라는 생각을 잠깐 해놓고 막상 저 방법과는 거리가 다소 있는 관찰들을 하기 시작했다... 아직 밥값 안했는데..
 
옥테인은 E를 구현했지만, 예제에서 틀린다고 말했다. 그치만 난 수학을 잘 못해서 도움이 전혀 안 될 것을 알았기에 방치했다.. 분명 20분 안에 풀고 F 짜겠다고 했는데..? 그치만 그는 빛나는 3솔의 옥테인. 어떻게든 해주겠지라는 믿음이 있었다.
 
서리가 C를 뭔가 투덜거리면서 구현하더니 맞았다.

---

# 혼돈의 대회 후반 : F번 AC

서리와 옥테인이 F를 다시 얘기했는데, 옥테인이 '이런 관찰 쓰면 됨'이라고 주장했고, 나와 서리는 뭔가 잘못됐음을 눈치챘다. 서리가 반례를 제시했고, 옥테인의 관찰은 '??? 문제를 잘못 이해함'으로 공중분해되어버렸다. 결국 옥테인은 E에 전념하기로 했고 F는 서리가 잡았다.
 
대회종료가 1시간 좀 안되게 남았던걸로 기억한다. 서리가 F 풀이를 뱉어냈다. 일단 듣긴 했는데 이해력 이슈인지 H에 집중이 쏠려있어서 그런지 당시에는 이해 못했고 그냥 서리를 믿기로 했다. 지금 생각해보면 이해하기 어려운 것도 아니었어서 이런 부분은 개선이 필요하다고 생각한다. 아까 I에서 코파일럿 이슈때도 이해력 딸렸던 것도 같은 맥락이다...
풀이를 이해하지 못했기 때문에 서리가 구현이 시간안에 될지 모르겠다며 걱정했을 때, 내가 할 수 있는 것은 키보드 빌려주기밖에 없었다. 옥테인의 A타입 to C타입 젠더까지 동원해서 옳게 된 팀을 구현하나 싶었는데, 설치 이슈인지 그마저도 실패로 돌아가게 되었다.
 
옥테인은 계속 E를 잡고 있었고, 나는 H를 조금 더 고민하다가 앞서 잠깐 스쳐지나갔던 '두 문자열을 공통된 형태로 만들어주기' 아이디어로 돌아가 곧 풀이를 떠올렸다. 하지만 시간이 30분정도 남은 상태였고, 풀이를 충분히 정리하지 못한채 구현에 뛰어들게 되었다. 시간 안에 절대 안될것 같다는 생각이 들었지만 일단 무지성 구현해보기로 했다. 원래도 좀 더럽겠다고 생각했지만 시간에 쫓기며 구현하다보니 점점 스파게티가 되어가는 코드를 볼 수 있었다.
 
서리가 RTE, CE, TLE를 거쳐 대회종료 11분 전에 AC를 받았다. 7솔이면 안정권이라고 생각했기 때문에 나는 구현에 좀 힘을 뺐고, 몇분 더 짜다가 절대절대 못짠다고 판단하고 cout << "안아줘요" << endl;을 제출했다. 프리즈의 긴장감 형성을 위해? 모든 문제에 의미없는 제출을 하고 대회를 마쳤다. 사실 이런 대회들 하는거 보면서 늘 있었던 로망이었다.
옥테인은 결국 끝까지 E번을 붙잡고 '이거 분명히 할 수 있을 것 같은데'를 외치며 완벽한 플래그 회수에 성공했다.

---

# 결과

최종결과는 40등으로 본선 진출에 성공했다.
7솔이 49등까지 있길래 7솔까지는 다 붙여줄 줄 알았는데 아니었다. 44등까지 통과했다고 들어서 그리 안정권은 아니었다는 것을 알게되었다. 계속 40등~50등쯤에 위치하길래 안정적으로 나갈거라고 생각했는데 너무 안일했었나보다.
하지만 사실 우리는 믿는 구석이 하나 있었다. 바로 여성 우대 티켓. 이로써 나는 밥값했다고 봐도 되는거 아닐까? 물론 본선에는 그런거 없으니 문제 열심히 풀어야지..

---

# 되돌아보기

내가 B를 풀고 긴장이 안 풀렸더라면 H를 시간 내에 풀 수 있지 않았을까 싶다.
또한 나는 잘 모르지만 E번에서 옥테인이 식을 세우는 부분에 실수가 있었다고 하는데, 이것도 잘 됐었더라면 9솔까지 노려볼 수 있지 않았을까 싶다. 좀 아쉽긴 하지만 그만큼 다음번에는 더 잘할 가능성이 있다는 뜻이니까 긍정적으로 생각해본다.
 
이번에는 쉬운 문제가 많았기 때문일지도 모르지만 비교적 각자 자신한테 맞는 문제를 잘 잡았던 것 같다고 생각한다.
셋 중에서 옥테인이 가장 구현이 빠른 것 같은데, 초반에 쉬운 문제들을 잡고 빨리빨리 풀어줘서 패널티도 아끼고 든든했다. 이후에 어려웠던 수학 문제인 E를 거의? 풀이까지 갖고 간 것을 보면 확실히 수학은 발견 즉시 옥테인에게 넘기는 전략이 좋은 것 같다.
I번은 대회 종료 후에 보니 세그까지 쓸 필요가 있었던 문제는 아니었지만, 아무튼 서리는 자기 몫의 문제들을 다 잘 풀어줬다. 원래 서리에 대해 구현을 잘한다는 이미지를 갖고 있었는데, 사실이 아니었다고 한다. 구현머신으로 써먹어야겠다는 내 계획은 무산되었다. 오히려 옥테인이 본선에서 첫 구현을 잡는게 맞는 것 같다.
쉬운 문제들을 알아서 컷하고, 바로 풀리지 않은 플래~다이아정도 되는 문제들은 분배를 잘해야 될 것 같다. 그래도 서리가 활발히 소통의 장을 열기 때문에 팀 연습 조금만 해보면 어떻게든 잘 되지 않을까 싶다.
 
본선은 노트북을 팀당 1대만 쓸 수 있는 점이 신경쓰인다. 이 부분때문에 팀연습을 해보는게 좋겠다는 생각이 든다. 본선까지 시간이 많다면 많지만 그렇다고 막 많은 것은 아니라서, 또한 나와 서리는 주로 대전에 있지만 옥테인은 반대라서 팀연습 할 수 있을지 모르겠다.
 
팀 노트북은 또 어떡하지.. 작년의 경험이 있는 서리를 믿어본다.
 
내가 개선되어야 할 점은 일단 당장 생각나는건 집중력 이슈와 이해력 이슈이다.
대회 중에 옥테인은 춤을 추고 서리는 휘파람을 불어서 여기에 적응할 필요가 있을 것 같다. 그리고 누가 몇문제를 풀었느니, 누가 해주겠지 이런 생각은 줄이고 문제 풀이에 집중할 수 있도록 해야겠다. 그리고 서리는 평소에도 구현하다가 '야 이것 좀 봐봐'를 시전하므로 자잘한 도움요청에 낚이지 않도록 주의해야겠다.
이해력 이슈는 어떻게 해결해야 되는거지.. 그냥 남이 뭔가 설명할 때 잘 알아들으려고 노력해야지 뭐..
 
여담으로 대회가 끝나고 송씨랑 대회 얘기 하면서 small to large 처음 짰다는 얘기 했더니 맛있는 small to large 문제를 떠먹여줬다. 움냠냠.. 후기 다쓰고 풀려고 했는데 시간이 너무 늦어져서 자야겠다. (자야겠다 특: 해뜸)
 
지금까지는 성격이 성격이라 대회장에서 나혼자 내적친밀감만 갖고 혼자 있다가 나왔었는데, UCPC 본선은 이제 친한 사람들도 좀 생겼고, 팀도 있어서 기대가 된다. 본선 대회 만족스럽게 마무리할 수 있으면 좋겠다.