NYPC 2021 본선 후기

대회 시작 전

대회가 시작하기 전, 노트북을 점검하는 시간에 코드블럭을 키고 몇가지 코드를 짜서 돌려봤습니다. NYPC는 휴리스틱 문제가 자주 나오는 편이기 때문에, 난수를 생성하는 mt19937을 짜서 돌려봤는데 무슨 이유에선지 컴파일 에러가 났습니다. 그래서 그냥 rand()를 쓰기로 하고 일단 넘어갔습니다.

다른 코드도 몇 개 짜봤는데 range-based for가 작동하지 않고 컴파일 에러가 났습니다. 알고보니 코드블럭 기본 세팅이 c++98로 되어있었고, 스태프의 도움을 받아 c++11로 컴파일을 할 수 있게 되었습니다. 버전을 올리니 mt19937도 정상적으로 돌아갔고, 별 문제가 없었습니다.

 

0:00~0:30

NYPC 본선은 일반적으로 난이도 순으로 문제가 나오기 때문에, 쉬운 1번과 2번은 반드시 풀어야 한다는 마인드로 1번을 읽기 시작했습니다. 처음에 문제를 잘못 읽고 틀린 코드를 짰지만 금방 다시 짜서 100점을 받았고, 2번으로 넘어갔습니다.

2번을 보고 수열을 앞부터 쭉 보면서 prefix sum이 0 미만이 되면 prefix sum을 제일 크게 증가시키는 수를 0으로 바꾸는 그리디를 생각을 했고, 증명을 하려고 했는데 엄밀하게 증명하는 것이 잘 안 되었습니다. 근데 직관적으로 맞을 것 같았기 때문에 일단 짜서 제출을 했고 바로 100점을 받았습니다.

 

0:30~2:00

3번부턴 난이도가 높을 것이라고 예상했기 때문에 쉬운 섭태를 최대한 빠르게 긁기로 했습니다. 3번의 2M<=K 섭태는 쉽게 풀었고, 4번의 N<=5000섭태는 제곱 풀이를 알지만 귀찮아서 dnc opt를 이용한 제곱로그를 짜서 긁었습니다.

5번의 서브태스크 2, 3은 간단한 구성적 문제였는데, 서브태스크 3의 실례 구하는 것이 자꾸 틀려서 점수를 못 받고 있었습니다. 30분 정도 디버깅을 한 것 같은데 고치지 못 했고, 코드를 다시 짜봐도 점수가 안 긁혀서 일단 넘어가기로 했습니다. 이때 점수는 276점이였습니다.

 

2:00~4:00

대충 쉬운 서브태스크들은 다 긁은 것 같았고 다른 서브태스크들을 긁으려고 했는데 꽤 오래 고민해도 풀리지 않는 서브태스크들이 대부분이였습니다. 이대로 가다간 망할 것 같아서 그나마 풀이가 보일 것 같은 4번 100점을 40분 정도 시도했고, 슬로프 트릭으로 뇌절하다가 결국 풀이를 찾지 못했습니다. (사실 이때 4번을 잡은게 미친짓이였던 것 같습니다 ㅋㅋ;)

아까 못 긁었던 5번의 섭태 3 실례를 긁기 위해 다시 5번의 디버깅을 시작했고, 대충 의심되는 부분들을 다 처리해줬더니 점수가 긁혔습니다.

그리고 30분쯤 남았을 때 3번의 M, K, A, B<=6 섭태를 1가지 가정을 한 나이브 bfs로 뚫어보려고 했고, WA를 계속 받다가 결국 맞지 못했습니다. 배열의 길이가 2K를 넘어가지 않도록 하는 실례가 항상 존재한다는 가정을 하고 짰는데 아마 틀린 가정인 것 같습니다.

 

대회 종료 후

초반 2시간에 276점을 긁고 후반 2시간 동안 6점 밖에 못 긁어서 그냥 망했다고 생각하고 시상식을 기다리고 있었습니다. 제발 10등안에만 들었으면 좋겠다고 생각을 하면서 기다렸는데, 특별상에 제 이름이 없어서 동상일 것이라고 예상하고 있었습니다. 하지만 동상에도 제 이름이 없었고, 은상에도 제 이름이 없어서 결국 상을 못 받는 줄 알았는데 놀랍게도 금상을 받게 되었습니다.

알고보니 이번 대회가 엄청 어려운 문제들로 구성되어있었고(3 4 5번 전부 루비), 다들 풀태를 노리다가 섭태를 못 긁은 것 같습니다. 대회 끝나고 은상과 대상을 받은 애들이랑 점수 공유를 해봤는데 은상은 280.4점, 대상은 저와 동점인 282점(...)이였습니다.

동상을 노리고 봤는데 금상을 받아서 기분이 좋았고, 시간차로 대상을 못 받아서 조금 아쉽기도 했습니다. 내년에는 대상 받으면 좋겠네요 ㅋㅋ