2026 SCSC 프로그래밍 경시대회 [Div. 1] 후기

카이런 (https://jkrt2.tistory.com/10) 참가가 얼마 안 됐지만 계속 달린다. 이번에는 서울대다.
이 대회가 원래였으면 오프라인 대회 기준으로 라스트 댄스였을텐데 며칠 전에 입대 연기라는 대형참사가 터져서 의도치 않게 PS 수명이 조금 늘어났다... UCPC 팀원도 구해야 할 거 같다. 그나마 요즘 폼이 상승세인 게 다행이라 하자 ㅋㅋ;

아무튼 Division 1에 배정됐다. 지난 SCSC 대회가 열렸을 당시에는 PS는 시작하지도 않았을텐데, 어쩌다 딥2하고 딥3을 건너뛰었다. 다름이 아닌 코포 레이팅 때문인데, 몇 달 전에 2번 연속으로 최고점이 찍혀서 2100을 간신히 넘긴 적이 있었다.

진짜 띡하고 한 번 올라갔다 (2104)

 

그 뒤 곧바로 20층으로 내려가고 그 뒤 7번 연속 20층 레이팅을 넘어서 20층 퍼포를 찍는 저 세상 저점-고점 차이를 보여주고 있었다가, 카이런 포스트에도 잠시 언급한 것과 같이 쌀먹 인터랙티브 덕분에 다시 오렌지를 찍어서 4점 차이로 딥2에 못 갔다는 억울함(...)은 조금 풀린 것 같다.

 

하지만 카이런과 비교해서 난이도가 오름차순이 아닌 점하고 딥1이라 난이도 분포가 골 - 루라는 게 좀 많이 무섭긴 했다. 그래서 굳이 솔브를 많이 할 생각은 하나도 안 하고 들어갔다.

 

참고로 그 날 처음으로 서울대 안으로 가봤는데, 서울대 역하고 샤 구조물하고 거리가 엄청나게 먼 걸 보니까 서울대가 얼마나 큰지 체감이 된 것 같다. 연세대도 은근 큰 것 같았는데....

이번에는 닉네임을 콘치즈볼루션으로 했다. 지난 번처럼 지메 맵 (https://gdbrowser.com/105724358, 전 platformer 1위) 이름을 갔다 붙였다. 사실 대회 내 누군가를 사칭할까 생각하기는 했는데 그건 나중에 기회가 된다면 한 번 해보겠다.

 

1:03 - C AC [+6]

사실 퍼솔한다는 마인드로 A를 건너뛰었다. 아무리 봐도 '잘' 만들면 풀릴 해구성 문제였는데 아무리 봐도 패턴이 안 보여서 N >= 8, 10, 11, 14... 이렇게 수를 늘려가면서 얼마나 가능하고 불가능한지를 찍다가 어느새 퍼솔은 간 지 오래 됐고 WA도 6개나 쌓였다. 결국엔 맞추긴 했는데 아무래도 믿음의 풀이만 계속 제출하다가 1솔한 시점에서 벌써 30위가 된 상황이였다. 여담으로 이 문제는 대 mythofys가 퍼솔에 성공했다.

 

1:35 - A AC [+1]

C를 푼 시점에서 가장 많이 풀린 게 A여서 돌아갔더니 상당히 까다로운 이탐 문제임을 깨달았다. 그걸 알아도 생각보다 구현이 까다로워서 (Master 수의 변화를 트래킹하는 것이 생각보다 실수하기가 쉽다) 1틀을 했다. 그래도 이번 대회에서 가장 쉬운 문제는 맞는 것 같다. 그런데 나중에 에디토리얼에서는 O(N+Q) 그리디가 가능하다고 하였다. N 제한이 2000이 아니였다면 이 문제는 못 맞췄을 것 같다.

 

2:38 - J AC [+1]

사실 이 문제는 얼마나 어려운지 파악을 잘 못 하겠다. 카이런 G와 비슷한 식으로 분할정복을 하면 되지 않을까라 했더니 맞았다. 근데 레지스터를 2048개 이하 써야 한다는 조건이 좀 빡세긴 했는데, 실수로 아직 분할하는 과정에서 채팅봇이 응답하는 가능성이 있었기 때문이다. 그건 좀 어거지로 무작위화를 돌려서 풀 수 있음을 알게 되었고, 그 뒤에는 꽤 순조롭게 맞았다. 좀 무식하게 푼 거 같긴 한데.... 지금 한 문제도 더 풀기 어려운 상황에서 그런 걸 따질 시간은 없었다.

 

아무튼 이걸 풀 당시에 K 데이터 반영 오류 때문에 대회 시간이 30분만큼 늘었다는 뉴스를 듣게 되었다. 그래서 그 문제도 한 번 보면서 풀려고 했는데 아무래도 CHT 똑붙....인가 했는데 슬라이딩 윈도우 마냥 제거하는 방법을 몰라서 (그리고 그 당시 제대로 못 들어서 L 최종 제한이 100만이였는지 500만이였는지를 잘 몰라서) 그냥 건너뛰었다. 차라리 물어보고 제출하는 게 낫다라는 생각을 지금 와서 뒤늦게 하고 있긴 한데 어차피 풀었어도 등수에 차이는 그렇게 많이 나지는 않았을 것 같다. 참고로 정해는 CHT + Silding Window라는데 도대체 저게 왜 O(L)에 되는 건지 모르겠다. DP 최적화는 아직 배울 게 많나 보다. 그 외에도 D도 뭔가 트리 DP 이상한 거 쓰면 되나 하고 찍맞 유사한 풀이를 몇 개 해봤는데 될 리가 없었다. 그건 뭔 페이커 알고리즘이라고 쓰는 게 있다는데 난 대 상 혁만 알고 있고 공부하기가 귀찮다. 아무튼 다 실패로 끝날 줄 알고 3솔로 만족하려 했더니....

 

3:43 - F AC [+]

정말 놀랍게도 하나의 문제를 더 풀었다!!! 이거도 A처럼 제한을 더 늘릴 수 있는 문제라는데 (NTT로 O(NlogN)이 가능하다고 한다), 다행히 quadratic 풀이가 가능했다. 누적 합 + DP를 사용하면 되는데, DP 식을 짜다가 진짜 머리가 아팠다. 정리를 잘 못 하는 인간이라 식 변수도 혼동하는 경우가 몇 번이나 있었지만 놀랍게도 꽤 일찍 예제가 나오는 데 성공하였고 그대로 AC를 맞았다. 다행히 이번 문제는 틀리기 어려운 예제가 있어서 (그리고 스저지 문제가 아니여서) 푼 문제 중 유일하게 WA 없이 맞추게 되었다.

 

추가로 주어진 30분은 의미없게 쓰다가 그렇게 대회 끝.

(앳코 기준) 페널티 700분에 4솔로 15위로 마무리했다. C부터 욕심부리지 않았으면 조금 더 낫았을 것 같긴 한데 처음에 박은 거 치고는 뭐 F 푼 것만으로도 충분히 만족스러운 것 같다. 이제 딥1에도 꽤 경쟁력이 생겼다는 점을 보여준 것 같다. 10위 이상이면 키보드가 상품이긴 했는데 받았다면 지메 하느라 업키만 혹사시킬 게 뻔했다. 문제 중에서는 F하고 J가 예상 난이도 P1이라는데 요즘 플레 상위권을 계속 하나씩은 풀고 있는 것 같아서 성장세가 드러나는 것 같긴 하다. 재밌는 점은 P5라고 주장한 문제 (H)가 있음에도 그 문제는 결국 0솔로 마무리되었다. 진짜 지문 보고 바로 입구컷 당했는데 난이도 파악하기도 생각보다 중요한 스킬 같다.

최종 순위

이 대회 Div 1은 카이런에 2위를 했던 dadas08이 우승하게 됐다. OI식으로 해서 처음 3문제에 거의 30틀을 했고 프리즈 당시 본인 아래였음에도 불구하고 (이건 카이런 때도 그랬다.) 혼자서 솔브 수 차이로 혼자 1위를 가져갔다. 저 사람이 ICPC에 나가면 대회 폭격할 거 같다. 참고로 대회가 끝난 뒤 집에 돌아와서 저 사람 온라인 저지 내 대회 문제를 세팅했다. 집 가는 버스가 하도 막혀서 12시에 도착했다 보니까 세팅이 끝날 때는 대회 시작 2시간 전인 오전 3시였다...

https://dojoi.xyz/ko/problems/65 하고 https://dojoi.xyz/ko/problems/67 이렇게 두 문제를 내긴 했는데 (많관부) 진짜 세팅하는 거도 어렵다고 느낀 게 폴리곤에 별별 오류가 튀어나와서 고치는데 LLM하고 다른 분들의 도움을 정말 많이 받았다. 그 두 문제는 그나마 입력 - 출력 형식이 매우 간단했는데 SCSC에는 저런 걸 12문제 내라니 참 출제자 분들하고 검수자 분들에게 감사함이 느껴지긴 한다 대회 검수 마저 해야 하는데 으악

K 오류나 슼보 구현이 안 된 상태인 등 약간 삐걱거린 데가 있긴 했지만 그래도 재밌게 푼 것 같다. 대회 후에는 rongrongbot님 팟하고 같이 인도음식 저녁도 옴뇸뇸 먹고 (사실 이건 사진 찍은 게 있지만 너무 구데기같이 찍어서 팟에 어느 누군가가 본인의 블로그에 올리겠지 마인드로 건너뛰겠다 🥰)앳코 폰 스피드 싸움에서 발렸다 ㅋㅋ! (저건 빠른 입출력 해놓고 import sys를 잊어먹어서다... 에휴 바보)  놀랍게도 그 대회를 레이티드로 하신 분들도 있는데 나처럼 딥1 가기가 싫었나보다 ㄱ-