NYPC 2020 본선 후기

NYPC 2020 본선에 진출하였다. 이번에 코로나 때문에 사람 수를 절반으로 줄여서 본선에 가기 더 힘들어졌지만 만점을 받았기 때문에 넉넉하게 본선에 갈 수 있었다. 그 와중에 우여곡절이 좀 있었지만 그건 노코멘트...

SRT를 타고 가서 SRT를 타고 왔다. 가는 길에 잠을 아주 잘 잤는데, 역에 도착하는 바람에 깨서 역효과가 났다. 그리고 자고 일어나보니 다리가 마비된 듯한, 다리가 안 움직여지는 상황이 있었는데 이런 거 처음이었다.

수서역에서 택시를 타고 넥슨 사옥까지 갔다. 사옥 밖에서 이미 도착했을 cgiosy 같은 사람이랑 얘기라도 나누려 했는데 아주 자연스럽게 안으로 안내하더니 안에서는 코로나 때문에 제자리에만 앉아있게 해서 결국 ps러들이랑 한 마디도 못 나눴다...ㅠ

좌석표를 보니까 앞자리에는 songc가 있었다. 옆자리의 뒤에는 onjo고... 나중에 보니까 앞앞옆에는 브루도 있던데 진짜 가슴이 웅장해졌다.

키보드랑 마우스는 들고 가는 게 좋을 거 같다고 해서 들고 갔는데 내가 들고 간 구데기 키보드보다 그냥 거기 노트북에 달린 키보드가 더 좋아서 그냥 그걸로 했다.

그리고 한 시간 반동안 기다려야 했는데 진짜 너무 힘들어서 결국 뒤에 20분 정도는 그냥 잤다. 그리고 실행이 잘 되는지 테스트를 해볼 때 연습문제가 없어서 내가 알아서 자체적으로 컨벡스헐 한 번 짜보고 되는지 확인했다.

그리고 대회가 시작됐다. 퍼솔상을 노리기 위해서 빠르게 1번을 풀려고 했는데 생각보다 그렇게 빠르게는 풀이가 안 나왔다. 1~2분 걸렸나? 결국 10분 때에 풀어냈고 제출번호가 12번이라는 걸 확인하고 퍼솔상은 맘접었다.

2번은 대충 이분탐색하면 될 거 같았고 성질들을 좀 관찰하다보니 곧 풀이가 나왔고 그냥 그걸 짰다. 25분에 AC.

그리고 3번을 봤는데 이제부턴 어렵다... 일단 40점 풀이를 구상을 했는데 이게 구현이 구데기다... 내가 진짜 구데기 구현 꽤 해본 입장에서 가능한 구데기가 있고 불가능한 구데기가 있는데 이건 불가능한 구데기다... psum을 선 포함 미포함 두 개를 넣고 그걸 여러 개 만들고 어케 잘 스위핑하면서... 좀 답이 없었다. 그래서 그냥 섭태3 풀이를 떠올리거나 100점 풀이로 가려고 했는데 당연하게도 안 떠올랐다. 결국 저건 진짜 상황이 심각해지면 짜기로 하고 4번으로 런.

4번은 기하였다. 이분탐색은 기본으로 하고 항상 직선이 원 두 개에 접하도록 고정할 수 있고 그러면 가능한 경우의 수가 상수 개밖에 없으니까 섭태1이 풀릴 거 같았고 이걸 두 번 하면 섭태2도 풀릴 거 같았는데 문제는 내가 공통접선을 어케 긋는지 모른다... 아크삼각함수 같은 거까지 쓰면 어케 될 거 같긴 했는데 오차제한이 10^-9이라서 굳이 시도해보고 싶진 않았다. 그래서 이번에는 5번으로 런.

5번에서는 예제에서 3점을 긁었다. 그리고 다른 데에 제출하려니까 괜찮은 휴리스틱이 안 떠올라서 결국 3점만 긁고 튀었다. 두 시간 지난 시점에서 아직 203점. 이미 상황은 심각해졌고 나는 구데기 3번 40점 구현을 짜기 시작했다. 사실 그거 짤 때 대회 끝날 때까지 짤 수 있을지도 의문이었다.

그런데 짜면서 생각해보니까, 직사각형을 고정할 때 쓰는 격자를 그 무슨 괴물한테도 그으면 구현이 훨씬 깔끔해질 거 같았다! 물론 시간은 약간 더 걸리겠지만 일단 구현 시간은 획기적으로 줄어들 것으로 보였다. 그래서 그 방식으로 틀었고, 구현 좀 하고 디버깅 좀 해서 40점 get.

이제 243점이 되었고 할 수 있는 짓은 3번 섭태3 풀기, 4번 공통접선 잘 그어서 37점 긁기, 5번 휴리스틱으로 싹 긁어내기였는데 첫번째와 두번째는 할 수도 있고 못할 수도 있는 거였지만 5번은 적어도 몇 점은 받을 수 있는 것이었기 때문에 5번으로 간 다음 3 4번을 처리한다는 방법을 썼다.

5번에서 처음 구상한 휴리스틱은 (얻는 점수)/(그걸로 가려지는 점 개수)가 가장 큰 룩이나 퀸부터 배치하는 것. 열심히 짜고 또 열심히 디버깅하고 또 열심히 제출했더니 30점은 받을 수 있었다. 그리고 이제 3번이나 4번으로 가려니 남은 시간이 30분밖에 없었다. 결국 내게 남은 길은 5번 휴리스틱을 더 강화하는 것뿐이라고 판단, 한 번 (얻는 점수) 쪽을 변형해봤다. 원래 룩의 점수 5와 퀸의 점수 9를 그대로 가중치로 썼었는데 퀸의 점수를 25까지 올리니 점수가 좀 올랐다... 근데 출력을 보니까 Q밖에 없었고 그냥 퀸만 쓰는 게 룩을 섞는 것보다 훨씬 유용하다는 걸 이제야 안 것이다. 결국 그걸로 바꿔서 다시 열심히 제출했고 데이터가 15개나 있어서 대회 끝나기 1~2분 전쯤까지 제출했다... 이거 하면서 도중에 메모장에 모두 선택 기능이 있다는 걸 깨달았다. 대회 끝날 때쯤에는 큐가 밀려서 마지막에 제출한 것들이 점수가 안 나와서 291.6점이었는데, 이제 대회가 마무리가 되고 다시 노트북을 슬쩍 열어보니 294.2점까지 점수가 올라있었다.

열심히 딴 점수지만 딱히 잘 친 점수는 아니었다. 작년에는 300점은 개나소나 따는 점수였고 다들 3번 61점에 5번 50점은 기본으로 깔고 갈 거 같았다. 그리고 이제 카톡방에서 분위기를 보는데... 뭔가 이상했다. 다들 나보다 점수가 낮았다. 일단 다들 5번을 전혀 안 긁은 거 같았다. 그래서 수상각? 수상각? 하고 계속 있었는데 진짜 9등으로 겨우 수상권에 들었다... 기분이 너무 좋다. 첫 오프라인 대회를 그래도 좋은 결과로 마쳐서 다행이다.