1. 배경
감사하게도 KAIST의 PS동아리 RUN의 봄 대회가 작년과 마찬가지로 외부인 참가를 받게 되었다. 그래서 기다리고 있다가 참가 신청이 열리자마자 빠르게 휴가를 쓰고 신청했다.
작년 ICPC 이후로 대회를 하나도 나가지 못했다. 겨울에는 대회가 거의 안 열려서이기도 하지만, 월간 향유회와 세미게임컵이 열렸음에도 개인 사정으로 참가하지 못했다.
따라서 이번 대회가 작년 ICPC 이후 6개월만에 참가하는, 그리고 군입대 이후 처음으로 참가하는 PS 대회가 되었고, 많은 기대를 하며 참가 신청을 했다.
또한 백준이 없어진 세상에서 개최되는 첫 대회였기에 분위기가 어떨지 궁금하기도 했다. 백준이 없어지면 대회 참가자들이 점점 줄어들고 대회도 점차 없어지지 않을까 걱정했는데, 이번 대회에서만큼은 그렇지 않은 것 같아 다행이다.
BIKO라는 플랫폼을 처음 써보기에 익숙하지 않아서 손해보는 건 없을까 걱정도 약간 했다.
대회를 나가기 위해 5/3~5/4에 1박 2일로 휴가를 나가는 계획을 세웠다. 이틀 다 휴무일이고 휴가를 1박 2일로 쓰는 거 자체가 통상적으로 손해라고 여겨지지만 어쩔 수 없었다.
그래도 나가고 싶었던 대회를 나가게 됐으니..! 오랜만에 보고싶었던 사람들도 많이 만나고 대회도 재밌게 치고 와야지!라는 생각을 하며 대회날이 되길 기다렸다.
2. 대회 전
첫 휴가때 너무 많이 신이 나서 새벽 4시에 기상해버리는 이슈가 있었어서 이번에도 그러지 않을까 걱정했지만, 다행히 오전 6시반에 맞춰둔 알람을 듣고 기상하였다. 대충 준비를 하고 7시 10분쯤 밖으로 나왔고, 8시에 학교 동아리방에 도착하였다.
동아리방에는 아무도 없었다. 나는 빠르게 내 옷과 노트북을 챙기고 팀노트를 인쇄한 뒤 기차를 타기 위해 광명역으로 향했다.
광명역에 너무 빨리 도착해서 체스 몇 판 정도 하다가, 9시47분~10시33분 기차를 타고 대전역에 도착했다.
대전역에서 같은 대회에 참여하는 leo020630(ICPC레전드), sapple(동아리 후배), nabina1395(동아리 후배)를 만나 간단히 칼국수를 먹고, 택시를 타고 대회장으로 갔다.
대회장에서는 dadas08 등 몇몇의 아는 사람들과 인사를 나누었다. 사실 내 대회 닉네임을 dadas08로 신청했는데 놀래키기 위해 말을 안 했다. 이후 2달만에 켜보는 노트북이 제대로 작동하는지 확인하고, 대충 자리 세팅을 한 뒤 대회가 시작하기를 기다리고 있었다.
그런데 갑자기 아까 탄 택시의 기사님께 전화가 와서 내가 택시에 수첩을 두고 내렸다는 것이다. 감사하게도 택시비 조금만 더 받고 다시 갖다 주신다고 하셨는데 문제는 대회 시작 시간인 13시쯤에 도착하신다고 하셨다. 그래서 일단 운영진이신 ibm2006님께 사정을 설명한뒤 대회중이탈허락을 받아놓고 대회 시간 날릴 것을 걱정하며 자리에 앉아있었다. 다행히 12시 55분쯤에 빨리 도착하셨고 무사히 13시에 대회를 시작할 수 있었다. 큰일날뻔했다ㅠㅠ
3. 대회
문제가 난이도순인 지 아닌지 잘 몰랐지만 그렇다고 믿고 A번부터 보았다. A번은 간단한 애드혹그리디(?) 문제였다. Freivalds' Algorithm의 증명에서 나오는 '나머지는아무렇게나하고하나만제대로정해면된다' 아이디어가 생각나서 그걸 적용했더니 바로 풀렸다. 풀고 나니 스코어보드에서 3등인가 4등이길래 시작이 좋다고 생각했다.
B번은 조합론 문제였는데 피보나치수열이 나오길래 '빠른행렬제곱으로피보나치구하기'를 짰다가, 알고보니 수가 너무 커지면 의미가 없어져서 대충 n이 작은 경우에만 계산해주면 되는 문제였다. 이걸 생각하는데 좀 오래걸려서 아쉬웠다. 몇 번의 카운팅 실수 후 AC를 받았다. 100번째 피보나치수를 행렬제곱으로 구하는 멍청한 코드가 BIKO에 박제되어 있다.ㅠㅠ
스코어보드를 보니까 D번이 C번보다 훨씬 많이 풀리길래 D번부터 보았다. D번은 파라메트릭서치+그리디를 한번 하고 파라메트릭의 결과를 이용해 다시 한번 그리디를 하면 풀리는 문제였다. B보다 훨씬 쉬운 느낌이었다. 그런데 구현해서 제출하니 계속 0점이 나왔다. 나는 BIKO에서 채점 결과를 누르면 WA인지 TLE인지 등등을 알려준다는 것을 알지 못하고, 그냥 0점이라길래 아니이거왜안알려줌 이라고 생각한 뒤 WA라고 가정하고 디버깅을 했다. 알고보니 multiset을 써야하는데 set을 써서 생기는 WA와 set에서 lower_bound를 하는데 S.lower_bound(x)가 아니라 lower_bound(all(S), x)를 써서 생기는 TLE가 모두 있었다. TLE라는 것은 스트레스를 돌려도 알 수 없다 보니 이를 알아내기까지 시간이 상당히 끌렸다. 아마 D에서 40분정도 쓴 것 같다. TLE인걸 알았다면 금방 고쳤을텐데 아쉬웠다. BIKO를 미리 써 보지 않은 내 잘못이다.
C번은 확률 계산 문제였다. 내가 잘 푸는 종류의 문제여서 쉽게 풀었다. 이것도 B보다 쉬운 것 같다. 확률 수열의 생성함수의 convolution 여러번을 O(N^2)에 한 뒤 각 쿼리에서 추가적인 처리를 O(N)에 해주는 식으로 풀었다. (굳이 생성함수를 알아야 하는 건 아니고 그냥 조합론 풀이인데 그걸 생성함수로 보면 편한 것 같다)
E번은 xor한것들중 k번째값 찾기 문제였는데, XOR MST와 세팅이 비슷해서 트라이로 풀면 되겠다고 생각했다. k번째값 찾기에 파라메트릭 서치를 이용하는 것도 많이 나오던 아이디어기 때문에 쉽게 떠올렸고, 트라이+파라메트릭으로 풀었다. 트라이 구현을 오랜만에 해봐서 잔실수가 조금 있었지만 그래도 너무 늦지 않게 해결하였다.
E까지 다 풀고 500점을 띄우고 나니 2시간이 지나 있었다. 이때 7등이었고 3시간이 남았으니 잘 하면 수상도 노려볼 수 있겠다고 생각했다. 그런데...
F번을 읽어보니 딱봐도 순수능지가 필요한 애드혹해구성 문제였다. 이는 내가 굉장히 좋아하는 유형의 문제였다. 그리고 스코어보드에 솔브가 조금씩 나오기 시작했기 때문에, 적당히 풀 만한 문제라고 생각했다. 그래서 대충 1~2시간쯤 써서 F번을 풀고 나머지 문제의 서브태스크를 긁어서 상을 받자! 라는 계획을 세웠다.
대립의 신전이 있으면 그걸 찾고 없으면 없다는 걸 이용해서 경로에 정점을 하나씩 추가해 나가는 풀이가 자연스럽다고 생각했다. '하나씩 추가해 나간다'와 관련된 풀이에서는 수학적 귀납법이 상당히 강력한 도구이기에 귀납법을 사용해 이리저리 생각해봤으나 풀지 못했다. 이외에도 BFS트리 등 다양한 풀이를 생각해봤지만 풀 수 없었다.
포기하고 다른 문제를 볼까 했지만 스코어보드에는 F가 솔브가 가장 많기도 하고 F가 가장 앞문제다 보니 가장 쉬운 것이 분명하다고 생각했다. 또한 어짜피 다른 문제를 다 긁더라도 6솔을 하지 못하면 높은 순위는 어렵겠다고 생각했다. 물론 서브태스크 대회에서 풀태스크 노리기보다는 서브태스크 긁기가 저점 방어를 위한 좋은 전략이라는 것이 정론이지만, SCPC 같이 꼭 n등 안에 들어야 하는 목적이 있는 것은 아니니 고점을 한번 노려보고 싶었다. (사실 F를 풀 수 있을 줄 알았다)
그래서 F에 모든 시간을 투자하기로 하고 약 2시간 40분 동안 생각할 수 있는 모든 풀이를 시도해봤으나 풀지 못했다. 익숙한 기분이었다. 쉬운 문제를 다 해결한 뒤 남은 문제에서 도저히 풀이 비슷한 것이 생각나지 않을 때의 무력감을 이전의 많은 대회에서 느꼈었는데, 오랜만에 다시 느낄 수 있었다.
20분쯤 남았을 땐 어짜피 풀이가 나와도 못푼다고 판단하고 추하게 F에서 30점, I에서 9점을 긁고 539점으로 마무리했다.
4. 대회 후
대회 끝나고는 너무 머리를 썼는지 많이 피곤했다. 대회를 오랜만에 해서 그런 것 같다. PS체력도 연습하면 늘고 안하면 주는 건가 보다.
대회를 같이 친 사람들과 문제 얘기를 하면 좋았겠지만 피곤하기도 했고 G~I는 거의 읽어보지도 않아서 할 얘기가 없었다. 기다리다가 해설을 듣고 스코어보드 구경을 한 뒤 단체사진을 찍고 대회가 끝났다.
스코어보드는 백준에서 할 때처럼 한 문제씩 까는 그런 기능은 아쉽게도 없었고, 그냥 스크롤을 맨 밑으로 내린 뒤 한 칸씩 올리며(...) 시상식을 했다.
나는 22등을 했고 상당히 아쉬운 등수지만 F를 못푼 시점부터 예상했기에 별 생각은 없었다.
진짜dadas08인 undertaker는 대회2등을 했는데 짭dadas08은 22등이라니ㅠㅠ undertaker보다 높은 등수를 해서 분탕을 치고 싶었는데 아쉬웠다.
대회 일정이 끝나고는 KAIST RUN 대회가 있을 때마다 가던 뒷풀이 장소에 가서 leo020630, petamingks, man_of_learning님, 그리고 처음 뵙는 한양대 분들과 같은 테이블에 앉아 이야기를 나누며 치킨과 맥주를 먹었다. 나름 도움이 되는 얘기도 많이 하고 재밌었던 것 같다.
5. 후기
- 대회를 망쳤으니 당연히 기분이 좋지는 않았다. 그래도 예전처럼 진심으로 PS를 하는 게 아니라 반쯤 접은 상태였기에 사실 별 생각이 안들었다. 그냥 아 대회 망했네 ㅠㅠ 정도였던 것 같다. ICPC 준비가 한창일 때 이랬으면 멘탈이 완전 나가 있다가 오기가 생겨서 더 열심히 공부했을 것 같은데 지금은 안 그렇다.
- 근데 이렇게 대회 성적에 진심이 아니게 되니까 오히려 PS가 재미없어진 느낌도 있다. 예전에는 대회를 준비하면서, 또 대회장에서 경쟁하면서 짜릿한 감정을 많이 느꼈었는데, 아무래도 대회를 준비하지 않고 참가만 하다 보니 어쩔 수 없이 그런 재미가 줄어드는 것 같다.(물론 재밌는 문제 풀고 좋은 사람들 오랜만에 만나고 그런 부분은 여전히 좋았다. 휴가 2개 쓴 게 아깝지는 않다) 그렇다고 PS를 다시 열심히 해볼까 싶어도 ICPC는 1.5년 뒤에나 나갈 수 있고 백준도 없어져서 딱히 의욕이 생기지 않는다. 뭔가 인생의 목표가 사라진 느낌이다. 대학을 다니는 3년 동안 가장 열심히 한 게 PS였는데 그게 사라지니 마음이 공허하다. 그래서 앞으로 뭘 할지에 대한 고민을 많이 하고 있다. 무엇을 하면 다시 짜릿한 기분을 느끼며 살 수 있을까?
- 문제 해설을 들을 때 다른문제 해설은 대충 들었지만 내가 대회를 망친 이유인 F 해설은 열심히 들었는데, DFS 한 번만 하면 자동으로 모든 게 해결되는 엄청나게 아름다운 풀이가 있었다. 다만 아무런 정보도 없는 상태에서 그걸 떠올리기는 너무 어려운 것 같다. 내가 생각했던 것들과 아예 다른 종류의 풀이였다. 풀어야 할 문제를 못 푼 것은 아니라 그냥 실력 부족이라 차라리 다행이라 생각했다. 이걸 알았다면 뒷문제를 보는 게 좋은 전략이겠지만 이렇게 어려울 줄 몰랐기에 어쩔 수 없었던 것 같다.
- 군대 오기 전에는 휴가를 쓰고 대회를 나가는 게 되게 어려울 줄 알았는데 막상 해보니 피곤하긴 해도 괜찮은 것 같다. 휴가가 딱히 아깝다는 생각은 안 들었다. 사실 휴가 나가서 할 것도 딱히 없어서 앞으로도 대회 있을 때마다 나갈 것 같다. 다만 군대 와서 구현력이 좀 많이 떨어진 감은 있다. D번에서 lower_bound 실수는 원래 자주 했어서 대회 때는 항상 조심하면서 코드를 짰었는데 오랜만에 하니까 다 까먹은 것 같다.
- dadas08은 이번에 IOI 국가대표 선발고사에서 1등을 했는데 이번 대회에서도 2등을 하는 걸 보니 요즘 폼이 상당히 좋은 것 같다. 앞으로의 미래가 기대되는 사람이다.
- 백준이 없어진 이후의 첫 대회가 성공적으로 마무리되었다. 갑작스러운 사고에도 불구하고 운영진 분들이 많이 수고해주신 덕분인 것 같다. BIKO라는 플랫폼을 처음 써봤는데, 생각보다 큰 이질감은 안 들었다. 백준 말고 다른 플랫폼에서 열리는 대회도 나쁘지 않은 것 같다. 5월에 내가 운영진인 SCSC 대회(많은참여부탁드려용)도 있고 각종 교내대회도 많은 걸로 아는데, 이런 대회들이 다 잘 열리고 사람들이 관심을 많이 가져서 백준이 없어진 한국의 PS환경이 빨리 안정화되었으면 좋겠다.
긴 글 읽어주셔서 감사합니다 !