UCPC 2021 예선 후기

 나는 klimmek55와 Ryute와 함께 참여하였다. 팀명에 관해서는 아무도 의견을 내지 않았다. 그래서 팀명으로 0.001의 이득이라도 보자는 마인드로 팀명을 "신경 쓰이는 팀명"으로 지었다. 각각 닉네임은 '코가 간지럽다, 들숨 내뱉는다, 눈을 깜빡인다.' 라는 악질적인 닉네임으로 다른 팀들의 시간을 1초라도 뺏자는 생각이었다.
 이 외적으로 따로 준비를 하지는 않았다. 예선은 온라인으로 치기로 했기 때문에 디스코드 방을 만든 정도. 팀 대회 경험이 좀 있는 Ryute가 시작전에 여러가지 사항들을 알려주었다.

 Ryute가 ABC를 보고  klimmek이 DEF를 보고 내가 GHIJ를 보는 전략이었다. 맨 처음에 스코어보드에서 가장 빠르게 많이 풀린 문제는 ABC였다. 그래서 Ryute가 A를 빠르게 풀고 B를 풀러갔고, 그 사이에 klimmek이 C를 잡기 시작했다. 나는 GHIJ 중에 G가 가장 내 스타일이었기 때문에 G를 잡기 시작했다.

 Ryute가 A와 B를, Klimmek이 C를 꽤나 빠르게 풀어내는데 성공했다. klimmek은 자신이 본 문제 중 쉬운 문제인 D를 잡기 시작했고, Ryute가 스코어보드에서 많이 풀린 문제인 H를 잡았다. 기여도가 0이었기 때문에 좀 불안해졌지만, G는 깡 아이디어 문제였고, 그렇게 늦지 않은 시간에 풀어낼 수 있었다.

A : AC (Ryute, 00:05)  B : AC (Ryute, 00:16)  C : AC (klimmek, 00:19) G : AC (stonejjun, 00:26)

klimmek은 D의 풀이를 알아냈고, Ryute는 H가 골드 수준의 DP라고 선언하였다. 따라서 나는 새로운 문제를 잡아야 했고, 그 문제는 내가 본 문제 중 가장 내 스타일 같았던 I였다. I를 어떻게 재귀적으로 풀지 고민하고 있던 중 D와 H가 풀렸고 J를 풀자는 의견이 있어서 J를 다같이 고민하는 것으로 넘어갔다. 

D : WA (klimmek 00:31) H : AC (Ryute 00:38) D : AC (klimmek, 00:44)

 J를 보고 든 생각은 문자의 양을 잘 관리하는 문제. 맨 처음에 뭔가 센트로이드로 하면 잘 될 것 같아서 우리 팀에 센트로이드를 잘 아는 사람을 물어봤지만, 아무도 없었다. 그리고 좀 있다가 Ryute가 작은거큰거(smaller to larger)을 써야 할 것 같다고 했다. 
 풀이의 정황상 (U의 개수, P의 개수, C의 개수) 묶음을 기준을 잘 세워서 정렬을 해야 할 것 같았다. 잘 정렬을 해야 합치는 과정에서 smaller to larger 과정에서 시간 복잡도를 장담할 수 있다. 이때 U-P=0 이어야 하기 때문에 U-P로 정렬을 하면 될 것이라는 생각을 했고, 좀 더 있다 C-U-P=0 이어야 하기 때문에 두 번째 인자로 C-U-P의 값으로 정렬을 하면 될 것 이라는 생각을 했다. 
 그렇게 풀이를 거의 완성시키고, klimmek은 E를 잡고 Ryute는 코딩을 시작하기로 했다. merge 과정에서 Ryute가 set을 써야 한다고 했는데, 그럼 시간초과가 날 것 같아서, 나는 set을 안쓰고 스위핑 하는 방식으로 따로 코딩하기로 했다. 

 가장 큰 패착이었다. 분명히 small-to-large 인데 왜 갑자기 https://cubelover.tistory.com/31?category=169015가 생각이 났을까... 왜 merge 과정이 (작은 그룹의 크기 + 큰 그룹의 크기)에 대한 선형인걸까... 이상한 정보들이 머릿속에서 꼬이고 이상한 코딩을 했다. 심지어 낸 코드는 메모리 초과를 내는 무한 루프를 돌고 있는 것 같은 코드. 

 그래서 Ryute의 코딩을 기다렸지만, Ryute의 코드는 시간초과. multiset에서 count가 굉장히 느리게 작동을 하는 것 같다. 내가 코딩을 잘못했었지만, 그 과정에서 뒷 파트에서 시간을 줄이는 방법을 생각했었기 때문에 그 방법을 Ryute에게 알려줄 수 있었다. 다행히 Ryute의 코드는 그 부분 말고 다 완벽했고, AC를 맞을 수 있었다. 그리고 그 사이에 klimmek도 E를 풀어냈다.

E : AC (klimmek 02:23) J : AC (Ryute 02:26)

남은 시간 동안 F와 I를 보았지만 풀리지 않았다. F는 어느정도 보였지만, 시간복잡도가 될리가 없어보였다. 그렇게 8솔로 끝나게 되었다. 

 

 굉장히 내가 한 게 적다는 생각이 들었다. E 풀이를 전달해주지도 못했고, I를 관찰해낸 것도 아니며, J에서는 의미없는 시간낭비만 했다. 그리고 그 모든 원인은 딱 하나이다. "기본기 부족" 기본 실력의 부족이 뼈저리게 느껴졌다. 문제가 나랑 안 맞는 것도 아니며, 컨디션의 문제도 아니다. 그냥 내 기본 지식과 실력이 부족하다는 것을 크게 느꼈다. 
 이 대회가 내가 조언을 듣고 한단계 발전할 의지를 가지게 되는데 큰 기여를 하게 되었다.