UCPC 2024 예선 후기

ICPC 팀원 두 명이 모두 방학에 바쁘다고 탈주를 해버렸다. 그래서 고등학교 친구들(crescmoon, menzrach02)과 함께 즐겜팟을 꾸려 올해 UCPC에 참가하게 되었다. 즐겜팟이지만 나름 SNU X KAIST X MIT라는 멋있는 간판까지 달고 있는 팀으로, 본선 진출을 목표로 참가했다.

 

crescmoon은 PS를 잘 안 해서 그렇지 최근 코포 두 라운드의 퍼포먼스가 각각 퍼플과 오렌지인 재능충이고, menzrach02는 나한테 PS를 배우던 두세 달 이외에는 PS를 한 적이 없고 자기는 PS가 싫다고 주장하지만 나한테 배울 당시 BFS도 모르던 수준에서 시작해 몇 달 만에 CHT나 HLD 등 RUN 중급반 스터디 내용을 흡수하던, 마찬가지로 재능충이다. 그렇기에 가장 어려운 점인 "고등학교 친구 3명이서 3시간 동안 안 떠들고 집중을 하는 데에 성공"만 한다면 본선은 충분히 갈 수 있을 것이라고 생각했다.

 

팀 연습을 한 번 해보면서 대충 정해진 전략은, 일단 typical하거나 구현이 많이 들어가는 문제들은 내가 맡고, 애드 혹이나 수학맛 문제들은 crescmoon이 맡고, 진득하게 고민해야 하거나 많조분 느낌이면 menzrach02에게 맡기는 것이었다. 의외로 각자의 단점을 잘 커버하는 조합이라 신기했던 것 같다.

---

아래는 제출 기록에 따른 타임라인이다. 문제는 https://www.acmicpc.net/category/detail/4252에서 확인 가능하다.

 

00:02:20

3k+1번 문제를 읽기로 한 crescmoon이 A번을 풀었다. 나는 문제 제목을 읽자마자 브론즈겠거니 했는데 crescmoon은 "이런 쉬운 문제가 나오는 게 맞아?" 하면서 문제를 다시 읽느라 시간이 좀 걸렸다고 한다.

 

00:18:51

3k+2번을 보기로 한 내가 E를 제출했다. 순수 나이브가 도는 제한이라서 별 생각 없이 짰는데, WA를 받아서 당황했다.

 

00:27:03

10분 동안이나 버그를 못 찾다가 인덱스에서 j 대신 i를 쓴 부분이 있다는 것을 발견하고, 고쳐서 AC를 받았다.

 

01:22:13

거의 1시간 가량 제출이 없다가 crescmoon이 J를 제출했다. 그리디 느낌의 풀이를 증명했다고 했는데, TLE를 받았다. 애초에 시복이 제곱으로 예상되는 풀이였기에 crescmoon도 나도 살짝 예상한 결과였고, 조금의 관찰만 더 추가하면 풀이가 완성될 것 같았다.

 

01:27:57

내가 G를 제출해서 AC를 받았다. 처음에 나는 G를 보고 유파 문제인 것을 바로 알았지만 각 단위 정육면체를 자르는 방법에 따라 4조각씩으로 나누는 풀이를 생각하는 바람에 총 18가지 케이스워크라는 끔찍한 풀이를 짜고 있었다. 그런데 menzrach02가 내 코드를 보더니 "무슨 슈퍼마리오라도 만들고 있냐?"라는 말과 함께 8조각으로 나누는 풀이를 바로 떠올렸다. 이를 듣고 내 코드를 전부 날린 뒤 menzrach02를 숭배하며 코드를 짰던 것 같다.

 

01:50:11

J를 잠깐 미뤄두고 D를 잡던 crescmoon이 포기를 선언했다. 대충 풀이는 나왔는데 구현을 절대 못하겠다길래 내가 문제를 넘겨받았다. 읽어보니 정말로 풀이는 바로 보이는데 구현이 좀 어려워 보였다. 세그를 쓰는 방법이 생각났지만, 왠지 오버킬인 것 같아 조금 더 생각해 보니 set을 어떻게 잘 쓰면 된다는 사실을 알 수 있었다. 평소에 cin도 안 쓰는 내가 코드에 auto 같은 거 써가면서 이터레이터를 막 건드렸고, 불안함을 안고 제출한 결과는 AC. G와 J에서 유파와 set을 연속으로 쓰고 나니 우리 팀의 정직한 맛 담당으로서 1인분은 하고 있다는 생각이 들었다.

 

02:12:30

스코어보드를 보니 B, F, I를 제외하면 솔브가 꽤 많았다. 시간이 1시간도 채 남지 않은 시점, 느낌상 각자 한 문제씩은 더 풀어야 본선에 갈 수 있을 것 같았다. 그렇게 crescmoon은 J, menzrach02는 H, 나는 K를 잡았다. 처음으로 나온 제출은 crescmoon의 J였으나, 결과는 WA였다.

 

02:17:52

crescmoon이 J의 버그를 잡는 데 성공했고, AC를 받았다. 이후로 crescmoon은 C를 잡고 제한을 보니 왠지 제곱 DP일 것 같다는 나의 말대로 풀이를 떠올려보기로 했다.

 

02:27:22

menzrach02와 crescmoon이 H에 대한 이야기를 조금 하더니, menzrach02가 1트에 H를 맞췄다. 나중에 들어보니 엣지케이스가 많아 꽤 어려웠다는데, 역시 꼼꼼하긴 하구나 싶었다. 이후 menzrach02도 C를 보기 시작했다.

 

02:29:51

내 첫 번째 K 제출이었고, WA를 받았다. B가 홀수면 당연히 안되고, B가 2 이상이면 너무 자명한 해가 존재하므로 B가 0일 때만 해를 구성하면 되는 문제였다. 조금 생각해 보니 A=n에서 가능하면 A=n+3에서도 가능했고, A = 2, 3, 5, 6, 9를 제외하면 항상 가능하다는 결론이 나왔었다. 아무리 봐도 틀린 부분이 없어서 menzrach02에게 풀이를 설명했으나, 풀이는 맞는 것 같고 또 이상한 데에서 구현 잘못했지 않나 하는 결론이었다.

 

02:39:32

아무리 봐도 틀린 곳을 모르겠어서 우선 코드를 조금 정리했다. 처음에는 A가 8 이상의 짝수이고 B가 0인 케이스를 따로 빼는 등 필요없는 케이스워크가 코드에 들어있었기에 여기에서 문제가 났을 수도 있었을 것이라 생각했기 때문이다. 결과는 WA.

 

02:41:06

menzrach02가 혹시 A=B=0인 케이스 빼먹은 거 아니냐고 해서 다시 한 번 menzrach02를 숭배하며 풀이를 작성했지만, 다시 WA. 문제를 잘 읽어보니 A+B는 양수였다.

 

02:44:13

코드 정리의 느낌으로 역시나 필요없는 케이스워크였던 B=2인 케이스를 제거했다. 그랬더니 AC. 알고 보니 이 케이스에서 행과 열을 반대로 출력하고 있었던 것이다. 거의 우연히 버그가 잡힌 느낌이라 코드를 정리하지 않았더라면 끝까지 버그를 못 잡았을 수도 있었을 것 같았다. 아무튼 이렇게 우리는 최종적으로 B, C, F, I를 제외한 7문제를 풀게 되었다.

---

사실 끝나기 9분쯤 전에 내가 C의 풀이도 내긴 했다. 팀원들에게 DP라는 페이크를 던져줘 놓고서 나는 그리디 느낌으로 풀었는데, 바로 구현을 시도했으나 시간이 너무 부족했다. 오픈컨이 끝나고 문제가 공개된 이후에 시간을 재고 풀어봤는데 대충 20분 정도 걸렸던 것 같다. 만약 K에서 구현 실수를 안 했거나 G에서 처음부터 8등분을 했다면 C까지 충분히 풀었을 것 같은 느낌이었다.

 

올솔이 5팀이나 나온 것으로 보아 B, F, I도 다상위나 루비급은 아닌 것 같은데, 아예 고민할 시도조차 못한 것이 아쉽다. 본선에서는 crescmoon과 menzrach02는 처음부터 각자 잘하는 분야의 문제를 충분히 고민하게 하고, 내가 초반에 컴퓨터를 잡고 골드 이하의 정직한 문제들 구현을 최대한 빠르게 끝낸 뒤 플중위 이상의 자료구조 문제를 풀어내는 것이 최적의 시나리오가 아닐까 예상한다.

 

우리 팀은 최종적으로 36등으로 마무리했는데, 대충 50팀은 본선에 간다고 하니 특별 기준 제외하고도 충분히 본선에 갈 수 있을 것 같다. 개인적으로 작년 UCPC 분위기가 너무 좋았어서 올해 본선도 매우 기대중이다.