2025 SCSC 대회 Div.3 리뷰

 

 

 

알고리즘 공부를 다시 하는 김에 오랜만에 ps대회에 나가봤다. scsc에 있던 작년에는 일정이 겹쳐 못 나갔었는데, 이번에는 잊고 있었다가 친구가 알려줘서 나갈 수 있었다. Div 1,2,3을 모두 지원했는데 Div.3를 배정받았다. 가장 낮은 디비전이라서 상위권을 목표로 했는데, 운좋게 우승까지 하게 되었다. 생각했던 것보다도 확실히 초보자분들이 많으신 것 같아서(중고등학생들도 있는 듯) 동기부여 정도로 생각하고, 내년에는 Div.2 10위권 정도를 목표로 하려고 한다. 그래도 상품으로 버즈3를 받아서 기분은 좋다.

 

이번에 그래프 알고리즘을 열심히 정리해서 골드 문제로 dp나 그래프가 나오면 꼭 풀어야겠다고 생각했는데, 골드 세 문제가 모두 ad_hoc이라 좀 난감했다. 오랜만의 오프라인 대회라 첨에는 많이 긴장해서 C, D에서 삽질을 많이 했다. H 아이디어가 끝나기 직전에 떠올라서 시간 단축을 했으면 풀만하지 않았나 싶다.

 

 

B. 주사위 피라미드

구현도 간단하겠다 싶어서 1~N층별로 면이 5, 4, 3, 2, 1개 보이는 주사위들의 수를 구해서 일일이 합치는 방식으로 했는데, 훨씬 간단한 풀이가 있었다.

최댓값 피라미드의 경우를 먼저 생각해 보자. 면이 1개 보이는 주사위의 눈은 (6)일 것이다. 2개의 면이 보인다면 (6, 5)가 보인다. 3개의 면이 보인다면 (6, 5, 4)가 보인다. 이런 식으로 눈의 합이 최대가 되도록 만들 수 있는데, 반대로 최솟값 피라미드는 면이 1개 보인다면 (1), 2개가 보인다면 (1, 2), 3개가 보인다면 (1, 2, 3), ... 이러한 규칙성이 나타나게 된다. 따라서 두 피라미드를 합쳐서 생각하면 (보이는 면의 수)x7이 답이 됨을 알 수 있다. 보이는 면의 수를 다섯 방향에서 사영시켜 생각하면 $\frac{35n(n+1)}{2}$가 답이다.

 

 

D. 물과 응애

처음에 문제를 대충 읽어서 스택인 줄 알고 삽질을 좀 했다. 일단 문자열의 처음부터 H와 O의 개수를 세서, H>=O이어야 한다는 것 까지는 진행했는데, O가 전부 나오고 나서의 조건을 어떻게 처리해야 할지 못 찾아서 고민을 많이 했다. 요구하는 문자열이 대칭이므로, 끝에서부터 거꾸로 한번 더 검사하면 된다. 개인적으로는 발상이 힘들었는데 그냥 문제 경험 부족인 듯 하다.

 

 

E. $K$-POP

우선 $a\times b=K$이면서 $a+b$가 최소인 $(a, b)$는 $O(\sqrt{K})$에 간단하게 찾을 수 있다. 구성 문제이므로 최대한 보편적으로 적용될 수 있는 방법을 떠올리면 되는데, 일단 $a, b$ 중 더 큰 수를 리프가 아닌 노드의 수로 하는 것이 좋다고 생각했다. 그리고 나서 예제에서 영감을 받아, 한 쪽으로 기울어진 이진 트리를 만들면 리프 노드 수와 리프가 아닌 노드의 수를 유연하게 조절할 수 있음을 확인했다. 이런 발상을 어떻게 빨리 하는지 모르겠다...

K = int(input())

import math
i = int(math.sqrt(K))
while i > 0:
    if K%i == 0: break
    i -= 1

print(i + K//i)
nonleaf = K//i
leaf = i
n = 2
while nonleaf > 0:
    print(n-1, n)
    n += 1
    nonleaf -= 1

leaf -= 1
t = 1
while leaf > 0:
    print(t, n)
    t += 1
    n += 1
    leaf -= 1

 

 

G. Sorting Replay at Jane Street

마지막 unstable sort 이후의 쿼리만 확인하면 됨을 빠르게 파악했다. unstable sort하게 되면 해당 인덱스($i_0$)의 값이 다르면 순서가 고정되고, 같은 배열끼리는 순서가 섞이게 된다. 남은 쿼리들은 stable sort들인데, stable sort하는 인덱스들($i_1, \cdots, i_n)$의 값이 하나라도 다른 배열들끼리는 순서가 고정된다. 즉 $(A[i_0], A[i_1], \cdots, A[i_n])$가 같은 배열 $k$개끼리만 순서가 섞이게 되고, 그 경우의 수는 $k!$가 된다.

따라서, 마지막 unstable sort을 포함한 이후 쿼리의 인덱스들을 저장해 두었다가, 배열들에서 해당 인덱스들의 값들만 뽑아 Counter에 넣어 주는 방식으로 $O(Q+N^2)$ 정도만에 처리가 가능하다. lazy update하는 쿼리 문제가 친숙해서 풀만했던 것 같다. 재귀를 이용해서 마지막 쿼리부터 처리하는 다른 방법도 있다고 한다.

 

stable_list = set()
for i in range(Q-1, -1, -1):
    stable_list.add(query[i][1]-1)
    if query[i][0] == 1: break

stable_list = sorted(list(stable_list))

bag = Counter()
for i in range(N):
    l = list()
    for t in stable_list: l.append(A[i][t])
    l = tuple(l)
    bag[l] += 1

res = 1
for value in bag.values():
    for m in range(1, value+1):
        res *= m
        res %= 998244353

print(res)

 

 

아래는 현장에서 못 풀어서 업솔빙한 문제들이다.

F. 현대모비스 V2X 자율주행 2

조금 생각해 보면, $k(k \neq N)$번째까지 R(또는 U)의 개수가 서로 같지 않도록 만들어 주어야 한다는 것을 알 수 있다. 따라서 R은 1, U는 0으로 처리해서 누적 합을 검사하는 알고리즘을 생각해 볼 수 있다. 두 배열의 누적합을 비교해서 더 큰 값을 $sum_{max}$, 더 작은 값을 $sum_{min}$이라 할 때, 두 값의 차이가 많이 벌어질수록 좋다고 볼 수 있다.

따라서 greedy하게 경로를 최소로 변경하려면 $sum_{max}$를 만드는 배열 $l_{max}$에서 0과 가장 뒤에 있는 1을 교환하거나, $sum_{min}$을 만드는 배열 $l_{min}$에서 1과 가장 뒤에 있는 0을 교환하면 된다. 각 행위를 max_update, min_update라 하면 다음과 같이 해결할 수 있다.

 

1. $sum_{max} < sum_{min}$이라면, update를 둘 다 진행해야 한다.

2. $sum_{max} = sum_{min}$이라면

2-1. $l_{max}[i] = l_{min}[i] = 0$이면 max_update를 진행한다.

2-2. $l_{max}[i] = l_{min}[i] = 1$이면 min_update를 진행한다.

2-3. $l_{max}[i]=0, l_{min}[i]=1$이면 더 뒤쪽의 index와 교환하는 update를 선택한다.

 

수학적으로 좀 더 깔끔하게 푸는 방법도 있는 것 같은데, 머리를 더 쓰기 싫어서 그냥 이렇게 풀었다.

def solve(l_max, l_min):
    l_max_1 = list()
    l_min_0 = list()
    for i in range(2*N):
        if l_max[i] == 1: l_max_1.append(i)
        if l_min[i] == 0: l_min_0.append(i)
    
    sum_max = sum_min = 0
    res = 0

    def _max_update():
        nonlocal sum_max
        l_max[i] = 1
        l_max[l_max_1.pop()] = 0
        sum_max += 1
    
    def _min_update():
        nonlocal sum_min
        l_min[i] = 0
        l_min[l_min_0.pop()] = 1
        sum_min -= 1
    
    for i in range(2*N):
        sum_max += l_max[i]
        sum_min += l_min[i]
        
        if sum_max < sum_min:
            res += 2
            _max_update()
            _min_update()
            
        elif sum_max == sum_min and i != 2*N-1:
            res += 1
            if l_max[i] == l_min[i] == 0: _max_update()
            elif l_max[i] == l_min[i] == 1: _min_update()
            else:
                if l_max_1[-1] > l_min_0[-1]: _max_update()
                else: _min_update()
    return res

 

 

 

H. SCSC 문자열 놀이

$N=\sum_{i=0}^{M-1}{(S\;or\;C)2^i}$임은 쉽게 알 수 있다. $N$의 제한을 보았을 때 문자열의 자릿수 $M$은 최대 40 정도가 된다. 따라서 재귀를 이용해서 구성할 수 있는데, k자리 문자열이 가질 수 있는 최댓값은 $\max(S,C)\times(2^k-1)$임을 이용해 가짓수를 많이 줄일 수 있다고 생각했다. 에디토리얼을 보면 수학적으로 잘 증명해 놓았다.

 

문제는 $S=C$일 경우, 가짓수를 줄일 수 없어 위와 같은 방법을 이용하기 어렵다. 따라서 'S 또는 C로 구성된 $M$자리 문자열 중 SCSC가 포함된 문자열의 개수'라는 새로운 문제를 풀어야 한다. 그냥 dp로 풀려니 중복제거가 힘들어서 $2^M$에서 SCSC를 포함하지 않는 문자열의 개수를 빼 주기로 했다. 문자열의 연속된 3자리 $\left\{ SSS, SSC, \cdots , CCC \right\}$를 갖는 문자열의 개수를 더해가면서 2차원 dp를 돌리면 된다.

if S != C:
    pattern = "SCSC"
    if S < C: 
        S, C = C, S
        pattern = "CSCS"

    res = set()
    def solve(n, now, start, history):
        global res
        if now < 0:
            if n == 0 and pattern in history:
                res.add(history)
            return

        if 0 <= n - C*(2**now) <= S*(2**now-1):
            solve(n - C*(2**now), now-1, True, history+"C")
        if 0 <= n - S*(2**now) <= S*(2**now-1):
            solve(n - S*(2**now), now-1, True, history+"S")
        if not start:
            solve(n, now-1, False, "")
        return

    solve(N, 40, False, "")
    print(len(res))

else:
    t = -1
    for i in range(4, 40):
        if 2**i - 1 == N//S:
            t = i
            break

    if N%S != 0 or t == -1: print("0")
    else:
        # SSS, SSC, SCS, CSS, SCC, <CSC>, CCS, CCC
        dp = [[0]*8 for _ in range(t)]
        for i in range(8): dp[0][i] = 1
        for i in range(t-3):
            dp[i+1][0] = dp[i][0] + dp[i][3]
            dp[i+1][1] = dp[i][0] + dp[i][3]
            dp[i+1][2] = dp[i][1] + dp[i][5]
            dp[i+1][3] = dp[i][2] + dp[i][6]
            dp[i+1][4] = dp[i][1] + dp[i][5]
            dp[i+1][5] = dp[i][6]
            dp[i+1][6] = dp[i][4] + dp[i][7]
            dp[i+1][7] = dp[i][4] + dp[i][7]

        print(2**t - sum(dp[t-3]))