2026 SCPC에 div3로 참가해 11위의 성적을 얻었다. 감사합니다!
서울대학교 컴퓨터 연구회(SCSC)에서 5월 16일 SCPC를 개최했다. 대학교 입학하기 전부터 여러모로 동경하던 동아리의 대회라 참가했고 별다른 수상경력이 없었기에 다행히ㅎ div3에 배정받을 수 있었다.
인생 첫 오프라인 대회 참가라(ICT경진대회는 제외. 결이 다르니까) 약간 기대를 많이 했고 기대한 만큼 재밌는 경험이었다.
(-) 대회 시작 전
뭔가 일정이 꼬이고 꼬여서 대회 전날에 밤을 새게 됐다. 난 원래 잠 부족에 영향을 많이 받는 편이라 실력발휘가 안 될 것 같은데 백준이 죽은 뒤로 PS를 아예 안 하기도 했고.. 그냥 올해는 참여하지 않고 넘어갈까 고민을 좀 했는데, 대회장 가서 졸더라도 가보고 싶다는 생각을 했다.
밤을 샜으니 시간이 떠 아침에 좀 일찍 서울대로 출발했다. 대회 시작 시각인 13:30보다 좀 많이 이른 11:00즈음에 대회가 열리는 28동에 도착했다.
사실 일찍 도착해서 div3가 진행될 303호에서 자고있으려 했는데, 당일에 KMO가 같은 호실에서 진행되고 있었다. 그냥 303호 앞 의자에서 자기로 하고 커피 한 병 원샷 후 1시간 가량 수면보충을 해줬다. 일어나 보니 12시였고 컨디션이 나름 괜찮았다.
12시부턴.. 딱히 한게 없다. 솔브닥 디코좀 구경하고 1층가서 대회등록, Jane Street 굿즈도 수령하고 그랬다. 303호 입장이 가능하고부턴 노트북 키고 충전기 꼽고..
세터에서 간식을 준비해주셔서 대회시작 전에 당보충을 좀 했다.
그러고 또 솔브닥 디코 구경하고 있으니 슬슬 GLHF이 올라오며 대회가 시작할 때가 되었다.
대회 시작
세터에서 div3는 A~J를 체감난이도 순으로 배치했다고 하여 당연히 A부터 읽었고, 역시나 빵점 방지 문제 느낌이라 바로 풀렸다.
(+01:30) A - Find the Missing Letter AC
문자열에서 S, C의 개수를 세서 개수가 1개인 문자를 출력하면 된다.
그 뒤에 B~G정도 대충 읽어보고 B를 잡았다.
이 때 B에서 지문을 잘못 이해하고 30분가량 뻘짓하다가 착잡한 마음으로 C로 넘어갔다. C는 수열문제라 풀 수 있을거라 믿었고, 오래 지나지 않아 풀이를 냈다.
(+52:42) C - The Kth Smallest Number WA (+1)
엥? 왜틀렸지?
M<N인 경우를 생각하지 않았었다.
(+58:36) C - The Kth Smallest Number AC
이 때 까지만 해도 잘해봐야 4~5문제 풀고 대회가 끝나겠거니 싶었다. 쉬운 문제 2개 풀었는데 1시간이라니..
적당한 관찰을 통해 a_(N+1)부터는 일정하다는 것을 알 수 있고, 증명도 어렵지 않다.
구간이 움직이며 제외되는 원소가 a_i보다 작은 경우와 큰 경우를 각각 생각해보면 각 구간에서 k번째 큰 원소의 값이 변하지 않는다.
C를 풀고 나선 짜증났던 B보다 D를 먼저 봤다. 다행히 D가 어렵지 않았고, 풀이가 금방 나왔다.
(+1:13:02) D - Sushisushi Conveyor Belt Sushi Restaurant AC
초밥을 먹든 안 먹든 시간이 흐르기 때문에 시간 T를 통해 X_i각각의 최대 길이에 제한을 둔다고 생각할 수 있다. 따라서 T에 대한 조건을 선제적으로 처리할 수 있다.
이후에 초밥 칸 각각에서의 선택은 다른 초밥 칸에 영향을 주지 못하므로 별개로 계산해주어 최댓값을 구하면 된다.
그 후엔 세터에 대한 믿음을 갖고 B를 다시 봤다. 다시 보니 내가 문제를 잘못 이해해서 어렵게 풀고 있던게 맞았다. w가 항상 1일 줄이야.
(+1:27:12) B - Mobilint Tensor Scheduling (REGULUS) AC
하나의 자식 노드에서 여러 부모 노드로 올라가는 경우는 없으므로 초기 상태보다 메모리에 많은 노드가 들어가있는 경우가 존재할 수 없다. 결국 맨 처음 연산이 피크 메모리 사용량이고, leaf+1이 답이었다.
w, M조건이 의미없었던 문제. 높은 div에서 하드버전으로 내기위한 문제인 것 같다.
이후에 E랑 F를 봤고, E는 감이 잡히지 않아서 쿼리문제인 F를 봤다.
그나마 F는 문제 이해가 금방이었고, 구현도 생각보다 금방 떠올라서 어렵지 않게 풀어냈다.
(+1:47:38) F - SQL AC
음수인 쿼리에 대해서는 해당 쿼리의 출력을 쉽게 결정할 수 있다.
양수 쿼리가 문제인데, 케이스를 정리해보면 그래프이론/유니온파인드처럼 풀 수 있다.
i번째 쿼리 = y라고 하자. (y>0)
y번째 쿼리가 음수라면, i번째 쿼리의 출력은 y번째 쿼리의 출력과 동일하다.
쿼리의 y번째 수가 양수이고 해당 y번째 수의 출력이 결정되어있다면, i번째 쿼리의 출력은 y번째 쿼리의 출력과 동일하다.
쿼리의 y번째 수가 양수이고 해당 y번째 수의 출력이 결정되지 않는다면, i번째 쿼리의 출력은 결정되지 않는다.(아무거나 넣어도 된다)
결정된 쿼리들만 그래프탐색의 아이디어를 이용해 올바른 출력을 구해주고, 나머지 쿼리들의 출력은 1로 채워주면 된다.
느낌이 좋다. 확실히 C를 푼 이후로 문제들이 상당히 빠르게 풀리고 있다.
2시간도 안됐는데 5솔이라니!
이후엔 E가 그렇게까지 어려운 문제는 아닐거라고 생각하고 계속해서 관찰을 했다.
(+2:00:00) 스코어보드 프리즈
당시 스코어보드 상황을 보면
난 5솔에 +1패널티로 29등, 1등을 포함한 상위권들은 7솔이었다.
쉬운 문제부터 풀리는 대회임을 감안하면 남은 1시간동안 순위변동이 그리 클 것 같진 않았고, 1~2문제를 더 풀면 순위가 많이 오를거라고 생각했다.
그런 와중에 E의 풀이를 냈다.
(+2:06:34) E - DETOX AC
시작하자마자 자신의 명찰을 알 수 없는 학생(출력이 1이 아닌 경우)가 굉장히 제한적이라고 생각했다.
OX_OX 또는 XO_XO의 형태가 현재 자신의 명찰을 알 수 없는 유일한 경우이고, 어떻게 케이스를 만들어도 3이상의 출력이 나오지 않는다는 것을 확인할 수 있다.
O/X에 상관없이 OO_, O_O, _OO의 경우는 무조건 1이고, 이 세 경우가 아니면 2가 아닐 수 없다.
6솔브!! 처음에 생각한 것보다 훨씬 잘봐서 마음이 편해진 상태였다. 이때부턴 어차피 남은 문제들이 다 어려워보여서 한 문제만 더 풀자는 생각으로 임했다.
G를 좀 읽어보니 내가 거의 안 풀어봤던 게임이론 문제였다. 문제의 요구사항을 도저히 떠올리기 어려워 그래프 이론으로 보이는 H를 잡았다.
30분쯤 뒤, 적당히 증명은 잘 모르겠는데 이게 답이어야만 할 것 같은 그리디한 풀이를 냈다.
(+2:39:14) H - Cramming WA (+2)
엥? 뭐지 잘못됐나
아! A - B를 계산하는 모든 부분에서 max(1, A - B)를 써야 하는데 한 부분에서만 썼다. 으휴
(+2:41:47) H - Cramming WA (+3)
아????
증명을 제대로 하지 않은 풀이었어서 이때 그냥 틀린 풀이인가 잠깐 고민했다.
아무리 생각해도 맞는데... 하면서 코드를 쭉 보는데 =에 ==를 써놨었다. 허
(+2:44:05) H - Cramming AC
그래프가 트리 구조인 것이 문제의 복잡도를 크게 낮췄다.
그래프가 트리 구조를 따르므로 위와같이 공부시간이 감소된 두 개 이상의 과목이 한 과목에 영향을 미치는 일은 일어나지 않는다.
첫 과목 공부시간 A를 제외하면 최대한 공부시간을 줄일 때 공부시간이 감소되지 않은 k개의 과목을 먼저 공부하고 공부시간이 kB만큼 감소된 한 과목 공부하는 경우밖에 생기지 않는다.
결국 A + (kA-kB)의 꼴을 따르게 되는데, 감소되는 공부시간에 하한이 있으므로 공부시간 감소를 한 번 받은 과목부터 공부하는 것이 유리하다.
사용할 수 있는 시간은 A + k * max(1, A - kB)이고, 공부한 과목의 수는 k+1개, 공부하는 순서는 아무 노드나 잡고 아무 탐색이나 돌려도 괜찮다.
7솔브를 달성했다.
이때부턴 15분밖에 안 남기도 했고 나머지 문제들이 너무 어려워 보여서 그냥 끝날 때까지 멍때렸던 것 같다.
(+3:00:00) 대회 종료
대회가 종료되었고, 뒤에 일정이 있었기에 시상식/문제 해설은 듣지 않고 나왔다.
체감난이도 : B2, S2, S1, S2, G3, G4, ?, G3, ?, ?
전체적으로 문제들이 관찰을 통한 그리디스러운 풀이가 많은 느낌이었다. 내 문제풀이 습관이랑 잘 맞아서 좋은 성적이 나온 것 같기도.
그동안 참여했던 NYPC, KOI는 전부 OI형 문제셋이어서 ICPC 형식의 대회가 더 신선한 경험이 된 것 같다. 내년부턴 div3를 참가하지 못하니 앞으로 Atcoder, Codeforces등의 대회에 좀 참여해볼 생각이다.
그리고 백준이 다시 살아돌아온다는 말이 있으니(!!) 백준이 돌아오면 본격적으로 PS도 많이 해야지.