F.S.M.
ICPC Seoul Regional 2020에서 예상하지 못한 좋은 성과를 거두고선, 이번 2021년도 대회에는 같은 팀으로 욕심을 내며 출전하였다.
팀원은 나와 민제, 세빈이. 팀명은 FSM. 민제랑 세빈이가 JetPunk라는 십덕 세계지리 오타쿠 퀴즈 사이트에 빠져있었는데, 오세아니아의 국가, “미크로네시아 연방”(Federated States of Micronesia)이 좋았나보다. 사실, 작년 팀명인 “Let Us Win ICPC WF”의 최악의 작명자가 나라서, 나는 발언권이 없었다. 팀명을 “유한 상태 기계”(Finite State Machine)로도 해석할 수 있기에 재밌다고 생각했다.
후기글을 작년에 왜 안 썼느냐 하면… 대회 초반부터 결과 발표 직전까지 분위기가 내내 암울했어서 쓰고 싶지 않았다.
그러면 그걸 왜 이제 와서 쓰나면… 올해 World Finals 2021 자랑글을 쓰고 있는데, 얘를 안 쓰니 뭔가 글의 구성이 이상하다. 하지만, 지금으로부터 2년 전 이야기라 기억나는 게 별로 없었다. 그래서, 뇌리에 박힌 몇 가지 중요 이벤트만 적어본다.
ICPC Seoul 인터넷 예선
자기 반성과 연습을 많이 했기에, 예선은 부담없이 즐겼다. 그냥 셋 다 잘했고 F, G 빼고 전부 풀어서 1등을 했다.
F의 티어는 다이아 4라는데 못 풀어서 아쉽지는 않다. G는 내가 보자마자 풀었어야 했는데 그러지 못해 아쉬웠다.
ICPC Seoul Regional 본선
Before the contest
본선 진출 명단을 보고, 셋 중 둘만 제정신이면 무난하게 World Finals 진출권을 따낼 거라고 생각했다. KAIST 신입생 팀들의 실력이 가늠이 되지 않아, 우승 자신감이 100%에서 80% 정도로 떨어졌다. 난 이렇게 생각했는데 세빈이랑 민제는 어땠는지 모르겠다.
대회 초반
본선 대회가 시작했다. 주최측이 올려준 합본 pdf를 프린터가 읽어들이지 못했다. 우왕좌왕하다가 결국 각 문제별로 pdf를 다운로드 받아서 하나씩 인쇄했다. 작년의 그 악몽이 떠올라서 살짝 싸했다.
초반 한 시간 내내 서울대 The Elders 팀과 KAIST의 BabyPenguin 팀에게 질질 끌려다녔다. 솔브 수 차이까지 생겨서 다들 멘탈 빈약 상태였다.
60 ~ 150 min.
세빈이가 초반부터 F를 잡고 두 번 틀리더니 G.G.를 치고 멘탈이 깨졌다. 나는 G를 뚫은 다음 세빈이의 F를 뺏어서 풀기 시작했다.
남들은 찍어맞추는 E를 엄밀하게 증명하느라 심신 미약 상태가 된 민제는 K의 역겨운 구현을 마치고 시간 초과 판정을 받았다. 나는 “F, 개쉬운 DP 기초 문제인데 왜 못 풂?”을 시전하고 세빈이랑 똑같이 틀렸다. 이때가 대회 시간의 절반이 지나간 때였다.
중간 점검.
이때 상황을 정리하자면, 나랑 세빈이는 F, 민제는 K에 한 시간 가까이 발이 묶여있었다. 그런데 상위권 팀들은 모두 F, K를 풀었다. 걍 자살 마려웠다.
150 ~ 180 min.
F를 한 번 더 틀린 나는 “주최측 데이터가 틀렸다”를 시전하고 문제를 민제에게 유기했다. 그러고 나는 H, I, J를, 세빈이는 A를 잡았다.
지금 돌이켜보면 나는 절대 해서는 안되는 최악의 판단을 내렸다. 반드시 풀어야 하는 F, K를 둘 다 민제가 맡게 되었고, 민제가 받았을 압박감은 상당했을 것이다. 심지어, 페널티로는 가망이 없어서, 두 문제 뒤쳐지고 있는 상황에서 솔브 수로 이겨야 했기 때문에, 더이상 민제에게 남은 코인은 없었다.
압박을 이겨내고 민제는 20여분만에 F를 풀어주었다. 이때 칼바람보다도 싸늘했던 분위기가 수그러들었다.
대회 끝나고 나랑 세빈이가 F를 틀린 이유를 며칠동안 분석해봤다. 부분문제의 해가 원래 문제의 해와 연관이 있어서 답은 DP로 구할 수 있는 건 맞았다. 그런데, 부분문제의 해를 구성하는 “방법”은 원래 문제의 것과 연관이 없었다. 나랑 세빈이는 여기에 낚여서, 그 “방법”도 DP로 구하려다가 틀렸다. 민제는 여기까지 생각 안하고 모든 “방법”에 대한 답을 계산해서 함정을 피할 수 있었다. 생각이 깊어지면 틀린다. 이런 억까는 처음 당해본다.
191 min.
J를 잘 생각해보니, 내가 나는코더다 송년대회에 출제하려다가 제한의 상한을 증명하지 못해 안 냈던 문제랑 완전하게 똑같았다. 출제진은 상한을 증명했겠거니 생각하고 내 풀이를 그대로 짜서 맞았다.
여기서 우리와 상위권 팀들의 솔브 수가 같아졌다. 대회 중 처음으로 웃을 수 있었다.
191 ~ 240 min.
민제가 시간 초과로 고생하길래 Fenwick tree를 쓰라고 적당히 훈수를 두었다. 결국 민제가 K를 풀었다.
세빈이는 A의 거대한 구현량에 정신이 나가 미쳐있었다.
H랑 I가 남았는데, H는 case-work를 꽤 많이 해야 해서 출제진의 양심이 없는 거 같았다. 결국 개노답 기하 I를 잡았다.
민제는 뭐했는지 모르겠다.
240 ~ 300 min.
세빈이가 종료 17분 전에 결국 A를 해치웠다.
내 I 코드는 요리보고 조리봐도 정해인데 WA 판정을 받았다.
민제는 뭐했는지 모르겠다.
After the contest
프리즈된 스코어보드를 보면서 다른 팀을 열심히 분석했다.
대회 종료 10분 전 즈음에 서울대 The Elders 팀이 A를 제출하고, 더이상의 제출이 없었다. 일반적으로 대회 종료 직전에 WA 판정을 받으면 코드 여기저기를 고쳐가면서 마구 제출하기 때문에, 우리는 The Elders가 당연히 한 번에 A를 맞았으리라 생각했다.
KAIST의 BabyPenguin 팀도 종료 30분 전에 I를 세 번 제출했고, 그 이후로는 더 제출하지 않았다. I는 뭔가 잘하면 풀릴법한 기하 문제라서, 당연히 풀었을 거라고 생각했다.
두 시나리오 모두, 우리가 솔브 수는 같지만 페널티로 지는 ~Bad Ending~이다. 특히, 첫 번째 시나리오가 일어나면 서울대 2등이 되어버려서 World Finals 진출에 실패한다. 하지만, A의 풀이는 아주 직관적이고, 강팀인 The Elders가 A를 못 풀었을 리가 없기 때문에, 셋 다 소파에 엎드려서 암울하게 울고 있었다.
Unfreeze the scoreboard
대회가 끝나고 한 시간 반동안 스코어보드 공개가 이루어지지 않았다. 너무 괴로워서 배고파도 저녁이 먹고 싶지 않았다.
그런데, 이 모든 짓거리가 전부 비틱질이었다.
The Elders는 A를 못 풀었고, BabyPenguin은 H, I 둘 다 풀지 못했다. 뜬금없이 KAIST의 DO Solve 팀이 J를 해결하면서 우리와 솔브 수가 같아졌는데, 우리보다 페널티를 많이 쌓아둔 고마운 친구들이라서, 정말 다이나믹하게 우리가 우승할 수 있었다. 무슨 90년대 소년만화 최종화처럼 스토리가 흘러갔다.
이 상황이 생각할 수록 참 재미있다. 만약 내가 J를 송년대회에 출제했다면, BabyPenguin은 J를 해결하면서 우승했을 것이다. The Elders는 A에서 아주아주 사소한 코딩 실수를 했고, 대회 종료 직후에 찾아서 고쳤다고 한다. (라이벌 팀이지만 이 부분은 너무 공감되기에 진심으로 안타까웠다.) 내가 구상한 문제는 유출된 적이 없는데 이게 J로 똑같이 등장한 이 우연도 참 믿기지가 않는다.
결과만 놓고 보자면, 초반에 아주 부진했던 우리는 솔브 수로 역전하며 당당하게 우승했다. 그 비하인드에 수많은 억까와 행운이 있었지만, 뭐, 알빠노.
세 줄 요약
우리는 Seoul Regional 대회를 두 번 연속으로 우승한 유일한 팀이 되었다.
덕분에, 우리는 서로가 서로를 2023년까지 입대하지 못하게 견제하는 사이가 되었다.
그리고 그렇게, World Finals 2021은 우리에게 잊혀져갔다.