2026 SCSC 프로그래밍 경시대회 후기(Div.2)

0. 들어가며#

중간고사가 끝날 즈음에 마침 SCSC 프로그래밍 경시대회 신청 안내가 나왔습니다. 이럴 때 아니면 언제 가보겠냐는 생각으로 같은 학교인 snowwantdev를 꼬셔서 온사이트에 Div.2로 참가하게 되었습니다.

둘 다 강원과학고등학교 PS 동아리인 '티라노' 소속이었기 때문에 이름을 티라노사우루스에 관련된 걸로 맞추기로 했습니다. 결과적으로는..

서울대학교에 티라노사우루스 두 마리가 출현하게 되었습니다. 만족스럽네요.

1. 대회 타임라인#

0:00#

A가 가장 쉬운 문제라서 A부터 봤습니다. 지문을 읽고 뭔 소리인지 이해가 안 돼서 바로 노트에 그려봤는데, 그러고도 더 이해가 안 됐습니다. $w_i$를 모든 정점에 대해서 고려해줘야 해서 절대 쉽게 풀리는 문제가 아닐 거 같은데 어째서 A번에 있는 건지.. 10분 동안 생각해도 모르겠어서 슥보를 보니 A를 푼 사람이 많길래 뭔가 놓치는 게 있나 보다 하고 바로 다른 문제로 넘어갔습니다.

F — 0:24 WA#

예시를 하나 잡고 시도해보니, 그냥 수열을 정렬하고 $K$번째에 있는 값이 항상 $a_M$이라는 관찰을 할 수 있었습니다. 바로 제출했고, WA를 받았습니다.

F — 0:28 AC#

좀 더 생각을 해보니 $M \le N$이라면 정렬하기 전 원래 수열에서 $a_M$을 출력해야 했습니다. 빠르게 수정하고 AC.

0:28 ~ 0:45#

C가 만만해보이길래 바로 구현하려고 했습니다. 어차피 A는 어떻게든 배치할 수 있기 때문에, B가 최대한 많이 나오게, 겹칠 수 있다면 B를 최대한 겹쳐서 구성하는 게 최적임을 쉽게 알 수 있습니다. $O(M^{2})$이 안 되기 때문에 효율적이게 B가 겹치는 최대 길이를 판별해야 했고, 알고리즘이 바로 생각이 안 나서 패스했습니다.

J — 0:52 AC#

그러고 나니 슥보에 J솔이 많았습니다. J를 슥 보니 왠지 모든 학생이 1 아니면 2번째에 답을 맞힐 수 있을 것 같았고, '이게 답이 아니면 이렇게 많이 안 풀렸겠지~'라는 생각으로 구현해서 AC를 받았습니다.

A — 1:22 AC#

이젠 진짜 A를 풀어야겠다는 다짐으로 다시 A를 붙잡았고, 한 20분 정도 더 고민하다가 지문을 다시 읽고 깨달았습니다. $w_{i} = 1$이라는 조건이 있다는 걸요. 이렇게 되면 트리에서 위로 올라갈수록 필요한 정점 개수가 같거나 줄어들기 때문에, 답은 항상 리프 노드의 개수 $+ 1$이 됩니다. 지문을 잘 읽는 습관을 가집시다...

C — 2:01 WA/TLE#

$O(M^{2})$이 안 되는 걸 아는데 $O(M^{2})$ 코드를 제출했습니다. 아무 생각 없이 제출한 건 아니고, 지금 제출한 코드가 TLE만 받는다면 로직은 올바르니 시복만 줄이면 된다는 걸 알 수 있고, 만약 WA를 받으면 로직도 틀렸으니 던지자는 마인드였습니다. 그리고 WA/TLE를 동시에 받아서, 던졌습니다.

D — 2:18 WA#

분명 어디선가 본 거 같은 문제인데 풀이가 안 떠올랐습니다. 일단 간단하게 구간에서 필요한 덧칠 개수를 누적합해서 쿼리별로 구하는 코드를 짰고, 예제가 돌길래 제출했습니다. 근데 WA를 받았어요! C부터 D까지 슬슬 말린다는 생각이 들어서 넘겼습니다.

G — 2:27 WA#

보자마자 홀짝의 느낌이 강하게 들었습니다. 대충 SCS..SC나 SC..CSC처럼 완성되기 직전 문자열이 있으면 C를 없애서 SS..SC로 만들거나, S를 없애서 SC..CC로 만드는 걸 통해서 상대방이 SCSC를 못 만들게 막을 수 있기 때문에 문자열이 더 이상 없을 때까지 끌고 갈 수 있다고 생각했습니다. 그리고 또 WA를 받았습니다!

G — 2:31 WA#

만약 처음 주어진 문자열에 SCSSC나 SCCSC가 있다면, 홀짝에 상관없이 테라가 무조건 승리한다는 걸 알아냈습니다. 그렇지 않으면 홀짝이겠구요. 이건 진짜 맞다고 생각하면서 코드를 제출했는데.. 또 WA를 받았습니다.

C — 2:55 WA/RE#

1:22에 A를 AC한 이후로 1시간 반이 넘도록 아무 문제도 풀지 못해서 멘탈이 갈려나가기 시작했습니다. 나머지 문제는 아예 모르겠고 D랑 G는 더 하면 폭사할 거 같아서 다시 C로 돌아왔습니다. 다시 손테케를 만들어서 돌려보면서 로직을 고쳤고, 대회 전날에 급조한 템플릿에서 KMP를 가져와서 사용했습니다. 더 이상 틀릴 리가 없다고 생각하고 제출했고, 이번에는 WA랑 RE를 동시에 받았습니다.

C — 2:59 AC#

KMP를 사용하면서 너무 '문자열'에 집중한 나머지, 입력으로 들어오는 B는 array라는 걸 망각하고 문자열로 만들어서 KMP에 집어넣었습니다. 예제와 손테케에서는 A, B의 원소를 모두 1자릿수로만 구성해서 오류가 없었지만 실제로는 $10^{6}$까지 가능했기 때문에 틀렸던 것입니다! python으로 풀고 있었기 때문에 그냥 KMP 함수에 문자열 대신 배열을 넣어도 올바르게 작동했고, B 배열을 직접 집어넣는 것으로 결국 AC를 받았습니다.

2:59 ~ 3:50#

슥보를 보니 가장 많이 풀린 6개가 A C D F G J였습니다. 남은 1시간 동안 새로운 문제를 잡는 건 너무 도박 같았고, D와 G 중에 적어도 1개는 풀어서 5솔까지 올리자는 다짐을 하고 D를 다시 잡았습니다.

기존에는 깡으로 누적합을 했기 때문에, 쿼리로 주어지는 구간의 경계에 대한 처리가 추가로 필요하다는 걸 알았습니다. 연속된 문자들을 하나로 묶은 블록마다 길이를 세주면 이분탐색으로 $l$, $r$이 어떤 블록에 있는지를 알 수 있고, 그 구간에서 경계에 걸리는 블록을 제외하고는 온전하기 때문에 바로 $\lfloor \text{구간의 길이} / 2 \rfloor$로 필요한 덧칠 개수를 구할 수 있습니다.

근데 손테케에서 자꾸 틀렸습니다. 3:50이 될 시점까지 왜 틀렸는지 이유를 못 찾았고, 그러다 갑자기 G가 틀린 이유가 떠올라서 G를 풀러 갔습니다.

G — 3:52 WA#

사실 틀린 이유를 알았다는 건 단순한 착각이었습니다. SCSSC, SCCSC 말고도 SSCSC나 SCSCC가 있어도 테라가 무조건 승리한다고 생각했는데, 이 문자열들은 이미 SCSC를 포함하고 있어서 조건상 나올 수가 없었습니다. 그래서 구현하다가 착각했다는 걸 깨닫고, 남은 10분 동안 풀 문제가 없다고 생각해서 G 코드만 하염없이 바라보고 있었습니다.

그런데 코드를 보다가, 테라가 승리하는 걸 판별했음에도 반복문 break를 안 하고 flag = 1만 하고 있다는 걸 깨달았습니다! 바로 반복문 안에 flag가 1이면 break하는 코드를 추가해 제출했고, WA를 받았습니다.

G — 3:53 AC#

앞에서 WA를 받은 이유는 들여쓰기 때문이었습니다. 4칸 들여쓰기로 코딩을 하는 저와 달리 엣코더 제출창에서는 탭을 누르면 2칸 들여쓰기가 되었고, 그것 때문에 break하는 조건문이 제대로 사용되지 못한 게 원인이었습니다. 그래서 확실하게 하려고 조건문을 없애고 바로 break를 하도록 로직을 바꿨고, 대회 종료를 7분 남기고 G AC를 받았습니다.

3:53~4:00#

틀린 부분만 고치면 D를 풀 수 있을 거 같아서 마지막 7분도 D를 디버깅하는 데에 집중했습니다. 이분탐색할 때 인덱스를 잘못 잡은 게 있어서 고쳐주었지만 여전히 손테케에서 틀렸고, 결국 D를 풀지 못하고 5솔로 대회를 마무리했습니다.

끝나고 업솔빙을 해보니 XXX 같은 블록까지 필요한 덧칠 개수에 포함시켜버린 게 틀린 원인이었습니다.

2. 마치며#

전체적으로 AC를 상당히 늦게 해서 5솔 중에서도 끝자락인 65위를 하게 되었습니다. 수상 커트라인이 6솔이어서 아쉽네요.

제 첫 온사이트 대회였는데, 정말 재밌었습니다. 이렇게 많은 사람들이 모인 곳에서 PS라는 같은 주제로 대화하고 웃을 수 있다는 게 참 좋았던 것 같습니다. 좋은 대회 만들어주신 출제/검수/운영진 분들 감사합니다!