2025 SCSC 프로그래밍 경시대회 후기

개요

교내 대회를 제외한다면, 여태까지 경시대회는 온라인으로만 참여하였지만(작년 초반에 열린 솔브드 그랜드 아레나를 온사이트로 참가하고 싶었으나, 그걸 알아차린 시점에 신청 기간이 마감되었다는게 아쉬울 따름이었다.), 이번에는 처음으로 온사이트에서 대회를 참가하게 되었다.
사실 2025 SCSC가 개최되는 그 주에 졸업 작품 중간 발표가 겹쳐 있어 신청을 살짝 고민했었는데, 나름 중간 발표를 잘 마무리하고 나니 여유롭게 참여할 수 있게 되었다. 프로그래밍 대회 특유의 분위기는 처음 접하게 되는 것이었기 때문에, 어떤 사람들을 만나고, 대회의 시작과 끝은 어떤 흐름으로 진행될까 궁금하고 기대되었었다.

대회 당일, 여름의 시작을 알리는 화창한 날씨와 함께 직통 좌석버스를 타고 서울대학교 정문으로 향했다. 정문 앞에서 자연과학대까지 가는 것은 역시나 버스를 이용하는 것이었다. 관악캠퍼스가 매우 크다는 것은 이루 잘 알려진 사실이다. 만약에 개최 위치가 공학동이었으면 구름에 엄청 가까워졌을 것이라고 상상했었다.
비교적으로 늦게 집에서 출발하여 도착하고 되는 대로 끼니를 때우자고 했는데, 막상 도착해 보니 편의점 마저도 갈 수 없어 어쩔 수 없이 공복인 상태로 아이스 아메리카노와 함께 시작하게 되었다. 정말 고맙게도 주최측에서 간식을 많이 주셔서 잘 버틸 수 있었다.

대형 강의동에서 마주친 것은 매우 넓은 2층짜리 칠판 ... 자연과학대에서 쓰이는 수많은 공식의 증명들이 쓰여지기엔 이정도 크기의 칠판은 되어야 하는구나 라고 생각했다. 단층 강의실만 접한 나로썬 다소 신기한 광경이었다.

내가 참여했던 Division 2 대회에서는 문제가 무려 10개나 나왔다. 코드포스를 할 때에는 6~7문제를 난이도 순서대로 풀어가는 경험에 익숙해져 있었는데, 문제 난이도도 랜덤이고, 중간에는 상위 플레와 다이아몬드가 섞여 있다는 점이 무서웠다... 스스로를 역시 묻어가는 사람이라고 생각하고 다른사람이 먼저 빨리 푼 문제를 뒤이어 풀기로 했다.

 

문제

2A. 주사위 피라미드 (17분, 18분, 20분)

문제를 보자마자 백준의 1041: 주사위(https://www.acmicpc.net/problem/1041)가 떠올랐다. 주사위가 피라미드 형태로 쌓여 올라간다는 점과 아랫면은 세지 않는다는 점이 이 문제의 난이도를 올려 준다. 1면 ~ 5면이 보이는 주사위의 수를 $n$과의 관계로 정의하고 해당 면의 개수에서 가장 많이(또는 가장 적게) 얻게 되는 점수를 각각 독립적으로 곱해 주어 이를 모두 더하면 된다.

그런데, 위에 말한 백준의 문제를 너무 의식한 나머지 최댓값과 최솟값을 더해야 한다는 점을 생각 못하다가 늦게나마 알아차리게 되었다. 이와 맞물려 살짝 식이 복잡한 나머지 주사위의 수를 구하는 식에서 자질구레한 실수를 하고 +2로 AC를 받게 되었다. 이해는 쉬웠지만 식을 구하는 과정이 다소 어려운 A번다운 문제였다.

이후에 풀이를 들어보는 중, 주사위의 면의 개수가 $n$에 대해 제곱으로 늘어난다는 점과 각 면에 곱하는 수가 상수라는 점을 이용해 $n$에 대한 이차식으로 상정하고 테스트 케이스+$\alpha$에 대해 라그랑주 보간법을 사용하여 그 식을 유추하였다는 사례를 듣고 감탄하였다.

 

2B. 물과 응애 (38분)

처음에는 스택을 활용하는 문제인 줄 알았으나, HOH가 연속으로 존재하지 않아도 제거할 수 있다는 점을 알아차려 접근의 방향을 빠르게 전환하였다.

어떤 위치에 O가 있다는 것은, 그 위치에서 양방향으로 '소진'할 H가 하나씩 있어야 한다는 것을 의미하고, 만약 그런 H가 소진되어 존재하지 않는다면 pure하지 않는다는 것이었다. 양 방향으로 문자열을 순차적으로 순회하며 H와 O의 개수를 저장하고, 만약 어떤 위치에서 O의 개수가 H의 개수를 역전할 땐 pure하지 않는다는 결과를 도출하는 방식으로 풀었다.

 

2I. $K$-POP (66분)

리프 노드가 아닌 노드의 수와 리프 노드의 수의 곱이 $K$라는 것은 두 수의 후보는 $K$의 약수이기 때문에 그 후보들을 브루트 포스 방식으로 확인하며 구하였다.

1에서 8까지의 $K$에 대해 나올 수 있는 트리의 형태를 파악해 보니 일관적으로 일자형 트리의 각 노드에 리프 노드를 임의로 추가한다는 것을 알아차릴 수 있었다. 그러면 (리프 노드가 아닌 노드의 수)$+1$ $\ge$ (리프 노드의 수)만 만족하면 이진 트리를 만들 수 있는 것이고 그 중에서 합이 가장 작은 경우를 선택하여, 그 노드의 수를 기반으로 위 형태의 이진 트리를 만들었다. 결과는 무난하게 AC.

 

2G. 현대모비스 V2X 자율주행 2 (139분, 142분)

주어진 입력으로 두 자율주행차량이 돌아다니는 격자 공간의 길이가 수십만으로 커질 수 있어 그 격자 공간에 대한 메모이제이션이 불가능해 보였다. 다행이도 자율주행차량이 갈 수 있는 방향은 오른쪽과 위쪽만이었기 때문에 문제를 많이 추상화할 기회를 찾았다.

만약 아래쪽 자율주행차량이 위로 이동함으로써 위쪽 경로와 겹치게 된다면, 경로를 오른쪽으로 수정해야 할 필요가 있다. 그리디하게 경로 중 처음에 위쪽으로 움직였던 방향과 마지막에 오른쪽으로 움직였던 방향을 서로 교환하면 그 사이의 경로가 모두 오른쪽 아래로 한칸 이동하니 가장 좋아 보인다.

자율주행차량의 경로가 겹치거나 그 후에 경로가 서로 반전되어 있을 때 한쪽 자율주행차량의 경로를 오른쪽 아래 방향으로 몇칸 이동해야 겹치지 않게 되는지 그 최솟값을 구하면 된다.

단, 반례가 하나 있다. 출발할 때와 도착할 때의 두 자율주행차량의 방향이 모두 오른쪽이거나 위쪽이면 아무리 한쪽 경로를 오른쪽 아래로 이동한다고 해도 경로가 겹치므로 반대쪽 경로를 적어도 한번 수정해야한다. 이미 수정 횟수가 두 번 이상인 경우에는 횟수의 반을 반대쪽 자율주행차량의 경로를 왼쪽 위 방향으로 수정하는 것으로 치환할 수 있기 때문에 해당 사항은 아니다.

대회 당시에 종이에 지그재그를 그려 가며 케이스를 탐구하던 것이 떠오른다. 직감으로 시작해 무작정 고안해낸 것이 정답었다는 것도 사실 신기할 따름이었다. 만약 자율주행차량이 오른쪽과 위쪽뿐만 아니라 왼쪽과 아래쪽도 움직일 수 있었다면 풀이 방식이 어떻게 달라졌을까 ...

 

2F. Sorting Replay at Jane Street (222분, 237분, 238분)

풀다가 시간이 끝나서 +3인 채로 아쉽게 종료한 문제였다. 처음에는 명확한 방법을 찾지 못하고 헤맸는데, 불안정 정렬을 수행하고 나서 안정 정렬을 수행하면 안정 정렬의 기준값이 같은 구간에서 무작위 순서가 존재할 가능성이 있음을 추측하였다.

불안정 정렬을 사용했을 때 기준값이 같은 구간은 무작위지만, 기준값이 다른 구간끼리는 위계가 발생한다. 그 이후에 안정 정렬을 수행한다고 하면 기준값이 같은 구간 내에서 이전 불안정 정렬에 대한 기준값이 같을 수도 있고, 서로 다를 수도 있을 것이다. 만약에 같다면 순서는 서로 여전히 무작위일 것이고, 다르면 위계는 지켜질 것이다.

쿼리 중 마지막 불안정 정렬을 수행하고 나서 이후의 안정 정렬을 수행하였을 때, 여전히 위계가 존재하지 않는 연속적인 구간에 $n!$의 경우의 수가 있어 이를 모두 곱해주면 정답이 아닐까 생각하고 있다.

돌아보니 구현할 때 정렬하는 과정이 있었는데 수열을 역으로 매핑하는 것을 까먹고 안했던것 같다 ... 그럼에도 예제 테스트 케이스 결과가 이상하리만치 잘 나오니까 오히려 방심했었나 싶다.

 

후기

처음 참가하는 것이라 참가에만 의의를 두자고 생각했는데, 26등이라는 나름 좋은 성적을 냈다. 5등상으로 문화상품권까지 타가니 뿌듯한 느낌은 배가 되었다. 한편, 그러면서도 대회 중에 겪었던 다양한 실수는 큰 배움이 되어 주었다.

대회가 끝나고 프리징 된 스코어 보드를 해동해가며 순위가 극적으로 바뀌는 환호섞인 과정은 온사이트 프로그래밍 대회의 진미였다. 아직 쳐다보지도 못했던 상위 문제들의 에디토리얼을 출제자들이 빠르게 해설하는 부분 또한 그렇다. Division 1 대회에만 있었던 '관악산 정상에는 구름이 없다' 문제는 다이아 기하학 문제라고 하니 집에 가서 시간을 내며 풀어보고 싶은 마음이 가득하다.

대회 때 사용했던 닉네임은 'Dot_Product_친밀감'인데, 내적친밀감을 이용한 개드립이었다 ... 다른 참가자들의 재치 가득한 닉네임을 보니 다음에는 더 어그로가 높은(?) 닉네임을 준비해야겠다고 생각했다.