ICPC 2023 본선 후기 (망함)

 

팀 멤버는 armyantking (P1), invrtd_h (D1), 172635 (P5). 내가 작년에 리저널 28등을 했음에도 불구하고 (팀명은 codingMinsu) 올해도 그만큼의 성적을 기대하긴 힘든 상황이었다. 가장 큰 전력이었던 bbb1293 (D5) 형님이 졸업하셔서 더 이상 ICPC를 치지 못하시기 때문. 그래서 대회 치기 전에는 30-40등을 기대하고 있었는데(물론 목표는 28등 위로 올라가는 것) 예상보다 더 꼴아박은 49등이 나왔다. 여러 가지 이유가 있었는데, 일단 내가 카이스트 교환학생을 가 있었기 때문에 팀 연습이 아주 힘들었다는 것. 내가 172635 이 분을 열심히 갈궈서(?) 훈련을 시켰어야 했는데 그럴 여건이 안 됐다. 172635 이 분에게 큰 기대를 걸고 있었던 이유는 애드혹 장인이기 때문이다. 직관이 매우 뛰어난 것으로 보이는데 이게 내 성향과 배치되는지라 잘만 한다면 서로의 단점을 보완하는 완벽한 팀이 나올 수도 있는 상황이었다. 심지어 이 분은 

 

 

 대회 첫 출전에 퍼솔이라는 전무후무한 경력을 갖고 계신다. 심지어 저 H번 문제는 예선이 끝날 때까지 우리 팀 포함해서 단 2팀만이 푼 어려운 문제였다. 하지만 이 분의 단점은 23학번으로 경력이 많지 않아 자료구조 공부가 부족하고, 너무 직관주의적이라 시간복잡도를 잘 못 재는 것 등이 있었다. 근데 시간복잡도 재는 건 본선 당일 날 보시면 확실히 연습을 좀 해서 성장했다는 느낌이 들었다? 

 

 연습경시 때 Forbidden turns 문제가 나왔는데 나는 이 문제를 현장에서 풀었기에 나머지 두 사람이 푸는 거 그냥 보고만 있었다. 문제 풀어본 사람은 알겠지만 hash map 자료구조가 필요한데, 172635 이 분이 이게 hash map이라는 사실을 인지하지 못한 상태에서 hash map과 비슷한 역할을 하는 자료구조를 고안하기 위해 30000진 트라이(...)를 꺼냈다. 시간복잡도가 O(30000)인 게 좀 킹받긴 하는데 노베 상태에서 Trie라는 자료구조를 자기 손으로 직접 고안한 게 너무 신기하다. 여담이지만 Trie는 내 최애 자료구조다. 옛날에 객지프 조별과제 할 때 나도 내 손으로 직접 Trie 구현하곤 했는데 추억이 샘솟는다

 

 0:00 경시 시작

 

 7분째에 D가 풀렸길래 D를 잡으러 갔다. 평범한 파싱 문제라고 생각했는데 invalid한 input도 같이 주어지는 킹받는 문제였다. 나는 올바른 input이 주어지면 그걸 해석할 자신은 있는데 invalid input을 판별하는 정당하면서도 간단한 알고리즘을 만들 자신이 없어서, LR 파서 구현(...)에 들어갔다. 30분만 잡으면 금방 만들 줄 알았는데, 내가 LR 파서 구현 중 실수를 해서 20분을 추가로 날렸다. 결국 52분에 D AC.

 

 그동안 172635가 B를 잡고 있었고 armyantking이 I를 잡고 있었다. 나는 바로 G 풀이에 들어갔기에 이 둘이 무슨 생각을 하는지 몰랐던 상황에서 67분에 I AC.

 

 한편 도중에 172635의 B 풀이에서 시간복잡도 지키면서 제대로 구현하려면 PBDS Ordered Set이 필요하다는 걸 내가 지적했다. 그래서 내가 컴퓨터를 잡고 Ordered Set 구현을 시작...하려 했는데 하필 또 무지성 Ordered Set 꼬라박기는 안 되고 적절히 수정한 알고리즘이 필요한 상황이었다. 사실 내가 알고 있는 지식 선에서 Splay Tree나 Treap을 쓰면 바로 문제가 풀리는 상황이었고, 이때 주저 없이 Treap 구현을 시작했어야 올바른 선택이었다고 나는 생각한다. 하지만 B를 푼 팀이 많았고 저렇게 많은(?) 팀이 Splay Tree나 Treap을 무지성으로 꼬라박는 선택을 하지 않았을 것이라고 생각하고 '일단 좀만 더 생각해보겠다' 스탠스를 취했다.

 

 이후 1시간 30분 동안 G 풀이에 많은 시간을 박았다. 결론만 말하자면 엄청나게 말렸다. 나와 172635가 잘못된 접근법을 합쳐서 세 번이나 내서 불필요하게 많은 시간을 G에 잡아먹었다. 처음에 낸 풀이는 첫 카드의 숫자를 강제로 1 2 3 ... 로 바꿔주고 다음 카드도 비슷하게 한 뒤 강제로 이분 탐색을 하는 풀이였는데, 이후 문자열 해석이 어렵다는 걸 이분 탐색 짜고 나서야 알았다. 그리고 두 번째 풀이는 시간복잡도를 잘못 쟀다. 한편 172635는 제목이 힌트일 것이라고 생각하고 해시 기반 풀이를 짜고 있었다. 이게 뭔 소린가 하면 사실 문제 지문에 제시된 마술이 꽤나 유명한 마술이라서, 인풋이 적절하다면 'YES'라 답한 카드의 첫 번째 숫자를 전부 합하기만 해도 정답이 나온다. 하지만 나는 인풋이 임의로 들어오기 때문에 그런 접근법이 통하지 않을 것이라 생각했다.

 

 2시간 20분이나 지나고도 G가 풀리지 않았는데, 스코어보드를 보니 50팀 넘게 G를 풀었기 때문에 G 난이도가 골드 정도인 것이 확실시되는 상황이었다. 그런데 그동안의 대회 경험에 의하면, 골드 문제였다면 애초에 내가 풀었을 것이다. 여기서 완전히 멘탈이 터진 상황... 정신을 붙잡고 머릿속을 뒤져서 '골드는 골드인데 내가 풀 수 없는 골드 문제'를 탐색하기 시작했고, 실제로 그런 문제가 있었다.

 

https://www.acmicpc.net/problem/30237

30237번: 합집합

 

 최근에 풀었던 골드 5 문제 중에서 내가 40분이나 썼던 유일한 문제였다. 하필 또 절묘하게 저 문제도 집합 문제다. 그래서 저 문제의 키워드인 역추적이랑 비슷하게(백트래킹이 아니라 답을 역추적한다는 거임) 문자열로부터 숫자를 역추적한다는 아이디어를 세웠고, 그제야 AC가 나왔다. 190분에 G AC.

 

 이후 30분 동안 B 풀이를 생각하다가 Treap 없이는 도저히 이 문제를 풀 수 없다는 결론에 다다르고 Treap을 짜기 시작한다. 220분쯤에 B AC.

 

 한편 내가 H를, 172635가 J를 잡고 있었는데 둘 다 실패했다. 이미 다른 문제의 풀이를 내기에는 너무 늦은 시간...이었다. 사실 나는 될 거라고 생각하긴 했는데, LIS 짜는 방법도 잘 알고 있었고 실제로도 LIS 비슷하게 짰는데 예제가 나오지 않았다. 한편 J는 깡구현을 시도하고 있었는데 접근법은 대충 맞았다고 한다. 그러나 푸는 사람이 C++ 문법에 익숙하지 않아 전사했고, 지금 생각해 보면 내가 J를 172635가 H를 잡는 게 맞았던 것 같다. C++ 문법을 최대로 사용해서 정확하게 구현하는 건 내가 잘하니까. 다만 그렇다고 해도 내가 시간 내에 J를 풀 수 있다는 장담은 할 수 없다. digit dp도 내 천적이라...

 

 회고: ICPC의 신이 우릴 버렸다. 일단 나는 내가 작년에 비해 상당히 성장했다고 생각했다. 실제로 지난번 RUN ICPC Mock Contest에서 내가 Platinum I, II에 해당하는 두 문제나 풀이를 내는 데 성공해서(그중 Platinum II는 돌아가는 솔루션을 짜지는 못했지만) 상당히 자신이 있었는데, 하필 이번 대회에서 내가 잡고 있었던 문제들이 다 내 카운터 문제였다. D번 파싱 문제에서 LR 파서를 꺼내든 것도 내가 다른 간단한 스택 알고리즘들의 정당성을 증명할 자신이 없어서였고, B번은 팀원에게 문제 설명 듣자마자 Treap 꽂아넣을 용기(?)가 부족했고, G번은 위의 설명에도 나와있다시피 사실상 나를 저격하는 문제나 다름이 없었다. 코포에서 날 민트 퍼포를 내게 만들었던 문제를 ICPC에서 다시 만나다니... 문제 자체는 되게 좋았다고 생각한다. 내가 말려서 그렇지

 

 내 왼쪽이랑 오른쪽에 카이스트 팀이 앉아있었는데 다 14위권 안에 충분히 들어갈 것 같은 실력의 팀이었다. 근데 풍선 개수 보니 둘 다 초반에 좀 말린 것 같더라. 아 나만 말린 게 아니구나... 싶었는데 옆 두 팀은 복구에 성공했는데 나만 복구 못 했다. 루비쯤 되는 실력자들도 다들 말리곤 한다는 게 가끔씩 위로가 되는 것 같기도 한데 사실 잘 모르겠다. 걍... 담번에 잘할 수 있었으면 좋겠다.

 

 돌아가는 길에 팀원들끼리 담에는 다이아 다이아 루비 찍고 도전하자는 다짐을 했다. 근데 내 실력에 루비 5 가면 좀 쪽팔릴 것 같은데 아닌가