SCPC 2018 본선 후기

어영부영하다보니 어느새 SCPC 본선이었습니다. 작년에 5등상을 받을 당시엔 앞으로 1년동안 열심히 할거니 2018년엔 4등상 정도는 받을 수 있지 않을까 싶었는데 본선 날이 다가오면 다가올수록 코딩이 뭔가 마음먹은대로 잘 되지 않았습니다. 당장 전날 돌린 코포도 딱 A만 맞추고 나머지를 조져 98점이 깎여서 4등상은 커녕 수상은 할 수 있으려나하는 영 찜찜한 기분으로 대회날을 맞이했습니다.

또 Dinic / Hopcroft / rotating calipers / Aho corasick / Suffix Array 등과 같이 개념은 알지만 팀노트없이 짤 자신은 없는 알고리즘들도 차마 외울 엄두가 나지 않아 나오면 어떡하나 고민만 하고 외워가지를 못했습니다.

작년 SCPC랑 SCTF때 냉방을 너무 강하게 틀어 고생했어서 이번엔 긴 팔 옷을 하나 챙겨갔습니다. 대회 시작 전에 컴퓨터 세팅을 다듬고, Dinic과 Hopcroft 알고리즘을 좀 봤습니다.

작년 본선과의 큰 차이 2가지가 있는데,

1. 동점자간 등수 기준이 제출 횟수가 작은 순이 아니라 시간 페널티 순으로 변경되었습니다.

2. 각 문제의 제출 횟수가 100회로 늘어났습니다. 사실상 횟수 제한이 없는 것과 마찬가지였습니다.

작년에는 문제 난이도가 1<<<2,3<<<<<<<<4 이었어서 점수가 동일한 사람이 굉장히 많았고, 그로 인해 제출횟수로 3-4등상, 그리고 4-5등상이 갈렸습니다. 올해도 비슷하게 시간 페널티가 중요하지 않을까 싶었는데, 이번에는 휴리스틱 문제가 존재해 그렇지 않았습니다.(최상위권은 잘 모르겠네요.)

대회가 시작되고 1번 문제를 보는데 뭔가 느낌이 좋지 않았습니다. 사실 올해 예선이 이전 SCPC 예선들보다 훨씬 쉬웠어서 본선도 쉬우려나, 페널티 싸움이려나 싶었는데 본선이 아주 그냥 불타올랐습니다. 일단 1번 문제는 주사위를 굴리면서 이런저런 짓을 하는 문제였습니다. 전개도와 공간 상의 위치를 잘 대응시키고, 굴러가는 모양을 잘 캐치해 4차원 DP를 돌리면 간단하게 해결할 수 있는데 제가 공간지각력이 진짜 부족해서 너무 고생을 했습니다.

1번을 종이에 끄적거리다가 머리가 너무 꼬여서 일단 접어두고 2번을 봤는데 2번은 Suffix Array를 이용하면 쉽게 풀 수 있는 문제였습니다. 그러나 제 머릿속에 Suffix Array 구현 부분은 싹 지워진지 오래였고, 뭔가 꼬이고있다는 생각을 하면서 다시 1번으로 넘어와 힘겹게 구현을 했습니다. 1시간 12분째, 3번의 시도 끝에 AC를 받았습니다. 4시간 5문제임을 감안하면 3, 4, 5번 문제는 읽어보지도 못한 채로 1번 문제에서 72분을 허비한 상황이 매우 심각했습니다.

다시 2번을 풀려고 했으나 도저히 Suffix Array를 짤 자신이 없었기에 일단 subtask 1, 2만 맞고 넘어가자 싶어 짝퉁 Suffix Array를 만들어 O(N^2lgN)에 돌 코드를 제출했습니다. 그런데 subtask 2에서 계속 Runtime Error가 발생했습니다. 정황상 재귀의 깊이가 깊어져 Stack 메모리 1MB에 걸리는 듯 했고, 뭔가 큰일났다는 생각이 들었습니다. 일단 2번을 제껴두고 3번으로 넘어갔습니다.

3번은 N개의 파란 점과 빨간 점이 있을 때 파란 점과 빨간 점을 잇는 전선을 서로 겹치지 않게 최대한 많이 그리는 기하 휴리스틱 문제였고, 3번의 존재로 인해 어차피 동점자가 거의 발생하지 않을테니 시간 페널티는 별 의미가 없겠다는 생각이 들어 제출은 진짜 내키는대로 막 했습니다.

일단 subtask 1은 그냥 O(N!)에 해결이 가능해 빠르게 얻어냈습니다. 그 다음이 문제였는데, X 좌표 순으로 정렬을 한 뒤 반드시 전선을 이을 때 이전 전선보다 X 값이 무조건 크도록 연결하는 방식으로 제출을 해보니 256점 만점에 223점이나 획득했습니다. 이 때 남은 시간이 30분이었습니다. 이제 이 다음에 X 좌표 역순, Y좌표 순, Y좌표 역순 이 3가지를 더 해보면 점수가 더 높아지겠다 싶어 급하게 구현을 했는데 계속 MLE가 떴습니다. 시간이 너무 촉박해 오류를 바로잡을 엄두가 나지 않아 제껴두고 다시 2번으로 돌아갔습니다.

2번에서 이전의 코드를 들어내고 아예 parametric search를 동원해 코드를 갈아엎어 subtask 2까지 확보했습니다. 남은 시간은 10분이었고 Hash로 subtask 3을 얻기 위해 급하게 코딩을 하다가 시간이 끝나 그대로 대회가 종료되었습니다.

4, 5번은 진짜 문제를 훑어보기만 하고 단 1분도 쓰지 못했습니다. 1번 문제에서 너무 오래 붙잡혀있던게 그 원인인 것 같네요. 30분 남기고 3번에서 점수를 확 땡긴게 다행이었긴 했지만, 그래도 여러모로 아쉬운게 많았습니다.

총점은 100+90+223 = 413점이고 2, 3, 4번의 만점자가 각각 13/10/20명이라 턱걸이로 5등상을 받거나 수상을 못하겠다 싶었습니다. 결과 발표 전까지 상을 받았으면 좋겠다 하면서 계속 마음을 졸이고 있었습니다.

결론적으로는 (아마 턱걸이로) 5등상을 시상했습니다. 스크린에 제 이름이 뜰 때 기분이 어우.. 너무 좋았습니다ㅎㅅㅎ 5등상에 대략 600점 초반도 같이 묶여있는걸 보니 작년도 그렇고 올해도 정말 운이 좋네요. 수상자들 데리고 양재역 디오디아에 가서 저녁도 줘서 행복하게 먹었습니다. 끝나고나서 집에 오는데 너무 피곤했습니다. 4시간동안 정말 머리를 쥐어짰네요 ㅎ_ㅎ..

뭔가 전반적으로 참가자들 수준이 굉장히 상향된 느낌이었습니다. 코포 레이팅이 다는 아니지만, 코포로 비유를 하자면 레드 문턱에서 기웃거릴 정도는 되어야 평소 실력으로 4등상을 노려볼만 하고, 또 오렌지 문턱에서 기웃거릴 정도는 되어야 평소 실력으로 5등상을 노려볼만한 것 같네요. 올해는 해외 참가자가 베트남에서 온 대학생들밖에 없었지만 점차 일본, 대만과 같은 곳에서 상금 헌팅하러 오기 시작하면 입상이 점점 더 힘들어질 것 같습니다. 내년 이맘때에는 아마 알고리즘 공부를 사실상 접은 상태일테니 내년에도 얌전히 5등상만 받으면 좋겠습니다.

아 그리고 올해도 작년과 같이 마우스 + 키보드 + 장패드를 줘서 감사히 받아왔습니다 ^_^ 이전에 받은 키보드는 중고로 처분해야겠네요. 이제 굵직한 알고리즘 대회는 마무리됐으니 이번 주는 좀 쉬면서 느긋하게 육목 AI 개발하고 숭고한 캠프 준비도 하면서 보내야겠습니다!

<타임라인>

1시간 12분 : 1번 문제 AC

1시간 40분 : 2번 문제 subtask 1 AC

2시간 3분: 3번 문제 subtask 1 AC

3시간 30분: 3번 문제 223점 획득

이후 3번 문제 개선 하려다가 꼬임

3시간 50분 : 2번 문제 subtask 1+2 AC

이후 2번 문제 Hash로 subtask 3까지 얻으려다가 완성하지 못하고 대회 종료