Codeforces Round #782 (Div. 2) A

[9번째 Contest]

슬럼프 시기에 친 버추얼,, A도 못 풀고 빡종. 지금 다시 보니까 이땐 많이 힘들었나보다. A도 못 풀고,,

A. Red Versus Blue

정수 $n$, $r$, $b$ $(r>b,\; n=a+b)$를 입력 받는다. $r$은 문자열 $R$ 의 갯수, $b$는 문자열 $B$ 의 갯수다. $R$ $r$개와 $B$ $b$개를 적절히 배치해서 길이가 $n$인 문자열을 만들어라. 단, 연속된 R의 갯수를 최소화해라.

풀이

문자열 $B$ 하나를 기준으로 사이 공간과 양끝에 문자열 $R$을 균등하게 배치하면 된다. $R$이 배치될 공간은 $b+1$개 있다. 각 공간에 $r/(b+1)$개를 배치하고 남은 건 하나씩 배치하면 된다.

코드

def solve():
    n, a, b = map(int, input().split())
    ans = ''
    b += 1
    for i in range(a%b):
        ans += 'R'*(a//b+1)+'B'
    for i in range(b-a%b):
        ans += 'R'*(a//b)+'B'
    print(ans[:-1])
    
    
for __ in range(int(input())):
    solve()

B. Bit Flipping

길이가 $n$인 $0$과 $1$로 구성된 $binary\; string$이 주어진다. 정확히 $k$번 다음 작업을 하고 난 뒤에 만들 수 있는 문자열 중 사전 순으로 가장 뒷 문자열을 구하라. 즉, 가장 큰 수를 구하라.

$i$번째 비트를 고르고 $i$번째를 제외한 나머지 비트를 모두 뒤집는다.

그리고 각 비트 별로 작업을 수행한 횟수를 구해라.

풀이

일반적인 풀이

다른 풀이: 미시적 접근

내 풀이 방식인데, 이런 애드혹스러운 문제에선 이런 접근이 필요한 경우가 있다.

$i$번 비트와 $j$번 비트에 대해 작업을 수행하면, 두 비트만 뒤집힌다. $2$번의 작업으로 다음 작업을 할 수 있는데, 이걸 응용해서 풀 수 있다.

$s_i=0$이고 $s_j=0$이라고 하자. $2$번의 작업으로 $s_i=1, s_j=1$로 만들 수 있다. 앞에서부터 $s_i=0$인 비트를 $2$개씩 $1$로 바꿔주면 된다.

여기서 $k$가 홀수, 짝수에 따라 결과가 바뀐다. $k$가 홀수라면, 위 작업을 아무리 반복해도 항상 한 번의 작업 횟수가 남는다. 그러면 $a_i$번 비트를 제외한 모든 비트를 뒤집는 작업을 하게 된다.

$k$가 홀수라면, 문자열을 최대한 $0$으로 바꾸고 마지막에 모두 뒤집어 주면 된다. 문자열 앞에서부터 $a_i=1, a_j=1$인 $i, j$를 골라서 $0$으로 바꾼다. 마지막에 가장 앞선 $k(a_k=1)$을 선택하고 작업을 $1$회 수행하면 된다.

$k$가 짝수라면, 문자열을 최대한 $1$로 바꾸면 된다. 만약에 작업 횟수가 남았는데, 가장 앞선 $k(a_k=0)$가 $n$이 아니라면, $i=k, j=n$에 대해 작업을 2회 더 실행한다. 즉, 작업 횟수가 남았는데 값이 $0$인 비트가 양끝이 아닌 곳이 있다면, 맨 오른쪽 값과 바꾼다.

남은 작업 횟수는 반드시 짝수고, 이는 결과에 어떤 영향을 주지 못한다. 남은 작업 횟수를 맨 앞에 더해준다.

코드

# 다른 풀이: 미시적 접근
def solve():
    n, k = map(int, input().split())
    s = list(map(int, list(input())))
    
    a, b = [], []
    cnt = [0]*n
    for i in range(n):
        if s[i]:
            b.append(i)
        else:
            a.append(i)
    
    if k%2:
        for i in range(0, len(b)-1, 2):
            if k<2:
                break
            s[b[i]], s[b[i+1]] = 0, 0
            cnt[b[i]] += 1
            cnt[b[i+1]] += 1
            k -= 2
        
        for i in range(n):
            if s[i]==1:
                s = [int(not x) for x in s]
                s[i] = 1
                cnt[i] = 1
                k -= 1
                break
        else:
            s = [int(not x) for x in s]
            s[-1] = 0
            cnt[-1] += 1
            k -= 1
            
    else:
        for i in range(0, len(a)-1, 2):
            if k<2:
                break
            s[a[i]], s[a[i+1]] = 1, 1
            cnt[a[i]] += 1
            cnt[a[i+1]] += 1
            k -= 2
        
        if k:
            for i in range(n-1):
                if s[i]==0:
                    s[i], s[-1] = 1, 0
                    cnt[i] += 1
                    cnt[-1] += 1
                    k -= 2
                    break
    
    cnt[0] += k
    print(''.join(map(str, s)))
    print(*cnt)
    
    
for __ in range(int(input())):
    solve()