UCPC 2023 예선 후기

작년 이맘때 solved.ac 디스코드에서 UCPC 이야기를 하는 대학생들을 보면서 뭔가 부러웠던 적이 있었다. 그렇기에 대학생이 된 올해 UCPC는 꼭 참여하고 싶었고, 얼마 전 짜여진 ICPC 팀원들과 참여하게 되었다. 팀원은 이예린(abra_stone) 누나와 이서현(seorii) 형. 팀명은 딱히 생각나는 게 없어서, 이서현 형이 팀명을 정하는 도중 보낸 이모티콘에서 딴 "안아줘요"로 정했다. 우리는 아직 팀 대회는 커녕 팀 연습도 해본 적 없었기에 대회 시작 직전에야 작전 논의를 시작했다. 어디선가 본 후기글을 떠올려 이서현 형이 3k, 내가 3k+1, 이예린 누나가 3k+2번 문제를 잡기로 했다.

---

(00:02)
A번이 노솔 방지용 브론즈길래 빠르게 AC. 3k+1 규칙에 의해 D번으로 넘어갔다.
 
(00:11)
D번도 코포 div.2 A~B 정도의 실버 문제이길래 바로 AC. G번으로 넘어갔으나 읽자마자 플레의 느낌이 나서 일단 K번으로 넘어갔다(원래 J번으로 넘어갔어야 하지만... 총 10문제로 착각하는 바람에 마지막 문제가 3k+1일 줄 알았다). 이서현 형은 C가 기하+mst인 것은 알겠으나 기하 이슈로 구현이 더러울 것 같아서 일단 다른 문제부터 읽었고, 이예린 누나가 B는 스몰투라지라는 아이디어를 낸 후 구현을 시작했다.
 
(00:26)
스코어보드를 보고 I를 잡던 이서현 형이 첫 제출을 했으나 컴파일 에러. C++ 표준이 아닌 것을 사용했다고 한다. 바로 다시 제출했으나 의문의 TLE. 이예린 누나와 디버깅을 시작했다.
 
(00:36)
K에서 그리디스러운 관찰을 했으나 진척이 없어서 포기하려다가, 스코어보드를 보고 문제가 어렵지 않을 것이라는 믿음을 가졌다. 잘 생각해보니 답에 대한 이분탐색을 섞어주면 되는 문제였다. queue를 이용해 구현했는데 초기값 하나 안 넣어줘서 WA 한 번 받고 AC. 그 사이에 I번 AC가 나왔다. 알고 보니 세그를 짜야 할 자리에 코파일럿이 이분탐색을 넣어놨다는 모양. K번 AC 이후에는 이서현 형이 F가 열심히 시뮬레이션 돌리는 문제라길래 읽기 시작했다.
 
(00:56)
드디어 이예린 누나의 B 구현이 끝났다. 구현이 끝나고 나서 하는 말이 "이게 내 첫 스몰투라지 구현이야..."여서 모두 긴장했지만, 한 번에 AC. 역시 짬에서 나오는 바이브는 강했다. C번을 제외하면 풀이가 바로 보이는 문제들은 전부 해결했기에 이서현 형이 다시 C를 잡고, 나는 F를 잡았다. 이예린 누나는 일단 대놓고 수학인 E와 아무도 못 푼 J를 제외한 문제들을 읽어보기로 했다. 
 
(01:36)
한동안 아무도 말이 없다가, 이서현 형이 C번 AC. 나는 F를 계속 붙잡고 있었지만 딱히 진전이 없었다. 왠지 행렬 곱이나 연산의 교환을 잘 쓰면 될 것 같다는 말만 반복했다. 이서현 형이 C를 풀었기 때문에 F를 넘겨주고 E를 잡았다. 남은 문제들 중 내가 풀 수 있는 유일한 문제라고 생각했다. 기댓값의 선형성을 이용해 반전수의 기댓값을 구하는 점화식까지는 쉽게 구해냈고, 제곱의 점화식도 구했다고 생각했다. 이때 했던 말, "20분 안에 풀고 F까지 풀수 있을듯."
 
(02:40)
1시간 만에 제출이 나왔다. 이서현 형의 F였는데, 결과는 RTE. 이후 CE, TLE를 거쳐 결국 AC를 받아냈다. 풀이를 들어보니 내가 하려던 이상한 관찰들 거르고, 적당히 짝홀짝홀 따져가며 시뮬레이션 하는 문제였다. 알고 보니 내가 F번은 문제 이해 자체를 잘못 하고 있었다. 본선 진출권으로 예상되는 7솔을 따낸 후, 이예린 누나는 H, 나는 E를 잡고 "이거 분명히 할 수 있을 것 같은데"를 외쳤다.
 
(02:55)
이예린 누나가 시간이 30분만 더 있었으면 구현이 가능했을 것이라고 하며 H 포기 선언을 했다. 나는 1시간 반 동안 E의 예제 2가 왜 안 나오는지 이유를 찾지 못하고 있었다. 다른 팀원들은 풀지 못한 모든 문제에 print("안아줘요")를 제출하기 시작했다. 결국 시간이 종료되며 7솔로 마무리.

---

결과적으로, 40등을 찍고 본선 진출이 가능했다. 본선 진출이 44팀이었으니 꽤나 턱걸이었다고 할 수 있다. 어쩌면 우대 조건 진출일 수도 있겠다 하는 생각이 들었다. 에디토리얼을 보니 E에서 식을 세우는 과정에 내가 하나 실수한 부분이 있었던 것 같다. 통계 공부를 다시 해야 하나... 아무튼 본선 진출했으니 성공!
 
이번에 나는 3시간 중 앞 40분에 브, 실, 골을 하나씩 푼 것 이외에는 사실상 팀에 기여한 부분이 없었다. 이서현 형과 이예린 누나가 각각 플레 하나씩은 풀어냈던 것을 생각하면, 본선에서는 E에 1시간 반 이상을 박고 예제 통과를 못하는 일은 없어야 할 것이다. 성공했다면 대회 중에 D3을 풀어낸 캐리롤이 되었겠지만... 나름 수학 담당을 자처하는 만큼 더 연습이 필요할 것 같다.