Codeforces Round #809 (Div. 2) A

B에서 멸망했지만, 빡집중해서 D까지 뚫었다. B만 제때 풀었어도 퍼포 많이 높았을 텐데 아쉽다.

망하면 벨로그 작성을 미루는 습관을 버려야겠다.. 코포한 다음 날 벨로그 작성하는 습관을 들여야겠다..

A. Another String Minimization Problem

쿼리 $n$개가 주어진다. 문자 $B$가 $m$개로 구성된 문자열이 주어진다. 각 쿼리에 대해 다음의 작업을 실행해서 주어진 문자열을 사전 순으로 가장 앞서게 만들어라.

쿼리 $a_i$에 대해, 문자열의 $a_i$번째나 $(m+1-a_i)$번째 문자를 문자$A$로 바꾼다.

풀이

각 쿼리에 대해 앞에서부터 $A$로 채워주면 된다.

코드

def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    ans = ['B']*(m+1)
    
    for x in a:
        i, j = x, m-x+1
        if i > j:
            i, j = j, i
        if ans[i]=='A': ans[j] = 'A'
        else: ans[i] = 'A'
            
    print(''.join(ans[1:]))
    
 
for __ in range(int(input())):
    solve()

B. Making Towers

숫자 n개가 입력된다. 이 숫자들은 타워의 종류를 나타낸다. 타워를 바닥에서부터 쌓을 건데, 입력된 순서대로 타워를 깔아야 한다. 타워는 위쪽 또는 왼쪽, 오른쪽에 설치할 수 있다. 각각의 타워 종류에 대해서 수직으로 쌓인 연속된 길이의 최댓값을 각각 구해라.

input : 1 2 3 1 2 3 1

풀이

그리디를 이용한 O(N)

그림을 관찰해보면, 동일한 타워를 위에 쌓으려면 두 타워의 거리 차가 홀수여야 한다.

타워 종류 별로 위치를 순서대로 저장한다. 각 타워 별로 저장된 위치를 순차적으로 탐색해주면서 가장 긴 홀수 차 수열을 구하면 된다.

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    idx = [[] for __ in range(n+1)]
    for i in range(n):
        idx[a[i]].append(i+1)
    
    ans = [0]*(n+1)
    
    for i in range(1, n+1):
        if not idx[i]:
            continue
        cnt = 1
        now = idx[i][0]&1
        for x in idx[i][1:]:
            if now&1 != x&1:
                now = not now
                cnt += 1
        ans[i] = cnt
        
    print(*ans[1:])


for __ in range(int(input())):
    solve()

풀이

DP를 이용한 O(N)

위와 풀이는 똑같다. 코드만 더 간결하다.

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[0]*2 for __ in range(n+1)]
    
    for i in range(n):
        x = a[i]
        dp[x][i&1] = max(dp[x][i&1], dp[x][not(i&1)]+1)
        
    for i in range(1, n+1):
        print(max(dp[i]), end=' ')
    print()


for __ in range(int(input())):
    solve()

C. Qpwoeirut And The City

풀이

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    if n%2:  
        ans = 0
        for i in range(1, n-1, 2):
            mx = max(a[i-1], a[i+1])
            if mx < a[i]:
                continue
            ans += mx+1-a[i]
        print(ans)
    else:
        dp = [[0]*2 for __ in range(n+3)]
        
        for i in range(1, n-1):
            mx = max(a[i-1], a[i+1])
            if mx < a[i]:
                dp[i][0] = dp[i-2][0]
                dp[i][1] = min(dp[i-3][0], dp[i-2][1])
            else:
                dp[i][0] = dp[i-2][0]+mx+1-a[i]
                dp[i][1] = min(dp[i-3][0], dp[i-2][1])+mx+1-a[i]

        ans = min(dp[n-2])
        if n >= 4:
            ans = min(ans, dp[n-3][0])
        print(ans)            

 
for __ in range(int(input())):
    solve()