제 5회 국민대학교 알고리즘 대회 후기

2주 전에 예선을 치르고 난 뒤 오늘 국민대학교에 직접 가서 제5회 국민대학교 알고리즘 대회에 참가했다. 그냥 후기를 한 번 남겨보려고 한다.

예선

예선은 7월 31일 금요일 오후 2시에 치뤄졌다. 온라인 예선이었고, 방식이 굉장히 독특했다. 일단 그전에 사전점검을 통해서 4가지를 점검했다. 노트북 화면, 노트북 카메라, 핸드폰 카메라, 음성. 

대회는 2시부터 시작하며, 1시간 동안 가만히 앉아서 대회를 치루는 과정에서 노트북 화면, 노트북 카메라, 핸드폰 카메라, 음성의 4가지를 계속 송출한다. 정말 머리가 좋은 방식이었다. 참가자 본인이 확실하게 다른 불법행위를 저지르지 않고 계속해서 대회에 참가를 하고 있는지를 거의 완벽하게 확인할 수 있는 세팅이었다. 이 방법을 생각해낸 대회 관계자 분들께 정말 찬사를 보내고 싶다. 
하지만 이런 과정 때문인지 15분이 늦게 시작이 되었으며, 그 공지는 약 4분 후에 알려주었다... 아무튼 15분에 대회가 시작되었다.

예선 문제는 공개해도 되는지 안되는지 확실하지 않지만, 일단은 공개를 안 하려고 한다. 난이도는 굉장히 쉬웠다. 딱히 어려울 것이 없었다. 약 실~골? 아무튼 무난하게 28분 컷을 내고 잤다. 대회가 끝나도 화면을 끊을 수 없었기 때문에 책상 좁은 공간에 엎드려서 불편하게 잤다. 

본선

본선 고사장에 조금 일찍 도착했다. 대회 시작은 2시인데 입실은 1시 10분 까지이고, 그 와중에 50분에 갔는데도 줄을 서서 입장을 하고 있었다. 코로나 때문에 입장을 할 때 철저한 방역과 함께였다. 
들어갔는데 학생증으로는 확인이 안된다더라... 청소년증이 학생증인 줄 알았다. 결국 나중에 여권을 다시 가져오기는 했지만.

아무튼 들어갔다. 굉장히 철저한 방역의 느낌이 진행되고 있어서 만나고 싶었던 사람들은 만나러 갈 수는 없었다. 화장실에 잠깐 들렸다가 자리에 앉았다.

역시나 50분동안 접속, 핸드폰 수거 외에는 아무것도 시키지 않았다. 이럴 거면 왜 이렇게 일찍 불렀나 의문이다. 하지만 나는 그 시간에 세그, dfs, 다익을 짜면서 손을 풀었다. 그리고 대회는 시작되었다

본선은 문제의 아이디어를  유출하지 말라는 엄중한 경고가 있었기 때문에 최대한 문제를 밝히지 않으면서 말을 할 예정이다.

예선을 통해서 문제의 난이도는 대충 예상이 갔고, 거의 코포마냥 완전 타임어택 싸움이 될 것이라고 예상을 했다.

문제 1

끝나고 주위에서 풀이를 들어보니 dfs로 가볍게 풀었다고 하더라. 하지만 나는 일단 처음에 딱 보자마자 위상 정렬이 생각이 났다. 이는 완벽히 잘못된 식을 가지고 풀고 있었던 것이었다. 하지만, 나는 일부분만 잘 고치고 베이스는 위상 정렬 내에서 계속하고 싶었다. 제한은 10000이었지만, 데이터가 약할 것이라는 믿음을 가지고 위상 정렬을 계속 베이스로 깔고 최악 $O(N^3lgN)$짜리 풀이를 짰다. 사실 빨리 풀어야 한다는 압박감에 시달렸다. 근데 맞았다. 애초에 시간제한 자체가 없는 문제였다... 더 웃긴 것은 0.3s? 정도에 굉장히 빨리 돌았다는 점이다. 대략 25분 정도에 풀었던 것 같다.

문제 2

굉장히 급박한 상황이었다. 1번에서 전을 좀 구었기 때문에 더 빠르게 풀어야 한다는 압박감을 가지고 있었다. 2번 문제는 좋은 문제였다. 문제 내용 자체는 좋았는데, 문제 스크립트와 예제에서 의도가 굉장히 다분했던 것 같다. 끝나고 몇 명을 물어보니까 다들 문제를 잘못읽었었다. 문제 자체는 쉬워서 정말 금방 풀 수 있었을 것 같다. 
결국 뇌절에 뇌절을 오지게 박고서야 겨우 문제를 풀어냈다. 내 풀이는 unoin&find에 lower_bound를 곁들인 풀이었다. 시간은 대충 1시간을 조금 넘겨서 풀었고, 1시간 이후부터 퇴실이 가능하기 때문에 다 풀고 바로 퇴실했다. 

끝나고 나왔는데 이미 한 4명 정도가 나와있던 것 같다. 물어보니까 33분,35분,38분이 각각 한 명씩 있더라... 뇌절을 정말 많이 박기는 했는데, 시간 차이를 듣고 애초에 가망이 크게 없었다는 것을 깨달았다. 대충 6등 안에는 들어서 동상은 탈 것 같은데, 운이 좋으면 4등 정도 해서 은상도 탈 수 있을지 모르겠다.

한동안 쉬고, 요즘 코딩 성적과, 대회 코딩 성적이 정말 처참했던 것을 감안하면 그래도 나쁘지 않은 성적이었다. 오늘을 바탕으로 이후 대회에서 더 좋은 성적이 있기를 바란다.