2026 SCSC 대회 Div.2 리뷰

 

 

 

올해는 div2로 쫓겨났고 40등을 했다. 스코어보드 프리즈 전에 이미 6솔브가 33등 언저리길래 망했다고 생각했는데 간신히 수상권 막차를 탔다. 작년 div2에 비해서는 난이도가 꽤 내려간 느낌이었고 그래서 7솔을 했었어야 했는데, 집중이 잘 안돼서 삽질을 많이 한 점이 아쉽다.

 

역시나 올해도 애드혹 or 그리디 위주의 구성이었다. 풀 만한 문제들 중에 올해 초에 열심히 공부한 그래프 알고리즘이나 dp 문제가 하나는 있을 줄 알았는데, 놀랍게도 하나도 없었다...

 

https://atcoder.jp/contests/scpc2026-div2

SCPC 2026 Div.2 - AtCoder

 

 

A. Mobilint 텐서 스케쥴링 (REGULUS)

A번치고는 문제가 좀 복잡해서 급하게 읽느라 $w_i=1$임을 놓쳤고, 그래서 그리디라고 가정하고 한땀한땀 구현해서 풀었다... 느낌상 다른 div에 심화 문제가 있을 것 같긴 하지만, 그래도 왜 굳이 입력을 받도록 문제를 냈을까 싶긴 하다. 암튼 저 조건이 있으면 부모 노드로 올라가는 순간 절대 최댓값을 넘어서지 못하기 때문에 (리프노드 수)+1이 정답이다.

 

 

C. 재배열

수열 $A$를 재배열해서 연속 부분 수열 $B$가 최대한 많이 등장하도록 하는 문제인데, $B$가 계속 등장하도록 이어붙인 다음 나머지들은 아무렇게나 배열하면 된다는 발상은 쉽게 할 수 있다. 이때 kmp의 fail함수를 구해 주면, $B$의 prefix와 suffix가 일치하는 최대 길이 $j$를 찾을 수 있다(Z algorithm으로도 가능하다). $B$에다 $B[j:]$를 계속 이어붙이면 답이 된다. naive하게 이어붙이니까 TLE가 나길래, $A$를 Counter에 넣어서 얼마나 이어붙일 수 있는지를 계산한 다음에 나머지를 붙이는 방식으로 했다.

 

 

D. 색칠 놀이

구간 쿼리 $[l, r]$이 들어올 때 해당 구간에서 연속된 색이 없도록 덧칠하는 횟수의 최솟값을 구하는 문제다. 색이 안 칠해져 있는 경우, 무시해도 된다는 것은 빠르게 파악했다. 결국 구간 내 연속된 색의 길이를 $a_1, \cdots, a_k$라 할 때, $\sum \left\lfloor \frac{a_i}{2} \right\rfloor$를 구해 주면 되는 문제라고 볼 수 있다. 보자마자 세그먼트 트리가 생각났지만 세그먼트 트리로는 생각보다 풀기 어렵고, 업데이트가 없기 때문에 누적합을 떠올렸다.

 

배열 전체에서 연속된 구간 각각에 대해 $\left\lfloor \frac{a_i}{2} \right\rfloor$을 구해 주고 누적합 배열을 만들어 준다. 이 방식으로 중간 구간들은 처리할 수 있고, 양 끝에 걸리는 구간들만 잘 처리해 주면 된다. 이분 탐색으로 $l$과 $r$에 걸리는 구간을 구할 수도 있겠지만, 미리 구간의 시작점과 끝점을 저장해 두는 배열을 만들어서 전처리해 두면 편하다. 이 생각을 못해서 엄청 창의적으로 풀었는데, 인덱스도 대충대충 정하고 해서 6번 틀린 끝에 AC를 받았다. 구현력을 좀 더 길러야겠다는 생각을 들게 하는 문제다.

 

 

F. 오름차순으로 정렬했을 때 K번째 수

A에서 도망쳐 와서 처음으로 푼 문제다. 집중을 안하고 문제를 읽으니까 이해하는 데에만 5분은 걸렸던 것 같다. 한 3번 정도 해 보면 규칙성을 찾을 수 있다. $a_{N+2}$를 찾는 경우 $a_1$이 빠지고 $a_{N+1}$이 들어가야 하는데, $a_1 > a_{N+1}$인 경우 어차피 $K$번째 수는 바뀌지 않고, $a_1 < a_{N+1}$이더라도 인덱스가 1 작아지는 대신 똑같은 값이 들어가므로 $a_{N+2} := a_{N+1}$임을 쉽게 증명할 수 있다. 

 

 

G. SCSC 게임

제작년 쯤에도 scpc에 게임 이론 문제가 나왔던 것으로 기억하는데, 그때는 2차원 dp였다. 근데 이번에는 양 끝에서부터 지우는 것이 아니라 임의로 하나를 골라서 지우는 것이기 때문에 dp를 쓸 수가 없다. 여기서부터 고민을 상당히 많이 했다. $S$가 꽤 크고 솔브 수가 많은 걸로 봐서 간단한 방법이 있겠다고 생각했다. SCSC를 완성시킬 수 있으면 완성시키면 되는데, 내 턴에 완성시킬 수 없는 경우 마지막 글자를 떼는 방식으로 상대에게 턴을 넘겨줄 수 있을 것 같았다. 그럼 상대도 동일한 전략을 구사할 것이므로, 결과적으로 문자열의 길이에 따른 홀짝성으로 문제가 풀린다.

 

 

J. DETOX

첫 번째에 손을 들지 않는 경우가 OX_OX거나 XO_XO밖에 없음을 먼저 확인했다. 두 경우 모두에서, 자신($i$)이 O/X 어떤 기호를 가지고 있든 $i-1$나 $i+1$번째 사람 중 한 명은 손을 들게 되어 있다. 어떤 사람이 손을 들었느냐에 따라서 자신의 기호를 확정지을 수 있다. 따라서 첫 번째에 손을 들지 않는 경우, 무조건 두 번째에 손을 들게 된다. 이번 대회에서는 제일 재밌는 문제였다.

 

 

---

 

 

이하는 업솔빙한 문제들이다.

H. CUBRID HA Load Balance

이상하리만치 현장에서 인기가 없었던 문제다. 이미 초반 2시간을 날려먹었던 나는 이 문제가 상위권에서도 얼마 안 풀린 것을 보고 플 상위 정도의 난이도겠거니 짐작하고 넘겨버렸다.. 시간을 5분 남기고서야 지문을 보고 그렇게 어렵지 않은 그리디임을 직감했다. 남은 시간을 E 대신 H에 올인했다면 충분히 풀만 했을 것 같다.

 

일단 서버의 번호가 그렇게 중요하지 않다는 생각이 들었고, 그러다 보니 그리디를 적용할 수 있을 것 같았다. 왜냐하면, 최대로 필요한 master 서버의 수가 $a$개이고, slave 서버의 수가 $b$개라면, 처음부터 $a, b$개의 서버를 적절히 지정하여 모든 쿼리를 처리 가능하도록 만들 수 있기 때문이다. 다만 중간에 master 서버가 없으면 한 slave 서버가 master 서버로 강제로 바뀐다는 점이 걸렸다. 즉 쿼리를 원래 순서대로 처리하는 경우 master 서버 개수가 최적이 아닐 수 있다. 하지만 쿼리를 역순으로 처리하게 되면, 최소 master 개수가 1이라는 조건을 두고 각 순간의 master와 slave의 하한을 갱신하는 방식으로 풀 수 있다. 두 서버 모두로 처리 가능한 요청은, 굳이 서버를 결정할 필요가 없으므로 추가로 필요한 서버 개수의 최솟값만 가져와서 최종 답에 반영해 주면 된다.

 

from collections import Counter
c = Counter()
for q in query:
    if q[0]==1: c[q[1]] += 1

avail = N - len(c)
max_m = 1
max_s = 0
val = True
res = 0
for q in query[::-1]:
    if q[0]==1:
        c[q[1]] -= 1
        if c[q[1]] <= 0: avail += 1
    
    else:
        if q[1]==0 and q[2]==0 and q[3]==0:
            continue
        max_m = max(max_m, q[1])
        max_s = max(max_s, q[3])
        add = max(0, q[1]+q[2]+q[3]-(max_m + max_s))
        
        if max_m + max_s + add > avail:
            print(-1)
            val = False
            break

        res = max(res, max_m+max_s+add)

if val: print(res)

 

 

L. 채널톡 워크플로우

시간만 있었으면 시도해볼 만한 좋은 구성적 문제다. 시작 아이디어는 일단 들어가자마자 $x=i$라 종료되어 버리는 경우는 막아야 하므로 $N+1$번 이상의 모듈들을 사용해 트리 내부를 구성해야 된다는 것이고, 그러면 깊이(여기서는 노드 개수로 정의하자)가 일정한 포화 이진 트리를 만들면 좋겠다는 생각을 하게 된다. $N=1000$인 경우에도 2047개의 모듈을 사용해 깊이 11짜리 트리를 만들 수 있으므로 정해라는 확신을 갖고 갈 수 있다. 트리의 깊이보다 $K$가 작다면, 1~N까지 모든 수를 구분하는 것이 불가능하다.

 

문제는 트리의 깊이보다 $K$가 큰 경우이다. 모든 리프 노드에 도달하는 시간을 $K-depth$만큼 지연시켜야 한다. 이때 놀라운 아이디어가 있다. $F_i=0$으로 설정해 분기를 없앨 수가 있는데, 모든 리프 노드의 분기를 없애고 바로 옆의 노드로 연결시켜 사이클을 만들어 준다. 그리고 리프 노드 직전에서, 원래 도달해야 되는 리프 노드의 $K-depth$ 이전 노드로 보내 주면 된다. $F_i \leq N$이라는 조건이 있어서 디버깅할 때 애를 많이 먹었다.

 

n = 2**ceil(log2(N))
D = int(log2(n)) + 1

if K < D: print(-1)
else:
    r = K - D

    node = n
    F = [0]*2048
    L = [0]*2048
    G = [0]*2048
    def build(s, e):
        if s==e:
            k = s-r if k>=1 else n+s-r
            return k
        
        if s == 1 and e == n:
            node_now = 0
        else:
            global node
            node += 1
            node_now = node

        m = (s+e)//2
        F[node_now] = min(N, m)
        L[node_now] = build(s, m)
        G[node_now] = build(m+1, e)
        return node_now
    
    build(1, n)

    for i in range(1, n+1):
        G[i] = i%n+1

    print(node+1)
    for i in range(node+1):
        print(F[i], L[i], G[i])