NYPC 2018 넋두리

상 탄 주변 블로거 1

상 탄 주변 블로거 2

상 탄 주변 블로거 3

이 셋 중에 하나는 후기를 올릴 것 같다. 문제 풀이는 저 갓갓들이 올리거나, 아니면 공홈에 빠른 시간 내로 업로드될 것 같으니 대회 문제 풀이가 궁금하다면 저 링크들로. 이 글은 탐레프가 어떻게 고등학교 대회 커리어 마지막 대회를 말아먹었는지에 관한 tmi 꾸러미에 더 가깝다. 대회 문제보다는 대회장 모습, 멘탈의 변화 등을 중심으로 기록한 일종의 일기?

---

D - 1.

예선에 민컷도 나오고, Plane sweeping도 나오고, 작년엔 HLD / 센트로이드도 나왔으니 이번엔 분명 어디서 굴러먹던 근본 없는 고인물 문제가 나올 거라고 예상했다. 그래서 제대로 구현한 적이 없었던 센트로이드, Hopcroft - Karp 이분매칭, Li - Chao 트리 같은 걸 엄청 열심히 연습해갔다.

망측한 자료구조 문제에 비비려는 용도로 OSRank 코드도 외워갔다. 나름 철저히 준비했다고 자부하며 잠이 든 나는 대회장에서 어떤 일이 일어날지 상상도 하지 못했다...

여담이지만 연습에 썼던 문제들 중에 재밌는 건 풀이를 쓰려고 한다.

09:00 ~ 10:30

들어가서는 열심히 친목질을 했다. 나같은 아싸도 열심히 받아주는 코더들의 온화함...

책상에는 A4지 대신 무려 옥스포드 노트랑 NYPC 펜이 있었다. 넥슨의 자본력을 다시 한 번 실감하게 된 시점. 다만 펜은 되게 두껍고 잡기 어려워서 대회 내내 불편했다.

 

대회장 뒤쪽에는 자유롭게 먹을 수 있는 다과가 준비되어 있었는데 되게 비싸 보였다. 속물근성을 발휘해서 열심히 치즈 타르트랑 착즙주스를 축냈다. 

얼마 뒤 테스팅을 시작했다. 컴퓨터 환경은 Win10. 우분투가 아니어서 불편한 사람도 있었다고 하는데 나는 좋았다. 정신나간 가상머신의 피해를 너무 많이 입기도 했고, Linux GUI가 불편하기도 하고...

초반에 디렉토리를 만들다가 코드블럭이 두어 번 튕겼다. 하지만 이내 정상화되었고, 부팅 이후 초기에 하드 인덱싱 작업이 오래 걸리기 때문이라고 주최측에서 이야기해서 대수롭지 않게 넘겼다. Output - only를 대비해서 텍스트 파일도 정상적으로 만들었다.

풍선 종류가 10개라서 문제가 10개라는 베이퍼웨어가 있었는데, (당연히) 1214와 1519를 구분하기 위한 것이었다. 물론 나는 이걸 몰라서 멍청하게 코드블럭 프로젝트를 10개나 만들었다.

별 문제가 없다고 판단했고, 점검이 끝났다는 의미로 자리 앞의 네임태그를 뒤집었다. 남은 시간에는 대회 동안 사용할 템플릿을 짰고, 정말 심심해서 Hopcroft - Karp 구조체를 짜고 있었다 ㅋㅋㅋ 물론 저 코드가 쓰이는 일은 없었다.

여담이지만 외워갔던 OSRank는 쓸 수 없었다. GCC 버전이 다른 것도 아닐 텐데 헤더가 하나 없다고 나오더라 ㅁㄴㅇㄹ

대회 시작 후 30분

징 타종과 함께 대회가 시작했다. 소규모 대회였기 때문에 코포처럼 서버가 느려진다거나 하는 일은 대회 도중에 없었다. 

A번 문제는 보자마자 2개를 고정하고 나머지를 찾으면 되겠구나! 라고 생각해서 unordered_map을 써서 뚝딱 코딩했는데 44점이 나왔다. "N이 5000인데 unordered_map을 터뜨린다고???"라는 생각 때문에 잠시 패닉. 정답자가 꽤 많이 나오길래 외면하고 있던 \(O(N^2 \lg N)\) 풀이를 짜서 냈고 AC를 받았다 (10분). 요즘 5000은 제곱로그지!

B는 일단 입력이 실수였다;; 갑자기 싸해지는 분위기를 억누르고 열심히 식을 세웠다. 포락선 식이 나왔지만 계산하다가 틀릴 것이 뻔했기 때문에 그냥 삼분탐색으로 구현했다. 그 와중에 구현을 이상하게 해서 1틀 추가 후 AC (33분).

여담이지만 문제의 포락선 식은 너무 유명한 astroid다. 수학심층 안한 티를 내버렸다.

AB에서 자잘한 구현 실수를 많이 해서 경각심이 생긴 건지, 이후에는 괴랄한 구현 실수를 거의 하지 않거나 타이핑 직후 잡아냈다. 물론 코포였다면 얄짤없이 떡락했겠지.

갑분싸

200점을 확보했지만 구현 dirt + 시간 까먹기가 심해서 계속 긴장해야 했다.

C는 바로 정해가 떠오르지 않는 output only 문제였다. 작년 포인트 경쟁 문제를 이 친구가 대체하겠거니 하고 우선순위를 넘겼다.

D는 사랑과 관심이 필요한 그래프 문제같았다.

E는 시발이었다.

섭태 1이 Point In Polygon이었다. 섭태 2, 3은 듀얼 그래프 위에서 BFS였다. 세상에나. 나오라는 LiChao는 안 나오고 기하라니. 뭔가 머리를 쓰는 것도 아니고 이런 쌩기하라니!

결국 (C에서 일정 점수 확보) -> (D 고민) -> (C or E1)으로 방향을 잡았다.

갑자기 난독증이 와서 디스크립션 이해에만 한참이 걸렸다. 문제를 이해하기 위해 테스트 1을 풀다가 두어 번 틀렸다.

어느 정도 감을 잡고 텍스트 파일을 다 다운받았다. 야매 알고리즘을 짜서 냈는데 칼WA가 나오는 게 아닌가! 디버깅을 위해서 output이 주어지면 input을 복원해내는 일종의 DM을 짜기로 하고, output 파일을 만들었다.

그런데 그 순간 코드블럭이 멈추고, 크롬이 다운되고, Win10 전체가 먹통이 되었다.

선발고사 / KOI / APIO에서 머신에게 열심히 엿을 먹었는데, 기어코 그랜드슬램을 달성하고야 말았다.

나름 노련한 대처랍시고 손을 들고 D 풀이를 맨땅에 헤딩격으로 생각하기 시작했는데, 섭태 정보도 몰랐고 예시도 없는 상태에서 무식하게 D에 박치기한 건 좋은 선택이 아니었던 것 같다. 차라리 C를 조금 고민했으면 모를까...

하필 머신 이슈가 여럿 터지면서 체감상 20분 가까운 시간이 소모되었고, 늘 그랬듯이 스탭님께 보여주기 직전에 이 머신병은 완치되었다. 이쯤 되면 종교를 하나쯤 가져야 할 것 같다. 신이 날 미워하는 게 틀림없어.

심지어 스태프님이 떠나자마자 머신병이 재발했고, 이번엔 아예 교체를 요청했다. 다행히 교체 요청 이후에는 늘 그랬듯이 머신이 잘 돌아가서 C 풀이를 짰는데, 문제를 잘못 이해하는 바람에 계속 0점이 나왔다. 이때는 어차피 교체될 머신~ 이라는 생각에 고치려는 생각을 제대로 하지 않았던 것 같다. 생각해보면 이것도 전부 버려지는 시간이었다.

곧 새 머신이 왔고, 어차피 로컬에 틀린 코드밖에 남지 않았던 나는 이전 노트북의 코드를 옮기라는 권유를 거절했다. 이것도 일종의 만용이었고, 결과적으로 꽤 큰 실수였다. 적어도 템플릿은 열심히 복사했어야 했다.

어쨌든 머신이 교체된 시점에서 내 점수는 210점, 대회 1시간 반 가량이 지나 있었다.

그리고 갑자기 속이 메슥거리기 시작했다. 이 때 나는 이미 최고로 긴장하고 있었던 것 같다.

대회 중반

화장실을 다녀오고 C 풀이가 회생불가능하다는 걸 깨달았고, (D 고민하기) vs (E PIP 구현하기)로 생각이 넘어갔다. 맨 처음에는 E에 구미가 당겼지만... 최대 점수가 27점인데 비해 위험성이 너무 컸고, 또 내가 "어렴풋이 기억하는 웰노운"에 약하다는 사실을 알고 있었기에 오래 붙잡지는 않았다. 2시간 20분이 지난 시점에서 D로 넘어왔다.

또 맨땅에 헤딩하다가 (나쁜 습관 1) 100점 풀이가 떠오르지 않고 + 섭태 12가 쉬워 보이고 + 섭태3도 열심히 하면 될 것 같아서 당장 섭태 1부터 긁으려고 들었다 (나쁜 습관 2). 섭태를 '부분 점수'로만 보는 건 굉장히 좋지 않은 습관인 것 같다. 특히 섭태3은 100점 풀이에 다가가는 열쇠라고 생각하기 때문에...

2시간 40분쯤 섭태 1을 맞고 나서야 NYPC는 마지막 제출이 점수가 된다는 치명적인 사실을 깨달았다. 즉, 나는 한 소스 안에 섭태 123의 풀이를 전부 담아야 했던 것. 열심히 섭태를 digging할 수 있었던 APIO와는 정반대였다.

섭태2의 DP 풀이가 잘 떠오르지 않아 섭태 3을 먼저 생각했는데, 섭태 3을 생각하다가 100점 풀이가 보였다! 이걸 내가 풀어내고 마지막 1시간에 3번에 투자하거나 E1을 잡아내면 수상권이라는 직감이 들었다.

같은 세로선 위에 있는 점들을 한 노드로 보고, 두 노드의 LCA까지 열심히 쿼리를 옮기면 오프라인으로 \(O(Q + NM)\) 정도에 풀 수 있을 것 같았다.

초기에 트리만 잘 구성하면 구현이 어려운 문제도 아니었고, 당장 코드를 밀고 새로 코드를 짜기 시작했다. 110줄 정도 코드를 짜고 이제 쿼리를 오프라인 형태로 트리에 넣으려는데...

분석해보니 복잡도는 \(O(QNM)\)이었다. 19점짜리 풀이와 가치가 같았다.

여기서 형식적으로나마 붙잡고 있던 이성의 끈을 놓아버렸다. !!!!커리어 마지막 대회!!!!에서조차 나를 이렇게 구석으로 몰아넣고 팝콘을 튀기고 있을 신을 잠시 동안 상상했다.

Sparse Table을 활용해서 복잡도를 줄여보려고 했지만 이미 나부터가 내 풀이를 강하게 불신하고 있었다. 몇 가지 생각을 더 해봤지만 다 한끗이 모자란 풀이였고, 나는 손을 더 뻗을 의지가 없었다. Sparse Table을 조금만 더 생각하면 100점 풀이를 생각할 수 있었다는 imeimi의 증언이 있었다 ㅎㅎ

주섬주섬

풀이에 오류를 찾아냈을 때 남은 시간은 1시간 30분 정도였고, 이 시간에 새로 D 정해를 만들어낸다 해도 코딩할 수 없다는 생각이 들었다. 눈물을 머금고 상장과 함께 D를 버렸다. 남은 일은 내가 할 수 있는 걸 다 하고 대회를 잘 마무리짓는 것이었다. 얻을 수 있는 점수가 가장 높은 순서대로 (D 40점) -> (C > 50점)을 노렸다.

D 40점 DP 코딩은 생각보다 까다로웠다. 특히 입력과 dp table의 인덱스를 다르게 짜는 바람에 잘못된 메모리 참조가 난무했다. 하지만 상과 작별했다고 생각하니 마음은 평온해졌고, 좋은 디버깅 예제를 찾아 30분만에 원샷 AC를 띄웠다.

1시간 (+머신병 추가시간 10분) 을 남기고 C로 들어왔다. 내가 코딩할 수 있는 가장 naive한 풀이를 생각했고, 대충 색이 2개인 5개 데이터에서 3~40점, 이 풀이를 3색으로 확장시킨 5개에서 2~30점 정도 점수가 나올 것 같았다.

풀이는 naive했지만 코딩은 전혀 쉽지 않았다. 특히 템플릿을 쓰지 않다 보니 코드는 내 약어들 때문에 생긴 에러대잔치였고, 위아래를 왔다갔다, 여기서 복사해서 저기다 붙이고 하면서 열심히 스파게티를 뽑았다. 마지막에는 코드가 300줄 가까이 갔던 것 같다.

다행히 rng신의 가호와 NYPC의 generous한 스코어링으로 앞 5개에서 48점이 넘는 점수를 뽑았다! 스파게티를 두 배로 늘려서 3색에서 돌아가는 코드를 짰더니 점수가 91점 정도 나왔고, 시간은 추가시간을 포함해 15분 정도가 남아 있었다.

추가시간에 또 하나의 최적화 코드를 완성해서 93.8점을 받았고, 마지막 5분은 손으로 최적화를 해서 94.35점까지 올렸다.

최종 스코어는 100 / 100 / 94.35 / 40 / 0으로 334.35점. 딱 중위권 정도의 점수인 것 같다. 탐중딱~

의외로 C번을 손으로 99.X까지 올린 사람이 많아서 당황했다.

총평 + PS에 만약은 없지만...

기본적으로 고난과 역경이 따라오는 온사이트 대회지만, 커리어 마지막 대회 아니랄까봐 신이 모든 종류의 고난을 패키지로 집어넣어줬다.

이러니저러니 해도 결국 패인은 기본적인 실력 부족 + 멘탈 관리 부족이다. 나름 보강된 계획을 가지고 갔지만 여전히 멘탈이 중요한 순간에서 무너졌다. 하지만 상황이 워낙 혹독했던 만큼, 다음 기회를 위한 멘탈 단련에는 큰 도움이 된 것 같다.

한 가지 늘어놓고 싶었던 what if?를 꼽자면,

- C 91점을 받고 남은 20분은 D를 66까지 늘리기에는 부족한 시간이다.

- D를 고민할 시간이 10~15분 정도 있었다면 노려볼 가능성이 있었다.

- 그리고 이 시간은 머신이 고장나서 손가락 빨고 있었던 시간이랑 비슷하다.

...물론 말도 안되는 소리다. 이런 시간은 시간 분배를 안정적으로 하거나, 정 안되면 AB를 광속으로 풀어서 확보해야 한다. 그래도 걍 억울하다고...

P.S. 식장에서는 경황이 없어서 (그리고 아싸라서...) 말을 못 전했지만, 수상한 알큼과 왜시계에게 진심으로 축하의 말을 보낸다.