Codeforces Round #800 (Div. 2) ABC

[3번째 Contest]

2솔.. ㅋㅋㅋㅋ 그레이 퍼포 ㅋㅋㅋㅋ 개같이 멸망
코포 오랜만에 해서 감 떨어졌다.

A. Creep

길이가 n인 0과 1로 구성된 문자열 binary string이 주어진다. binary string의 점수는 문자열을 구성하고 있는 0과 1의 갯수의 차이다. binary string의 creepiness는 binary string의 모든 접두사의 점수의 최댓값이다.
우리가 구해야 하는 건, 0 a개와 1 b개를 적절히 조합해서 creepiness가 최소인 binary string을 만드는 거다.

풀이

사용가능한 0과 1의 갯수는 a, b개이다. 문제 조건을 만족하는 binary string을 만들기 위해, 0과 1을 번갈아가면서 붙이고 남은 숫자가 있다면 뒤에 이어붙여주면 된다.

그리디의 정당성 증명은 다음과 같다. creepiness의 최솟값은 abs(a-b)이다. binary string의 prefix 중 가장 긴 prefix는 binary string 그 자체이다. 이 경우, prefix의 number abs(a-b)이다. 모든 prefix의 number은 항상 abs(a-b) 보다 크거나 같다. 따라서 creepiness가 abs(a-b)가 되도록 binary string을 만들어야 한다. 그러려면 0과 1을 번갈아가면서 배치해야 하고 그 결과 prefix의 number가 0과 1로 진동을 한다.

코드

def solve():
    a, b = map(int, input().split())
    ans = '01'*min(a,b)
    if b>a:
        ans += '1'*(b-a)
    else:
        ans += '0'*(a-b)
    print(ans)

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

B. Paranoid String

길이가 n인 문자열 s가 주어진다. s는 0과 1로 구성되어 있다. s의 아무 substring을 골라서 아래 작업을 통해서 길이가 1인 문자열로 만드는 게 목표이다.

1번째 작업: 문자열 속 01을 1로 바꾼다.
2번째 작업: 문자열 속 10을 0으로 바꾼다.

작업을 무수히 실행하여 길이가 1인 문자열로 만들 수 있는 substring의 갯수를 구하라.

풀이

특정 문자열의 접미사가 '01' 또는 '10' 이면 접두사로 어떤 문자열이 오든 길이가 1인 문자열로 만들 수 있다. 그 외의 경우엔 만들 수 없다. 몇개 끄적여보면 답 나오는 간단한 문제로 패스.

코드

def solve():
    n = int(input())
    s = input()
    ans = 1
    for i in range(1, n):
        t = s[i-1:i+1]
        if t == '01' or t=='10':
            ans += i+1
        else:
            ans += 1
    print(ans)
 
 
for __ in range(int(input())):
    solve()

C. Directional Increase

길이가 n인 배열이 주어진다. 이 배열은 우리가 만들어야 하는 최종 배열이다.
우리는 최초에 길이가 n이고 모든 원소가 0으로 초기화된 배열을 갖는다. 다음 작업을 실행해서 최종 배열을 만들 수 있는지 결정해야 한다. 최초에 포인터는 첫번째 원소를 가르키고 있다.

1번 작업: 현재 위치의 값을 1 증가시키고 포인터를 오른쪽으로 옮긴다.
2번 작업: 현재 위치의 값을 1 감소시키고 포인터를 왼쪽으로 옮긴다.

위 작업을 실행 횟수에 제한은 없고, 모든 작업이 끝난 뒤 포인터는 첫번째 원소에 위치해야 한다.

풀이

작업을 실행하고 난 결과 배열을 a라고 하자. $a_i$는 (1번 작업 실행 횟수) - (2번 작업 실행 횟수) 이다. 포인터는 첫번째 원소에서 시작하고 끝나기 때문에, $\sum_{k=1}^n a_i(1번 작업 실행 횟수) = \sum_{k=1}^n a_i(2번 작업 실행 횟수)$ 을 만족해야 한다. 즉, 최종 배열의 합이 0이 아니라면, 우리는 최종 배열을 만들 수 없다. 이게 첫번째 예외처리.

첫번째 원소부터 마지막 원소까지 차례대로 탐색하며 누적합을 구한다. 그 과정에서 누적합이 0보다 작아지면, 최종 배열을 만들 수 없다. 두번째 예외처리.

증명: 포인터는 첫번째 원소에서 출발해서 첫번째 원소에서 끝난다. 이걸 잘 생각해보자. 우리가 i번째 원소를 탐색하고 있다고 가정하자. 1번째 원소에서 i번째 원소까지 우리가 실행한 1번 작업 횟수를 x라고 두고, 2번 작업 횟수를 y라고 두자. 만들 수 있는 최종 배열이라면, $x=y$ 를 만족해야 한다. x는 간단하게 말해서 오른쪽으로 움직인 횟수고 y는 왼쪽으로 움직인 횟수이다. 왼쪽으로 움직인 횟수와 오른쪽으로 움직인 횟수가 같아야 1번째 원소에서 포인터가 멈추지 않겠는가?

마지막으로 $x=y$ 인 경우에 주목해야 한다. $x=y$ 가 상태가 되면, 즉 $i$번째까지 부분합이 0이 되는 상태를 말한다. 이 상태에선 더이상 앞으로 나아갈 수 없다. $psum \geq 1$ 이어야 앞으로 갈 횟수가 남아 있는 건데, $x=y$ 인 상태에선 한 칸이라도 더 나가면 첫번째 위치로 돌아올 수 없다. 이게 세번째 예외처리.

코드

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    if sum(arr)!=0:
        return 0    
 
    psum, f = 0, 0
    for i in range(n):
        psum += arr[i]
        if psum < 0:
            return 0
        if psum==0:
            f = 1
        elif f:
            return 0
        
    return 1
 
 
for __ in range(int(input())):
    print('Yes' if solve() else 'No')

D. Fake Plastic Trees

풀이

해설