올해도 작년처럼 서울대학교 컴퓨터 연구회 SCSC에서 주최하는 SCPC(SCSC Computer Programming Contest)가 열려 참가했습니다. 작년에는 별 생각 없이 지원해서 검수했던 대회였는데, 올해는 참가해야겠다는 생각이 들어서 신청했습니다. 닉네임을 뭘로 할지 조금 고민을 하면서 신청 폼을 작성할 당시 옆에 있던 친구한테 스코어보드 닉네임을 추천해 달라고 했는데, admin을 얘기하길래 바로 그대로 admin을 닉네임으로 해서 참가했습니다.
제가 참여한 디비전은 Division 1입니다. Codeforces 오렌지를 찍었기 때문인데, 제가 그렇다고 수많은 GM이나 IGM들과 경쟁했을 때 경쟁력이 있는 것도 아니라서 높은 상은 받기 어려울 것이라고 생각하고 대회에 임했습니다. (Division 2였으면 거의 우승을 바라봤을 텐데 아쉽습니다. 물론 Div.1에 계신 모든 분들이 Div.2였다면 우승을 바라보셨을 것입니다..)
같은 날 서울대학교에서 KMO 1차가 있었는데, SCPC 대회를 치는 경곽 학생들이 다들 치는 것 같아 저도 신청하고 같이 쳤습니다. 가채점 결과 66점인 것 같은데 어느 정도 상을 주는지는 잘 모르겠습니다. 중등 KMO를 준비하던 중학교 1학년 때랑 비교해서 경시 문제를 푸는 실력은 크게 변화가 없는 듯합니다.
12:30에 앞선 KMO가 끝나고 급하게 SCPC가 열리는 28동으로 이동했습니다. 이동하니 12:40 정도로 약 20분 정도 시간이 남아 있었습니다. 일단 점심을 먹지 못했기 때문에 급하게 간식을 챙기고 자리에 앉았습니다. 여담이긴 하지만 의자가 살짝 불편했는데, 책상과 의자 사이 거리를 마음대로 조정하지 못하는 게 조금 불편했던 것 같습니다. (그래서 자세가 꽤 불편했는지 그날 밤과 다음날 아침까지 목이 좀 뻐근했습니다.)
대회 시작 전에는 정신없이 달려온 탓에 간식이나 좀 먹었고 사진 한 장도 찍지 못했습니다. 아무튼 서둘러 atcoder에 로그인하고 대회가 시작했습니다.
[0:00 - 1:17] A CUBRID HA Load Balance AC (4WA 5RE)
어.. 일단 A부터 말렸습니다. 작년 대회를 검수했고 작년 대회의 div1 A번이 p3, B번이 제일 쉬운데 g1이었던 걸 기억하고 있었지만 그럼에도 A를 읽었는데 어떻게 풀지 바로 생각나지 않는 것 자체가 당황스러웠습니다. 일단 1 i가 주어지면 그 이후로는 반드시 꺼지니까 각 서버를 켜서 사용할 수 있는 시간 범위를 생각하면서 우큐 그리디 같은 느낌을 생각했습니다. 하지만 이내 O(NQ)가 도는 제한이고 그냥 역순으로 그리디하면 된다는 생각이 들어 그대로 구현했습니다.
그런데 바로 1WA를 적립합니다. 그러고 나서 보니 1 i가 중복해서 있는 경우 가장 처음 쿼리만 생각해줘야 하는데 가장 마지막 쿼리 기준으로 꺼지는 것처럼 코드가 짜여 있었습니다. 그래서 이를 고치고 다시 제출합니다.
또 2WA를 적립합니다. 그러고 보니 아무런 서버도 켜져 있지 않는 상태는 유효한 상태인데 이 상태를 Master 서버가 없어서 무효한 상태라고 판단하고 Master 서버를 억지로 만들어내려고 하는 상황이었습니다. 그래서 이것도 고치고 다시 제출합니다.
그런데 3WA를 적립합니다.
이때 틀린 데이터 개수가 단 1개인 것을 확인합니다. 그래서 작은 N에 대해서 열심히 반례를 찾으려고 시도해봤지만 잘 나오지 않았습니다. 그래서 결국 저 WA 데이터 하나를 찾아서 뚫는 방향성을 생각하게 됩니다.
일단 작은 N에서 틀리는 게 맞는지 확인하기 위해 assert를 박아서 제출합니다. (3WA 1RE) RE 덕에 작은 N에서 틀린다는 걸 확인해냈습니다. 하지만 N이 작아도 Q가 큰 상황일 수도 있기 때문에 다시 한 번 과감한 assert를 박고 제출합니다. (3WA 2RE)
다행히 N과 Q가 모두 작은 데이터에서 틀리는 상황이었기 때문에 반례를 찾을 만할 것이라고 생각하고 계속 반례를 찾습니다.
그러다가 우연히 아래와 같은 반례를 찾아냅니다.
4 2
2 2 1 0
2 0 1 2
답은 Master 서버 2개, Slave 서버 2개가 최소한으로 필요하므로 4이지만, 코드가 3을 뱉었습니다.
이 반례를 해결해서 제출했더니 아래와 같이 더 많은 테케에서 나가는 걸 확인하고 맙니다. (4WA 2RE)
결국 모르겠어서 다시 원래 코드로 돌아가서 assert를 더 찍어봅니다. 반례가 N = 4일 때라는 걸 찾았고, 아래와 같은 코드를 제출합니다. N이 4가 아니면 아까 49개를 맞혔던 코드로 풀고, 그렇지 않은 경우는 위에서 찾은 반례와 같은 형태를 해결하는 코드를 냈습니다.
그렇게 해서 데이터를 뚫어내는 데에 성공하고, 어떻게든 1AC를 쌓습니다.. 패널티가 망해서 솔브 수가 중요하겠다는 생각을 하면서 다음 문제로 넘어갔습니다.
[1:17 - 1:40] C. SCSC Magical Garden AC (1TLE)
A를 풀고 스코어보드를 보니 C 솔브가 꽤 많이 보였습니다. 그래서 바로 C로 넘어갔습니다. 임의의 3x3 내부에서는 S가 더 많지만 전체 NxN 격자를 보면 C가 더 많도록 격자를 구성하는 문제였습니다. 고민을 좀 해보니 N이 3의 배수면 불가능하고, N이 조금만 커져도 불가능함을 증명할 수 있었습니다. 그래서 N = 4, N = 5, N = 7 정도를 직접 구성하다 보니 N = 7에서 쉽게 구성하는 방법을 찾아냅니다. 3x3을 아래 모양으로 반복해서 채우는 것입니다.
CCC
CSS
SSS
마찬가지로 N = 8에서는 아래 모양으로 반복해서 채우면 됐습니다.
CCS
CCS
SSS
그래서 N을 3으로 나눈 나머지에 따라 분류해서 위 모양대로 채우고 S가 더 많은지 체크해서 출력하는 코드를 냈는데, 예상 외의 TLE를 받습니다. 그러고 나서 문제를 다시 보니 출력 데이터의 크기로 입력의 크기를 제한하고 있는 걸 확인했습니다. 그래서 로컬에서 작은 N에 대해 계속 답을 찍어보며 NO가 되는 임계점을 찾아서 제출했습니다. 그래서 AC를 받습니다.
[1:40 - 2:43] J. ChannelTalk Workflow AC (1WA)
C를 풀고 스코어보드를 보니 J가 많이 풀려 있어 또 J로 갑니다. 보니까 문제가 해구성이라서 재밌게 해볼 만하다고 생각했습니다. 일단 문제를 처음 읽고 나니 K를 늘리는 것에서 불가능한 상황은 없을 것 같고, K가 작을 때는 완전 이진 트리 형태로 구성해야 한다는 생각이 들었습니다.
그래서 일단 아래에서부터 합쳐주면서 토너먼트처럼 트리를 구성해주고 나머지 모듈은 K를 1씩 늘리는 데에 사용하는 풀이를 생각했는데, K가 조금만 커지면 사용하지 못한다는 것을 깨닫습니다. 그래서 K가 큰 경우에 사용할 수 있는 다른 풀이를 고안해냈는데, 이 역시 모든 K에 대해 구성할 수 있는 풀이는 아니라는 생각이 들어 방향성을 바꾸기로 합니다. 그러다가 맨 처음에 생각하던 사이클 구조 (빙글빙글 돌면서 긴 거리를 이동하게 만듦)가 꽤 유효하다는 생각이 들었고, 그래서 1부터 N에 순서대로 이동하는 사이클을 만들어 문제에서 주어진 K값에 맞춰지도록 이진 트리의 탐색 결과가 실제 도달해야 하는 값에서 x칸 밀리도록 만들었습니다.
처음에 사소한 실수를 해서 1WA를 쌓았지만, 두 번째에 AC를 받았습니다.
[2:43 - 2:55?] D. Mobilint Tensor Scheduling (ARIES)
그 다음으로 스코어보드에서 많이 풀린 문제가 D라서 D를 읽었습니다. 분명히 트리 dp 같긴 한데 어떤 순서로 메모리를 바꾸는 게 이득인지 잘 감이 오지 않았습니다. 그러다가 문제를 풀다가 도중에 갑자기 K번 문제의 지문에 적힌 제한과 실제 데이터의 제한이 다르다는 공지가 떠서 K번을 열어 봤습니다. K번도 D번과 비슷한 개수의 솔브 수가 있었기 때문에 K번을 풀까 고민하다가 D번이 전혀 모르겠어서 K번을 생각해보기로 넘어갑니다.
[2:55? - 4:30] K. Storing Roll Cake 1WA
문제를 읽고 조금 고민해보니 자르는 순서와 관계없이 자르는 비용이 일정하다는 것을 관찰했고, O(NK)에 해당하는 dp식이 쉽게 r구해졌습니다. 얼핏 보아하니 CHT를 쓰면 O(N)이나 O(N log N)에 풀 수 있을까 생각해서 cht를 짰는데, K 범위 제한 때문에 제가 아는 기본 CHT로 풀리지 않는다는 사실을 깨달았습니다.
그래서 CHT에 대해 여러 블로그를 검색해보다가 결국 풀지 못했습니다. 중간에 그럴듯한 가설을 세우고 그것대로 구현해서 CHT를 제출했는데 장렬하게 WA를 받으면서 풀지 못했습니다. 그리고 마지막에 D번에 아래와 같은 제출을 하나 하고 대회를 마무리했습니다.
스코어보드 프리즈 이후로 추가로 푼 문제가 없어서 프리즈 전 17? 18등이라 많이 내려가서 25위 근처일 것이라고 생각했습니다. 그런데 의외로 저뿐만 아니라 다른 분들에게도 문제 셋이 어려웠는지 20등으로 마무리하면서 기가 막히게 네이버페이 2만원을 커트라인에 걸쳐서 사수해냈습니다!
그리고 대회가 끝난 뒤 SCSC 뒷풀이에 참여하지는 않았지만 경곽 학생들(mj1000j, swlee0202, shijun2009)과 lunarlity, dadas08까지 총 여섯 명이서 BBQ에서 치킨을 먹었습니다. 꽤 저렴한 가격에 맛있게 먹은 듯합니다.
그리고 SCSC div.1을 우승한 dadas08이 프리즈 이후에 다이아 4문제를 슥슥하면서 풀었다길래 mj1000j가 그 비결을 물어봤는데 자꾸 Chinese Bronze라고만 주장해서 슬픕니다. 저에게는 Korean Diamond였는데 말입니다.
이런 문제를 슥슥할 수 있게 더 다양한 자료구조와 다이아 알고리즘을 공부해야 할 것 같습니다.
'PS' 카테고리의 다른 글
| DOJ - KOI 2nd Round Mock 1 High 후기 (1) | 2026.06.05 |
|---|---|
| 2026 Kaist Run Spring Contest 후기 (1) | 2026.05.05 |
| PS 문자열 알고리즘 - 8. 1D Trie 구현 (4) | 2025.08.13 |
| PS 문자열 알고리즘 - 7. 접미사 배열과 lcp 배열 응용 (0) | 2025.08.12 |
| PS 문자열 알고리즘 - 6. 접미사 배열과 lcp 배열 (0) | 2025.08.12 |