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

0. 들어가며

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

 

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

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

1. 대회 타임라인

0:00

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

0:24 F WA

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

0:28 F AC

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

0:28 ~ 0:45

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

0:52 J AC

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

1:22 A AC

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

2:01 C WA/TLE

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

2:18 D WA

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

2:27 G WA

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

2:31 G WA

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

2:55 C WA/RE

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

2:59 C 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이 어떤 블록에 있는지를 알 수 있고, 그 구간에서 경계에 걸리는 블록을 제외하고는 온전하기 때문에 바로 구간의길이//2 로 필요한 덧칠 개수를 구할 수 있습니다.
근데 손테케에서 자꾸 틀렸습니다. 3:50이 될 시점까지 왜 틀렸는지 이유를 못찾았고, 그러다 갑자기 G가 틀린 이유가 떠올라서 G를 풀러 갔습니다.

3:52 G WA

사실 틀린 이유를 알았다는건 단순한 착각이였습니다. SCSSC, SCCSC 말고도 SSCSC나 SCSCC가 있어도 테라가 무조건 승리한다고 생각했는데, 이 문자열들은 이미 SCSC를 포함하고 있어서 조건상 나올수가 없었습니다. 그래서 구현하다가 착각했다는걸 깨닫고, 남은 10분동안 풀 문제가 없다고 생각해서 G 코드만 하염없이 바라보고 있었습니다.
그런데 코드를 보다가, 테라가 승리하는걸 판별했음에도 반복문 break를 안하고 flag = 1 만 하고 있다는걸 깨달았습니다! 바로 반복문 안에 flag가 1이면 break하는 코드를 추가해 제출했고, WA를 받았습니다.

3:53 G 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라는 같은 주제로 대화하고 웃을 수 있다는게 참 좋았던 것 같습니다. 좋은 대회 만들어주신 출제/검수/운영진 분들 감사합니다!