NYPC 2023 본선 후기

예년 본선 후기가 별로 없길래 저라도 적어봅니다.

 

대회 전

https://heejayaa.tistory.com/165

올해는 제가 옥 선생님(utilforever)께 얻어먹었습니다 😋

등심? 스테이크, 리코타 치즈? 샐러드, 뇨끼를 먹었습니다. 뇨끼를 처음 먹어봤는데 쫄깃하고 맛있었습니다. 스테이크는 두툼하니 야무졌습니다. 잘 먹고 들어가서 끝까지 잘 버틸 수 있었던 것 같네요 :)

감사합니다!

 

한편, NYPC의 시간대를 부분집합으로 갖는 춘배컵이 BOJ에서 진행 중이었습니다. 저는 N. 고양이 리그 문제를 출제했습니다.

xiaowuc1님이 퍼솔하는 걸 확인할 수 있었으나 뭔가 스코어보드 구경이 이제는 그닥 재밌지는 않네요. 역시 문제를 만들어내는 순간이 제일 즐거운 것 같습니다.

 

넥슨에 도착한 뒤 드디어 옥 선생님과 사진을 남길 수 있었습니다 📸

동반인을 위한 카페가 있었는데, 출제진 몇 분을 뵐 수 있었습니다. 내년에 저도 출제하고 있으면 좋겠네요.

뭔가 내부에 체험 부스 같은 게 하나 있었는데 잘 모르겠고 슬슬 들어가야 해서 대회장 쪽으로 갔습니다.

 

대회 직전에 볼 checklist를 챙겨갔는데, 슬슬 시작이라 그냥 보지도 못하고 들어갔습니다.

 

제 번호는 77번이어서 운이 좋으려나 하는 생각을 갖고 들어갔지만, 그렇지 않다는 것을 곧 깨달았습니다. 이유는 후술 합니다.

아마도 일주일 전쯤 온 본선 확인 메일이 있었는데, 그냥 알려준 거 또 알려주는 건 줄 알고 대충 읽고 넘겼습니다만.. 이틀 전쯤에 확인 회신 메일을 보내달라는 요청이 와서 그제야 즉시 회신했습니다. 아마 그것 때문에 번호가 뒤쪽인 것 같네요.

 

77번 자리는 60명의 1519 학생들 중 제일 오른쪽이자 제일 뒤쪽 자리였고, 입구와 맞닿고 있어 사람들이 제일 많이 드나드는 자리였습니다...

또한 모든 학생들의 풍선을 볼 수 있는 자리이기도 했습니다...

 

세팅 시간

대회 전부터 세팅이 제일 걱정되어서 빨리 세팅하고 싶은 마음밖에 없었습니다.

그러나 제 노트북만 켜지지 않아서.. 내가 컴퓨터 켤 줄도 모르는 컴맹인가? 하는 생각이 들었습니다.

계속 안 켜지길래 운영진께 알렸고, 알고 보니 77번 자리만 코드가 안 꽂혀 있었고, 그나마 꽂을 자리도 없던 상황이었던 것 같습니다.

 

그래서 10분 정도 운영진들이 바삐 움직이며 제게 새 노트북을 가져다주셨습니다. 대회 경험이 조금 쌓여서 멘탈이 전보다는 나아졌지만.. 이런 돌발 상황에서도 정신을 유지할 멘탈은 아니어서 굉장히 패닉 상태로 세팅을 시작했습니다.

 

다행히 jhnah917님이 세팅을 도와주셔서 세팅을 끝낼 수 있었습니다. VSC로 g++, c++14?, file input/ouput/error 세팅을 했고 잘 작동하는 것을 확인했습니다. 아마도 저 때문에 세팅 시간이 연장된 것 같기도 한데, 정신이 없어서 확실한지는 잘 안 나네요.

아무튼 작동하는 걸 허둥지둥 확인하자마자 대회가 시작되었습니다.

 

대회 시간

1번을 읽기 시작했습니다. 굉장히 복잡한 지문이어서 이해하는데 20분가량 소요한 것 같습니다.

슬슬 해보려고 하는데 다른 참가자들에게 풍선이 하나씩 달리기 시작했습니다. 서둘러 구현을 하다가 다시 문제를 확인하니까 제가 접근한 방법이 틀렸다는 걸 깨달았습니다.

아무리 봐도 플래티넘 2 이상의 쿼리 문제였습니다. 그래서 이건 문제 이해에서 착오가 있었다는 확신을 갖고 다시 문제를 읽어보았습니다.

 

앗.. 제한 칸 마지막 줄에 "값이 0인 칸에 변화가 없다"는 말이 적혀 있었습니다. 이게 있다면 문제의 난이도는 실버 수준으로 떡락합니다. (분명히 지문을 명확하게 할 수 있었음에도 저렇게 둔 것은... 애초에 지문을 정확하게 읽으라는 교훈을 주기 위한 의도로 출제한 문제가 아니었나 싶습니다)

그래서 코드를 여차저차 수정해 보았습니다만, 자꾸 WA가 났습니다.

 

정말 멘탈이 갈려나갔고, "모든 난이도 값을 XOR 한 결과"가 방에 대해 distinct한지, 난이도에 대해 distinct한지 질문을 넣고 2번으로 넘어갔습니다.

 

대충 이 시점이 1시간이 지난 시점이었던 것 같습니다...

 

2번은 지문이 굉장히 깔끔했습니다. 일단 slope trick이 떠올라서 부들부들하다가 다른 참가자들이 거의 다 풍선을 두 개씩 달고 있는 걸 확인하고 다시 지문을 읽었습니다.

대충 그리디 같은데 잘못된 가정을 갖고 시작하면 사풀로 빠질 법한 문제라고 생각했습니다.

그런데 잘못된 가정을 갖고 풀이를 작성했습니다. 평소라면 안 했을 법한 짓인데 아무튼 그렇게 하고 있었습니다. 물론 WA를 받았지요.

 

슬슬 답변이 돌아오길래 대충 2번을 붙잡다가 다시 놓고 1시간 30분 차쯤에 1번을 돌아갔습니다.

예상한 대로 '문잘읽' 답변이 돌아왔고.. 슬슬 수상은 포기하고 0점을 면한다는 마인드로 마음을 내려놓으니 마음이 차분해졌습니다.

 

역시 질문 사항과는 무관하게 업데이트를 multiset이나 xor 값에 취하고는 있지만, 정작 배열에 새 값을 대입하지를 않고 있었다는 것을 알았습니다. ㅋㅋㅋㅋㅋ

그냥 말릴 대로 말렸다는 표현 밖에는 할 말이 없었습니다.

 

아무튼 고쳐서 100점을 보고 2번으로 넘어왔습니다.

 

그래도 0점을 면해서 다시 마음이 차분해졌고, 적당히 누적합을 적어 보니까 $A[1]$에 대한 연산을 정하면 나머지 연산은 자동 결정되니까... 늘 하던대로 $A[1]$ 변화량에 대해 답이 감소-증가 형태를 띰을 이용하여 기울기에 대한 이진 탐색을 진행하였습니다. 중앙값으로 풀어도 어떻게 된다고는 하는 것 같네요. 하지만 그것까지 고민하고 싶지는 않았습니다.

 

64bit 정수형에 들어오는지 잘 모르겠지만 일단 내봤고, 연산 횟수가 작을 때까지 점수가 긁히길래 __int128_t로 바꿔서 제출 후 100점을 받았습니다.

 

아마 이게 2시간 정도 지난, 2시간 정도 남은 시점이었을 것입니다.

 

그냥 수상 욕심이 싹 사라져서 일단 5번-4번-3번 순으로 긁을 것들 찾아보려고 30분씩 둘러봤습니다.

 

5번은 그냥 제한부터 논문 냄새가 나긴 했습니다. 그래도 쓸만한 게 있나 싶어 45도도 돌려보고, 어디까지 완전탐색 가능한지 견적도 체크해 봤습니다. 근데 딱히 괜찮은 게 없어서 4점만 대충 긁고 4번으로 이동했습니다.

 

그럼 이제 1시간 30분 정도 남은 시점이겠네요.

4번을 보는데, 그닥 어렵지 않은 자료구조 문제 같았습니다. set만 쓰거나 set이랑 세그트리를 잘 섞어 쓰거나 하면 될 것 같았습니다. 근데 구현을 빠르게 할 수 있을지 모르겠어서 한 20분 보고 3번부터 해치우고 오자라는 생각으로 3번으로 이동했습니다.

 

1시간 10분 시점부터 보게 되었습니다.

3번을 봤는데, 조금 손으로 해보니까 부분문자열 비교에 걸리는 시간 자체를 단축시킬 방법이 없기에 부분문자열 길이가 짧다는 것을 이용한 DP를 하면 되겠다는 생각이 들었습니다.

일단 1번 조건은 만족하는 마지막 순간에 +1을 해주면 되겠다는 생각으로 열심히 짰습니다만, 예제가 제대로 안 나왔습니다.

그래서 생각해 보니까 이 DP를 prefix랑 suffix에 각각 해주고, 합한 걸 전부 확인해 주면 충분하겠다는 생각이 들어, 짰던 DP를 복사해서 두 개의 함수로 나눴습니다.

 

여기까지 하고서 아마 30분이 남았던 것 같습니다.

근데... DP 테이블 다 찍어봐도 잘 나왔는데 자꾸 제출하니까 알 수 없는 RE가 떴습니다. 도통 이해할 수가 없었는데요..

마지막까지 디버깅을 해보았지만, 고쳐지지 않았고, 배열의 크기를 마구 늘리니까 한 5점 정도 긁히다 말았습니다.

 

UPD - leading zero를 고려하지 못한 풀이었네요..ㅠ 0이 있을 것이라고 전혀 생각을 못 했습니다..ㅠㅠ

 

마무리

이번 대회의 티어를 대충 매겨보자면 S1 - P5 - P2 - P2 - R? 정도가 될 것 같습니다. 수상 컷은 404점 시간 컷이라고 하네요. 원래는 4시간 5문제가 굉장히 타임어택이라고 생각했지만, 이 정도 난이도면 1, 2번을 주고 들어가는 데다 3, 4번이 어렵지 않아서 적당한 시간인 것 같네요.

 

UPD - 잘못 짠걸 생각하면 실제 3번 난이도는 $>$P2일 것 같네요.

 

다소 아쉽게 대회를 치르긴 했지만.. 그만큼 제가 고쳐야 할 명확한 부분이 드러난 것 같아서 뜻깊었습니다. 지문 이해(...)와 안정적이고 빠른 구현과 확실한 디버깅... 반드시 필요합니다. 풀이 도출은 꽤 빨라진 것 같고요. 다이아 발상 연습보다는 플래티넘 3~2 랜디나 cf div.1 같은 걸로 적당히 어려운 문제를 많이 푸는 게 답인 것 같습니다. 올림피아드류 말고 구현 빡셀 수 있는 리저널 같은 것도 가리지 말고요.

 

확실히 이벤트가 많은 본선에 참가하는 것은 그 자체만으로 굉장히 즐거운 경험인 것 같습니다. 다만 얼굴을 아는 사람이 별로 없어서 좀 아쉽긴 했는데요.. 앞으로도 이런 큰 대회의 본선에 자주 진출할 수 있었으면 좋겠습니다.