SCPC 2022 본선 후기

Chap 0. Prologue

2차 예선에서 탈락의 고배를 마신 작년과 달리 올해는 본선에 진출할 수 있었다. 그렇기 때문에 더욱더 상이 간절해졌다. 5등상이기만 해도 부수적으로 얻을 수 있는 것들이 많았기 때문에 SCPC 수상이 정말 간절했다. 올해의 CP 3대 목표는 scpc 수상, icpc 월파 진출, 코포 레드 달성이다.

예선은 굉장히 나답게 통과했다. 4번은 힘을 들이지 않고 풀이가 생각났는데 3번은 죽어도 풀이가 안떠올랐다... 불안해서 열심히 긁었고, 안정적으로 본선에 진출할 수 있었다.

Chap 1. 본선 준비

icpc ucpc와 scpc의 차이는 무엇일까. 첫째로 개인대회라는 것이고 둘째로 팀 노트가 없다는 것이다. 그렇다면 코포와 scpc의 차이는? 검색이 안된다는 것이다. 그렇다. 모든 코드를 다 머릿속에만 의존해서 짤 줄 알아야 한다.

특히 scpc는 문자열을 굉장히 좋아한다는 소문이 있다. 하지만 나는 문자열을 등지고 살았었기에 이번 기회에 겸사겸사라는 생각으로 해싱, 마나커, kmp, 트라이를 공부했고, 추가로 이분 매칭, 디닉, hld, centroid 등을 공부하고 코드를 암기했다.

남은 건 아호코라식과 SA였고 작년 문제를 생각했을 때 꼭 ㅁ외워가야 하는 것이라고 생각했지만, 대회 전날 커피를 마시고 집중도 못해서 공부도 못하고 새벽 4시 30분에 자버렸다...

Chap 2. 무난한 출발...?

 1번 문제를 읽고 천천히 생각을 했다. 딱 보니까 최적의 구간은 양 끝 점을 포함하는 구간이거나, 양 끝 점에 극한으로 다가가서 포함을 하지 않는 구간 둘 중 하나였다. 따라서 n^2개의 구간 중 가장 좋은 구간을 찾으면 된다.
 이런 문제 특, 답이 될 만한 $O(N)$ 개의 구간만 보면 된다. 각 점마다 1/n의 가중치를 가지고 있다고 가면, 이동하는 만큼 감소가 되고 하나를 먹을 때마다 1/n 이 증가한다. 그래서 모든 점을 1/n - 이전 점까지의 거리라는 값으로 바꾸면 배열에서 가장 큰 부분합을 구하는 문제와 비슷하게 되고, 이는 쉽게 해결할 수 있다.
근데 WA를 받았다. 큰 충격과 불안에 휩싸였지만, 풀이는 틀리지 않았을 것이라는 믿음을 가지고 코드를 보니 cout precision을 안 한 것을 확인할 수 있었다. 근데 내가 까먹었는지 precision이 잘 안 되었다. 그래서 printf %. 12f로 제출했더니 맞았다.

+34 1번 100점

 이후 2번을 봤는데 보자마자 $O(N^3)$ DP 가 떠올랐고, 30초 있다가 DNC OPT가 떠올랐다. 하지만 섣부르지 않기 위해서 열심히 종이를 잡았고, DNC OPT를 적용할 수 있다는 사실을 확인할 수 있었다. 따라서 바로 코딩을 시작했고, 결과는 WA... 혹시나 해서 OPT 부분을 없애고 $O(N^3)$ DP를 짜니까 바로 47점을 얻을 수 있었다.

 이때가 시작 후 50분 시점이었기 때문에 아직 2번을 보는 것이 맞다고 판단. 2차원에서 가로 세로 OPT가 아닌 대각선 한 줄 별로 DNC를 실시하였다. 결과는 똑같이 WA... 나는 큰 충격에 휩싸였고, 이후 패닉 제출을 여러 번 했지만, 결과는 똑같았다.
시점은 90분이 지났고, 점수는 147점. 풀이는 틀렸을 리가 없었지만, 2번 문제의 10번의 제출로 페널티는 꽤나 쌓인 상태였다. 무난하다고 볼 수도 있지만, 뭔가 께름칙한 시작이었다.

+53 2번 47점

Chap 3. 훌륭한 중반

이후 3번으로 보고 좀 생각을 해보다가 던졌다. 그리고 4번을 봤다... 어? 보자마자 드는 생각은 DP나 파라매트릭. 그리고 문제를 읽으면서 당연하게 같은 숫자는 붙어있는 것이 이득이라고 생각하였다. 또한 정답에 카운트되는 메인, 정답에 카운트되지 않는 깔개로 잘 분리를 하면 전체 답은 전체 개수 - 깔개 수 인데, i번째 수까지 k개의 깔개가 생겼을 때로 잘 DP를 하면 되지 않을까라는 생각을 했다.

(메인 2222222) (깔개 1) (메인 333333) (깔개 3) (메인 4)

 이후 손으로 좀 굴려보니까 많은 숫자 뭉치는 위쪽에 있는 게 이득이고, 작은 수부터 보면 굉장히 편하다는 사실을 확인했다. 다음 수가 들어갈 때 더 큰 수가 들어오기 때문에, 깔개가 부족하면 그냥 메인으로 있던 수 중에 하나를 깔개로 끌고 와서 내리면 그만이었다.
 여기서 Touch the Sky라는 문제가 생각났고, PQ를 관리하면서 그리디를 하는 방식이 떠올랐다. 하나의 메인 뭉치를 다 깔개로 내리면 뭉치가 하나 줄어서 깔개를 하나 덜 써도 되기 때문에 무조건 이득이라고 생각했다.
 위의 상황을 예시로 들자면 다음에 5 2개가 들어오는데, 메인>깔개 이므로, 깔개로 하나를 내려야 한다. 이때 항상 메인 중 하나를 내릴 수 있으며 4를 내리는 게 이후 상황에서 무조건 이득이다.

1. (메인 2222222) (깔개 1) (메인 33333) (깔개 3) (메인 4) (깔개 3) (메인 55)
2. (메인 2222222) (깔개 1) (메인 333333) (깔개 3) (메인 55) (깔개 4)
2번의 경우에만 다음에 오늘 k개를 바로 정답에 카운트되는 메인으로 보낼 수 있다.

 그럼 pq로 뭉치 크기가 작은 순서로 관리하면서 메인 뭉치 개수와 깔개 개수를 비교하면서 스위핑 하면 된다.
그리고 이 모든 과정을 7분 만에 마무리하였다. 그래서 코딩을 다 했더니 경과 시간은 107분에 4번 문제를 푼 사람은 x. 내가 생각하기에 4번은 잡으면 풀 수 있는 사람이 너무 많다고 생각하여 4번을 안 내고 3번을 잡는 선택지를 했다.
 3번에서 (log 범위)^2 이 필요한 38점짜리 풀이를 거의 만들어 가고 있는데 4번 문제의 정답자가 나와있었다. 그래서 얼른 제출을 했더니... WA? 그래서 내 풀이를 검토했다. 사실 엄청 어려운 문제인데 내가 사풀을 낸 것이 아닐까 무척 두려웠다. 하지만 풀이를 검토했더니 틀린 부분이 없어 코드를 검토했고, 1 이상이면 pq에 넣는 것을 1초과일 때 넣는 것으로 구현했다는 것을 발견할 수 있었다. 그리고... 결과는 AC!

+142 4번 100점

완벽한 순간이었고, 수상은 확정 지었다고 생각했다. 이제 2번 100점과 3번 38점을 받으면 꽤나 높은 상을 탈 수 있다는 기대감이 생겼다.

Chap 4. 다소 아쉬운 마무리

3 번은 38점 풀이는 그렇게 어렵지는 않았다. 근데 구현이 생각보다 많이 까다로웠다. 156분에 첫 제출을 해서 182분 까지 11번의 WA를 받았다. 하지만 나는 남들과 다른 거의 유일한 점수인 상황이었기 때문에 (이때도 4번 솔브 수 2~3) 페널티 경쟁은 할 일이 없다고 생각했다. 그렇게 왜 틀렸는지 모든 수를 찍어봤는데 100까지 모두 잘 나왔다. 그래서 다시 문제를 읽어봤더니 0에서 이상한 결과를 출력하고 있다는 것을 깨달았다. 이후 바로 예외처리를 해서 38점을 받을 수 있었다.

 마지막으로 2번에 달려들었다. 1시간 동안 다양한 dnc OPT와 추한 뚫기 코드를 이용해서 20번을 넘게 제출했지만 얻게 된 것은 페널티뿐이었다. 끝나고 들어 보니 2번은 dnc opt가 안 되는 문제였다... 나는 무엇을 증명하였는가.

+184 3번 38점
총결과 285점. - 100 47 38 100 0

Chap 5. After story.

 끝나고 내 위에 있는 사람들을 열심히 찾아다녔다. 처음에는 4등~5등상 을 생각했으나, 생각보다 내 위에 사람이 없었고, 혹시 3등상? 이라는 마음이 생겼다. 그렇게 수소문한 결과 내 위에 정확히 8명을 찾을 수 있었다... 특히 그 중 내가 아는 최저점은 100 100 88 0 0 의 288점이었다. 진짜로 3점차이로 4등상이면 너무 억울할 것 같아서 288 이 차라리 훨씬 많거나, 내가 들은 사람중 더 이상 상을 탈 수 없는 사람이 있어 정확히 8등으로 3등상 막차를 타기를 간절히 바랐다.

 17일에 결과가 공지된다는 문자가 오기 전까지 매일 간절한 마음으로 SCPC 홈페이지에 접속했다. 시작 전에는 5등상만 받아도 된다더니 행동은 달랐다.(ㅎㅎ) 사실 머릿속으로는 이미 4등상일걸 알면서도 혹시나 하는 마음에 계속 기대를 하지 않을 수 없었다. 사실 이미 모든 증언에 의해 4등상 이하가 확실시되어있는 상황이긴 했는데도 좀 많이 기대한 것 같기도 하다.

Chap 6. 시상식과 상자 안의 고양이

드디어 시상식 날 아침이 되었고, ifland에 들어가서 자리에 앉은 후 기다렸다. 5등상을 보고서 가나다 순으로 나온다는 것을 확인했고, 4등상의 두 번째 페이지를 봤는데...

나의 이름을 확인할 수 있었다. 막상 이렇게 되니까 아쉬웠지만, 한편으로는 후련했다. 결국 해냈고, 수상이라는 목표는 이루어 냈기 때문에! 사실 이미 마음속으로도 어느 정도 예상을 했는지 막상 마주해도 막 큰 타격보다는 후련함과 행복감이 더 컸던 것 같다.

 끝나고 나서... 나에게 택배로 고양이 상자가 하나 다가왔다. 그 상자 안의 고양이는 살아있으면서 죽어있었다. 그렇다면 나는 고양이가 살아있기도 하니까 잊고 행복하게 살아갈 수도 있었다. 하지만 그럴 수 없었다. 언젠가는 상자를 열게 될 것이었고, 사실 궁금함을 참지 못하는 나에게 그 언젠가는 바로 당장이었으니까.
바로 링크를 타고 들어가 점수 순으로 개제 되어있는 홈페이지에 표시되어있는 결과를 확인했다. 결과는...

캬~~ 당당한 4등상 첫자리!!!! 와~~~ 고양이는 깔끔하게 죽어있었고, 상자 안에 남아있던 독가스가 퍼져서인지 몰라도 나까지도 어질어질했다. 여기저기 하소연을 하면서 마음을 가라앉혔다. 장난 삼아 윗사람 탓도 해보고, 나보다 잘 본 사람을 가르쳐준 사람 탓도 해보고, 문제 배점 탓도 해보고 했지만, 다 농담이었다. 왜냐면 그냥 내가 좀 만 더 잘했으면 되는 거니까.
그렇게 매 대회에서 한 등수 올라가거나 떨어지면 상이 바뀌는 나의 줄타기는 변하지 않았음을 확인할 수 있었다.

Chap 7. Epilogue - Story of stonejjun03

 이번 대회는 본선도 예선도 누구보다 나 답게 해냈다. 예선 2차는 3번 대신 4번을 풀어냈고, 본선에서는 30명 넘게 푼 2번을 못 풀고 6명만이 푼 4번을 가볍게 풀어냈다.

 사실 최근 1년간 마음고생이 굉장히 심했다. 성과는 잘 안 나오고 있고, 그냥 내 실력에 내가 만족스럽지도 않았고, 사실 나 스스로 내가 정말 열심히 한다는 생각조차 들지 않았다. 코딩이 재미없었고, 하기 싫은 느낌이 강했다.
 그래서 마음을 더 독하게 먹었다. 잘하는 사람에게 찾아가 쓴소리를 듣고, 남들과 비교해서 3일 정도 자극받아 열심히 하고, 다른 사람 붙잡아서 관리해달라고 하면서 한 두 달 열심히 하고, 마치 카드 돌려막기를 하는 것처럼 어떻게든 외부에서 요인을 만들어서 나를 더 구석에 몰아넣었다. 나는 그래야 하기 싫은 걸 열심히 하는 사람이라서.

 사실 코딩이 막 그렇게 싫은 건 아니었다. 하지만, 내가 정말 부족한 능력을 기르기 위해서는, 내가 원하는 대회에서 안정적인 성과를 거두는 사람이 되기 위해서는 조금은 하기 싫은 공부를 해야 되는 상황이었다.

 근데 막상 하다 보니까 할만했다. 무엇보다 정말 좋은 성과를 내고 싶고 잘하는 사람이 되고 싶다는 간절함이 컸던 것 같다. 같이 버츄얼 돌고, 플레 몇십 문제 박아다가 조금씩 해결하고, 매일 코딩에 일정 시간을 쏟고, 나에 대해서 분석하고, 무슨 문제던지 끝까지 마무리 짓는 것들. 막상 습관처럼 되니까 해 볼만 했다.

 작년의 나와 비교하면 확실히 늘었다고 말할 수 있는 것 같다. 저점은 올랐고, 고점의 폭도 증가했다. 고점의 폭? 이라고 하면 약간 이상하지만 최근에 어떤 대회를 치더라도 나한테 정말 잘 맞는 (그래서 남들과 차별 점으로 이득을 가져올 수 있는) 문제가 하나씩은 매 대회에서 보였다.
 하지만 아직 그 한 문제를 쉽게 푸는 것을 온전히 이득으로 가져오지는 못하는 것 같다. 이번 2번 같은 문제를 안정적으로 풀 정도는 되어야 더 한 단계 나아갈 수 있을 것이다.

 이렇게 블로그에 이런 이야기를 푸는 것은 처음인 것 같다. 오랜 생각이어서 그런지 글이 술술 써졌다. 지금까지 도움을 주신 많은 분들께 감사하다는 말을 하고 싶다. 그리고 이 글을 보는 많은 (? 어쩌면 적은) 사람들에게 더 나아갈 것이라는 다짐을 하려고 한다.

지금까지 후기로 시작하여 저의 이야기로 끝난 글을 읽어주셔서 감사합니다.