M(IT)² Winter 2025 Beginner Round 5위 후기

학부생 신분을 유지하고 칠 수 있는 팀대회가 이제 정말 몇 안 남았다. 학위수여식이 2월 24일이니까 한 달 조금 더 남았고, 이제는 정말로 뒷방으로 물러나서 입문하려는 친구들을 데리고 경험시켜 주는 병풍이 되거나 아니면 수상권을 진지하게 노리지 않는 사람들끼리 모여서 즐겜을 하거나. 이번에는 즐겜팟으로 대회를 치뤘다.

2024 UCPC 때 내 실력 부족으로 예선에서 똑 떨어진 팀 B2M(nflight11, 0xchaser, we12223)이 재결성했다. 그 때 팀원 셋이 코포 블루, 코포 민트, OMC 블루라서 블루 둘 민트 하나로 B2M이었는데, 내가 코포를 접고 나서 내 위에 있던 치터가 날아가면서 1599점에서 1600점이 되어 추하게 블루 신분을 지켰다. 지금도 그래서 코포 기준으로 블루 둘 민트 하나고, 마땅한 팀명도 생각 안 나서 그냥 그 때의 팀 이름을 그대로 가져갔다. Advanced Division의 권장 참가 대상이 코포 블루~라서 이 멤버가 그대로 Advanced로 들어가면 수많은 레드에 치여 처참하게 죽을 것이 분명했다. 그냥 Beginner Division으로 참가를 넣었다.

5th B2M

그리고 536팀 중에서 5등 했다. 와우! 막판에 7번 문제를 뚫어 내서 높은 순위로 대회를 마칠 수 있었다. 처음에 들어가기 전까지는 상위 입상에 대한 큰 기대를 안 했는데, 막상 쳐 보니 또 각이 보여서 새벽 3시 40분에 시작한, 한국인에게는 가혹한 시간대의 대회였어도 끝까지 집중력을 잃지 않을 수 있었다.

난이도 순서대로 배열되어 있다고 하여, 3으로 나눈 나머지를 기준으로 문제를 배분했다. 0xchaser가 1 4 7번을, we12223이 2 5 8을, 내가 3 6 9를 잡았다. 물론 금방 자기가 잡을 수 있는 문제 잡기 메타로 바뀌긴 했는데... 간단한 대회 타임라인은 다음과 같다. WA가 좀 많았는데, 오답 페널티가 없어서 그것까지 기록하지는 않는다. 한 문제에 열몇번 박은 것도 있어서 그거 다 넣으면 너무 길어진다.

 

0:03:56 P3 AC (+), First Solve!

대회 시작하자마자 문제 보기 시작했다. TSP인데 점이 20만개라서 \(\mathcal{O}(N)\) 풀이밖에 없을 것이라는 것을 확신하고 접근하기 시작했다. 두 정점 사이를 이동하는 시간이 항상 \(|f(P)-f(Q)|\)의 꼴이고, 이를 최소화하는 방법 중 하나는 \(f(P)\)가 최소인 점에서 최대인 점으로 이동하며 \(f(P)\)가 작은 순에서 큰 순대로 모든 정점을 짚고, 돌아올 때는 출발점으로 바로 돌아오면 된다. 결국 \(2(\max f(P) - \min f(P))\)가 답이라는 걸 얻고 바로 구현해서 예제 돌리고 제출했다. First Solve를 먹었다. 나처럼 P3부터 본 사람은 없었나 보다.

0:08:58 P1 AC (+2)

0xchaser가 P1을 금방 풀어 냈다. 잡았다는 보고만 받고 문제를 볼 생각을 안 하고 있었다. 그 동안 나는 원래 봐야 할 P6을 보다가 이거 금방 답이 생각나지는 않을 것 같아서 바로 유기하고 P4를 보러 갔다.

0:15:06 P4 AC (+)

한 번 사전순 정렬을 해 주면 되는 문제였는데, 빠르게 제출하는 것에 정신이 팔려서 \(K\)번 정렬하는 비효율적인 풀이를 제출했다. 시간제한이 조금 너그러운 편이었기에 TLE를 받는 불상사는 일어나지 않았지만, 긴장해서 자명하고 쉬운 풀이를 놓쳤다는 사실은 조금 아쉽다. 그리고 소통에 오류가 있어서 원래 이 문제 담당이었던 0xchaser가 다시 제출하게 만들었던 점도. 디스코드 채널에 메세지 남기는 것으로 충분할 줄 알았다. 핑 할걸.

0:33:21 P2 AC (+3)

we12223에게서 구현 디테일로 인해서 틀린다고 헬프 콜이 들어왔다. 문제는 이 팀에서 나만 Python3 주력이라는 것이고 그렇기에 기존 코드를 수선하는 것을 내가 잘 못한다는 점이다. 그래서 그냥 문제를 보고 바닥에서부터 다시 짰다. 'M'을 기준으로 문자를 나누고, 나눠진 모든 component가 \(N>0\)에 대하여 'IT'*\(N\) 꼴인지 체크하는 것으로 진행했다. Python에는 좋은 문자열 함수가 많다. 덕분에 좀 날로 먹을 수 있었다.

0:54:26 P5 AC (+3)

그 뒤엔 P5로 갔다. 뭔가 번뜩이는 생각이 있어서 무작정 진행해 봤는데, 20개의 테스트케이스 중 13개에서 AC를 받았다. 풀이 방법 자체의 문제라기보다는 일부 로직에서 꼬인 게 있어서 손이 빈 we12223을 붙잡고 무작정 설명을 해 가면서 이게 정당한지 체크해달라고 하고 있었는데, 그러던 와중에 어디서 문제가 났는지 알아내서 고치고 맞았다.

Season NMKth bbak-daegari

로직이 아니라 업데이트의 문제였다. 코포 Div.2의 B~C번쯤 되는 문제였는데 이런 사유로 틀리다니 조금 부끄러웠다. 시차 탓으로 돌려도 될까?

1:05:24 P8 AC (+2)

오늘의 1등공신 0xchaser가 혼자 잠시 끙끙대더니 후반부 문제의 수급을 들고 돌아왔다. 뭐지? 어떻게 한 거지? 한편 나와 we12223은 P6을 관통하는 관찰을 찾으려고 하고 있었다.

1:10:09 P6 AC (+)

AAB와 BAA, ABB와 BBA를 바꿀 수 있다는 조건이 굉장히 까다롭게 보이겠지만, 사실 이 조건은 2칸 차이 나는 서로 다른 원소를 바꿀 수 있다는 것과 똑같은 소리고, 홀수 번째 요소와 짝수 번째 요소는 독립적인 데다 각 요소 내에 있는 A는 순서를 유지해야 한다는 상당히 강력한 조건이 붙는다. we12223과 처음에는 그래프 탐색인 줄 알고 이야기를 나누고 있다가 발상이 떠올랐고, 짧은 구현 후 AC를 따낼 수 있었다.

2:16:54 P7 AC (+13)

P9는 대회 치르던 당시 감각으로는 매우 끔찍한 구현 문제로밖에 느껴지지 않아서 7번 문제에 전부 달라붙었다. 뭔가 작은 수부터 삭제하는 방법이 항상 좋은 결과를 내지 않을까 하는 생각 하에 적당한 스프라그-그런디 코드를 냈지만 어림도 없었고, 0xchaser가 낸 코드가 테스트케이스의 상당수를 맞히고 있길래 파라미터를 가지고 이분탐색을 돌렸다. h가 100이면 하나 빼고 WA고 300이면 TLE라면 이 중간에 답이 있을 것이라는 강력한 믿음...

그리고 그 믿음은 PBA로 돌아왔다. 맞히면 장땡이잖아...

 

이후 몇 분 동안 P9와 스코어보드를 번갈아 가면서 꼬라봤다. 큰 수확은 없었고, 누가 마지막까지 P5를 안 풀고 있었다가 끝나기 직전에 풀어서 한 순위 밀렸다.

 

오랜만에 제법 괜찮은 경험이었다. ICPC 이후로는 석사 과정을 밟고 있어도 받아주는 UCPC를 제외한다면 더 이상 팀 대회를 칠 기회가 없을 것이라고 여겼다. 비록 시간이 조금 무자비하긴 했지만...