KAIST Run Spring 26' 후기

마지막에 글을 쓴 게 3월인데 그 이후 BOJ 서비스 종료라는 매우 큰 일이 일어났다. 이 일에 대해서 글을 작성하려고 했는데 뭔가 내가 말빨이 좋은 사람이다 그런 건 전혀 아니여서 (블로그 다른 글을 보면 알겠지만 상당히 내용이 중구난방이기도 하다) 작성은 딱히 하지 않았다. 근데 벌써부터 그 사이트가 그리운 건 한마음인지 슼보에서도 백준그리워요 닉이 난무했다. Good Bye BOJ 대회는 잘 치른 거 같고 오랜간만에 몰고 회원분들을 만나서 반갑기도 했다.
다시 BOJ 섭종으로 넘어가면, 이제 여러 대회들이 갑작스러운 섭종 소식을 듣고 열 수 있는 새로운 플랫폼을 탐색하거나 심지어 만드려는 움직임이 여럿 보였는데, 이런 상황에서도 대회를 열고 PS/CP 활동을 유지시키려는 분들에게 고마움이 든다.

BOJ는... 서비스 종료다....

대회일 (5/3) 아침에 대전으로 내려갔다. 고등학교 졸업 이후 2년 만에 대전을 찾은 건데, 아직도 뭔가 역 모습이 익숙해보였다. 성심당은 여전히 대기열 길이가 엄청났고, 카이스트까지 대중교통으로 가는 건 여전히 힘들었다. 
null(ptr)scapes란 이름으로 참가했다. Why? 모르겠다, 닉 후보를 찾으니까 아무래도 지메만 하는 이 사람한테는 이게 가장 잘 맞는 것 같았다. ptr는 'PS에요' 호소하려고 괄호 안에 붙였는데 아무래도 이 사람은 자기 닉을 어떻게 발음할지에 대한 생각을 하나도 안 한 게 확실하다.
대회장에 가보니까 생각보다 사람이 많았다. 아직 오프라인 경험이 거의 없어서 그런지, 아는 분들은 거의 대부분 몰고 소속이였던 것 같다. 그래도 전보다는 그 비중이 줄어든 것 같아서 얼마 정도 CP에 참여는 하고 있구나 생각은 들긴 했다. 근데 그거도 그렇고 많은 분들이 그냥 미친 고수로 소문나서 알게 된 것 같기도 하다. 이 중 바로 옆자리에 배정된 분이 무려 dadas08이라... (참고로 다다스님은 몇 달 전에 대곽 후배인 koi312500이 리겜 입문해줬을 때 우연히 옆에서 사볼을 하게 되느라 만나게 된 경험이 이미 있다) 저 분 코드 베껴간다고 드립성으로 말하기도 했다 (실제로 저 분은 대학생 분들 사이에서 아예 대회 2등을 차지하셨다. 그냥 괴물이 맞다.)
아무튼 포인트는 이미 실력이 엄청난 분들이 여럿 있어서 그냥 재미로 풀어보자라는 생각만 하고 있었다. 그나마 최근에 Good Bye 대회와 몇 달만의 코드포스 오렌지 복귀에 성공하는 등 고점이 터지긴 했는데, 그래봤자 레드 퍼포도 아직 아니여서 잘한다는 기대는 딱히 안 한 것 같다. 사실 순위상의 존재조차 대회장에서 다른 분들하고 얘기하느라 알았고, 대회 룰조차 숙지를 제대로 한 편은 아니였던 것 같다. 이 중 하나가 문제 순서대로 난이도가 배치됐다는 점인데, 지금 생각해보니 이 룰은 오히려 몰랐던 게 득이 됐던 것 같다. 아무튼 저렇게 무지한 상태로 대회를 시작했다.

[0:05] B 50 (Total 50)
다들 A를 풀고 있었는데 A가 무서워보여서 바로 B로 넘어갔다. 아무래도 B가 깡수학 같아 보여서 그렇나? 아무튼 successive fibonacci가 서로 서로소임을 보이면 풀리는 문제이다. 근데 그걸 바로 관찰해놓고서 약간 오버띵킹을 심각하게 한 것 같다. 겹치는 원소를 잘못 파악해서 Floorsum 같은 공식을 써야하는 줄 알아서 일단 검증용으로 floorsum을 쓰기 전에 Naive로 섭테2까지 확인해봤더니 맞았다.

[0:22] B 50 (total 100)
그래서 플썸을 만들고 공식을 조금씩 정리해봤더니 시간이 조금 많이 흘렀고, 그 사이 B를 맞춘 사람이 3명 정도 늘었다. 근데 나는 예제를 돌려보니까 벌써 틀리게 나왔는데, 이 때 쯤 난이도 순으로 문제가 배치됐다는 것을 눈치채기 시작했다 (오래도 걸린 것 같다.) 그래서 A로 넘어갈까 했는데 무슨 이유에서인지 B를 마저 풀고 싶다 생각해서 붙잡았더니.... 플썸 자체가 틀린 공식이라는 것을 알게 되었다. 사실 2번째로 가장 쉬운 문제에 플썸 같은 공식이 나오는 게 이상하긴 했는데 눈치가 없어서 그걸 파악하는데 너무 많은 시간을 허비했다. 아무튼 고쳐서 맞았다. 처음에 공식을 이상하게 안 세웠으면 거의 대부분이 A부터 시작해서 높은 확률로 퍼솔이 가능했을텐데 그 점이 좀 아쉽긴 하다.

[0:38] A 100 (total 200)
그래서 다시 A로 돌아갔는데 문제가 좀 무시무시해보였다. 뭔가 원소 몇 개를 고정시키고 값을 계속 변화시키는 발상을 생각해봤는데 그러면 빠지는 케이스가 하나씩 있어서... 모두 다 그런 특수 원소가 홀수 개가 들어가게 construct할 수 있을까 등 괴상한 그래프 이론 문제까지 생각해버렸다. 지금 생각해보면 아무래도 난이도 순이라는 것을 인지한 게 맞나 싶다.
그래서 뇌를 빼고 생각을 해보니까 '그냥 통으로 랜덤질하면 안 됨?' 이랬다. 생각해보니까 기댓값이 요구하는 값과 같아서 한 번 돌려봤더니 맞았다 (사실 부등호 실수 때문에 한 번 TLE가 나긴 했다. 무슨 이유로 초반부에 실수를 좀 많이 하는 것 같다.) 놀랍게도 이게 에디토리얼에 나온 풀이 중 하나였는데 기댓값이 주어진다고 분포가 랜덤질로 가능하나...?라는 생각이 아직 들긴 한다. 아무튼 그거든 deterministic이든 둘 다 실버 발상은 아닌 것 같다 ㅋㅋㅋ B보다 어려웠다.
사실 이 시점에서 진짜 삽질을 엄청나게 한 것 같은데 (특히나 이 사람이 초반부에 강한 걸 생각해보면...) 그래도 20위대 정도에 들은 것으로 기억난다. 나머지 분들도 A/B가 어려웠나보다

[0:51] D 100 (total 300)
C가 무서워보여서 이번에도 건너뛰었다. 그냥 순서대로 풀 생각을 없앤 것 같다. 놀랍게도 AB보다 더 수월하게 진행됐다. 뭔가 개수를 고정시키면 일반적인 그리디 아닌가?라 생각해서 매우 평범한 이탐 + 우큐 문제가 되어버렸다. 유일하게 WA 하나 없이 100점을 맞은 문제이다. 다행히도 이번 대회에서는 WA 페널티가 없어서 본인한테 영향을 주지는 않았다. 다만 이 문제에서 heap default가 최소/최대인지를 좀 혼동해서 시간을 좀 날린 것 같다.

[1:20] C 100 (total 400)
이거도 솔직히 AB보다는 무난히 진행된 것 같다. 사실 가장 큰 문제점이 '연결된'을 아예 connected component로 봐서 처음에 코드를 잘못 짠 건데 예제를 보면 해결되는 거였다. 지문이 약간 모호한 점도 있지만 앞으로 예제를 살펴보면서 내가 해석한게 맞는지부터 생각해야 할 것 같다. 아무튼 다항식 곱셈이라 사실 연산 수가 어떤 순서든 항상 같아서 분할정복 곱셈이 필요 없었는데 그걸 굳이 또 했다. 그리고 답을 출력할 때 답에 998244353 mod를 안 씌워서 한 번 더 틀렸다. 다행히 이번엔 많이 빨리 발견해서 고쳤다. 이번에 BIKO에서 몇 번째 테케에서 틀렸나를 알려주는데 그걸 통해서 어디가 잘못됐는지 얼추 유추가 가능했던 것 같다. 놀랍게도 ABCDE 중에서 푼 시간이 가장 오래 걸렸는데, 쓸데없이 분할정복한다고 구현하느라 (일일히 곱해도 시복이 같기 때문) 시간이 좀 걸렸던 것 같다.

[1:43] E 100 (total 500)
뭐지 왜 갑자기 잘 풀리지
이거도 뭔가 웰노운 같다. XOR max 논리를 적용해보면 이탐이 가능하다는 것을 알 수 있다. 이거도 좀 실수가 있었던 것 같다. 처음에는 오름차순 대신 내림차순이라 답해서 틀렸으며 (놀랍게도 이탐도 마지막에 2로 나누는 연산을 잊어버려서 예제하고 답이 똑같게 나오는 일이 일어나버렸다), 나중에는 트라이 크기 바꿔놓으라 주석에 대놓고 써놓으면서 안 그래서 틀렸다. 그래도 그 외에는 잘 풀렸다. CDE를 은근 빨리 풀어서 그런지 이 시점까지는 점수 동률 상태로 (전부 500점이였다) 한 자리 수 랭킹에 박혀 있었다. 솔직히 2시간 지난 시점에서 그 순위를 유지할 줄은 모르긴 했다.

[2:00] F 30 (total 530)
사실 이 시점부터는 풀 수 있으려나? 라는 생각이 들어서 1위라도 일시적으로 먹을 겸 점수라도 얍삽하게 챙겨보자라는 마인드로 섭테를 긁기 시작했다. 1과 2는 생각하기 비교적 쉬운 아이디어라 간단한 구현으로 30점을 챙겼다. 아쉽게도 이 문제를 풀기 직전 1위 분 (TLE)가 해당 문제에 100점을 추가하여 2위에 만족해야 했다. 그래도 이 정도면 만족한다 생각하고 F를 좀 더 생각하려고 하다가.... 갑자기 대회 안내서에 적힌 문장 하나가 생각이 났다.

' 인터렉티브나 투 스텝 유형의 문제가 적어도 하나 이상 출제됩니다. '

인터랙티브는 거의 항상 나에게 고마운 존재였다. 처음으로 블루 -> 퍼플로 올라간 것도 어려운 문제에 배치된 인터랙티브, 처음으로 퍼플 -> 오렌지로 올라간 것도 어려운 문제에 배치된 인터랙티브 덕분이였다. 오프라인 대회에 참가하면서 풀은 첫 다이아 (SUAPC 25 Summer) 역시 인터랙티브 형태였다. (물론 그건 팀원의 힘을 좀 많이 받긴 했지만)
아무튼 그래서 이번에도 도움이 되려나 살펴보더니 뭔 문제에 2^30, 2^40 같은 괴상한 숫자가 온갖 나오는 것이였다.
그래서 사실 F로 돌아갈까 했는데 솔직히 그걸 풀 바에 G를 이해하려는 게 더 빠르다 생각해서 파보기 시작했다.

[2:21] G 30 (total 560)
k = 1과 섭테 2/3은 대략적인 이탐 논리로 해결하면 풀린다. 사실 여기서 가장 힘들었던 점은 인터랙터 숫자가 참 괴상해서 답을 겁증할 방법이 무지성으로 BIKO에 제출하기밖에 없었다. 섭테 1 - 3은 그래도 유사 이탐이라 비교적 쉽게 맞출 수 있었다. 사실 이건 푸는 거보다 지문 이해가 더 빡센 게 맞는 것 같다. (실제로 2^30, 2^40이 서로 번갈아서 나와서 오타 아니냐를 시전할 뻔했다)

그래서 여기서 더 생각해보니까 분할정복으로 왼쪽 / 오른쪽을 선호하는 쪽으로 각각 나누면 어떨까라는 생각을 해서 한 번 구현을 시작해보았다. 사실 처음에 저걸 '좌파 / 우파'라고 노트에 끄적여놔서 진짜 뻘짓하는 줄 알았는데 알고 보니까 그게 진짜 풀이였던 것이다. 다만, 제한에서 -1/2^20이 조금 찔리긴 한 게 구현을 잘못 했으면 무한 WA의 굴레에 갇힐 수 있다는 생각이 들긴 했다.
그래서 제발 한 번에 맞자는 마인드로 제출했는데 인터랙션 쿼리를 잘못 날려서 2번 연속 틀렸으나 3번째 제출할 때 시간이 조금 오래 걸렸다.
그러고 나서 결과를 보니....

이 상태로 50분을 있었는데 이 사람은 슼보가 줌에 있다고 사진을 안 찍었다. 하마터면 인생퍼포 못 남길 뻔 (cenix님 사진 제공 감사합니다)

[2:32] G 100 (total 630, First Solve)
인터랙티브가 이 사람을 한 번 더 고점으로 끌고 가버렸다. B를 놓쳐서 퍼솔은 영영 못 할 줄 알았는데, 퍼솔에다가 무려 리더보드 1위를 대회 반이 지난 시점에서 먹어보았다. 진짜 꿈 꾸는 줄 알았는데 어떻게 처음에 스피드포스도 애매하게 해놓고 1위를 차지할 수 있었는지가 의문이였다. 좀 10분 동안은 멍때린 것 같다.

그 뒤에 1위를 유지하던 탓이였을까, 나머지 문제는 딱히 성과가 없었던 것 같다. I도 뭔가 O(N^2) (즉, 75점 정도)를 푼 것 같다는 설레발을 쳤는데 알고 보니까 계산 과정부터가 틀려먹어서 어쩔 수 없이 50점짜리 세제곱을 냈다. [3:53, total 680] 이 시점에서는 I에서 점수 최대한 먹는다고 뻘짓을 겁나 많이 하다가 1위 자리를 A - G를 올솔한 분에게 뺏겼는데 나중에 무려 프리즈 전에 H까지 푸신 걸 보니 굇수임이 틀림없다 ㅋㅋㅋ
그 뒤에 남은 유일한 문제인 H도 최대한 깎으려 했는데 2 -> 16 -> 30으로 조금씩 올리는 것이 최선이였다. [4:21, total 710] 대충 플로우 문제라 하는데 이 사람의 플로우 모델링 능력을 생각하면 못 푸는 게 당연하긴 했다 ㅋㅋ

참고로 I 50이 H 30보다 점수를 따기가 더 쉬웠던 것 같다. 이번 대회는 순서를 의심하는 것이 신의 한 수가 맞았던 듯

그렇게 하다가 대회 끝. 프리즈 전 2위, 그리고 프리즈 후 5위라는 성적으로 대회를 마감했다. 놀랍게도 외부인이 없었던 YCPC보다도 한 단계 높게 나왔다 (???) 사실 순위상이 3위까지인 거는 아쉬웠으나 생각도 안 하고 있었는데 그 정도로 근접한 거 자체가 기적인 것 같다. 그리고 그 사이에 따라잡으신 세 분도 전부 뒷심이 그냥 대단한 게 맞는 것 같다. 괜히 레드 하는 게 아닌가 보다. 도대체 뭐를 해야 F를 푸는 건지;; 퍼솔상 넙죽이 에코백도 맛있게 쌀먹하긴 했는데 정작 카이가 날 떨궈서 어쩌면 좀 들고 다니다가 슬퍼질 에코백일 거 같다.

아무튼 끝나고 다른 분들하고 같이 싸이뮤직에서 리겜 입문을 하고 그 다음 날에도 온갖 재밌는 짓을 다 하고 집에 돌아갔는데 글이 너무 길어지는 것 같으니 나중에 쓰고 싶으면 더 쓰겠다. [뒷풀이에서 테트리스 굇수들이 옆자리에 있었던 썰 같은 거처럼 풀고 싶은 게 좀 있긴 하다 ㅋㅋ] 

사실 아는 분이 많지 않다는 거 치고 만난 분들이 너무 많아서 뭔가 다 적을 자신이 없어서 비워두기로 했다 (???) 다들 저하고 같이 얘기 나눠주고 그래서 감사합니다 🥰

최고점이 연속으로 찍히니까 오프라인 대회 중에서는 라스트 댄스가 될 가능성이 높은 SCSC 성적도 갑자기 기대가 되기 시작한다. 창대하게 마무리 한 번 했으면 좋겠다.

 

P.S. 변수명을 이상하게 짓는 건 아직도 습관이다.

tot가 두 개일 때 대체명을 써야 했음 ㄱ-