Codeforces Round #796 (Div. 2) ABCD

인터랙티브 있는 라운드라서 시작 전부터 불안했다. A도 어려워서 좀 걸렸고, C가 어이없게 어려웠다. D는 쉬워서 D부터 풀고 C까지 풀어서 4솔!

A. Cirno's Perfect Bitmasks Classroom

$x$가 주어지고 다음 조건을 만족하는 최소값 $y$를 구하라.

풀이

첫번째 조건을 만족하려면, $x$의 비트값 1의 가장 오른쪽를 탐색합니다. $x$는 1이상이므로 이 값은 항상 존재합니다. 구한 값을 $y$의 잠정 값이라 가정을 해봅니다.
두번째 조건을 만족하는지 봐야 합니다. 두번째 조건을 말로 풀어보면, $x$와 $y$의 비트 중 서로 다른 게 1개 이상 있는가? 입니다. 현재 $y$는 $x$의 일부분이거나, $x$와 동일합니다. 만약 $x$가 2의 제곱수라면 $x=y$ 일겁니다.
$x=y$인 경우에 두번째 조건을 만족하지 않으므로 가장 작은 숫자인 1을 조건이 만족할 때까지 더하면 됩니다.

코드

def solve():
    n = int(input())
    t = n
    ans = 1
    while not t&1:
        t = t>>1
        ans = ans<<1
    
    while ans==n or ans&n==0:
        ans += 1
        
    print(ans)


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

B. Patchouli's Magical Talisman

$n$개의 숫자가 주어집니다. 우리는 다음 두 작업을 할 수 있습니다.

Fusion: 숫자 2개를 고르고 합칩니다.
Reduction: 짝수 1개를 고르고 2로 나눕니다.

위 두 작업을 최소로 사용해서 모든 숫자를 홀수로 만들어야 합니다.
최소 작업 수를 구하라.

풀이

숫자 중에 홀수가 1개 이상 있다면, 그 숫자를 가지고 짝수를 Fusion 작업을 하면 최소입니다.
만약 홀수가 없다면, 짝수 $n$개 중에 하나를 골라서 Reduction 작업을 통해서 홀수로 만들고 남은 짝수를 합쳐주면 됩니다.

코드

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    even = [x for x in arr if x%2==0]
    odd = [x for x in arr if x%2]
    
    if not odd:
        cnt =int(1e20)
        for x in even:
            a = x
            cc = 0
            while a%2==0:
                a//=2
                cc+=1
            cnt = min(cnt, cc)
        print(cnt+len(even)-1)
    else:
        print(len(even))

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

C. Manipulating History

최초의 문자열 $s$가 입력된다. $s$는 1개의 알파벳이다. 그 다음 문자열 $2n$ 개가 주어진다.
문자열 $s$ 안에 $t_{2i-1}$ 가 있다면, $t_{2i}$로 바꿀 수 있다. $t_i$는 입력 받은 문자열 $2n$ 중 하나이다.
마지막으로 $s$에서 위 작업을 $n$번 반복한 결과가 주어진다.
여기서 문제는, 입력 받은 $2n$개가 뒤죽박죽 섞였다.
이때, 최초 문자열 $s$를 구하라.

풀이

최초 문자열 $s$, 입력 받은 모든 문자열, 결과 문자열의 모든 문자 갯수를 각각 세서 홀수인 게 정답이다.
증명은 자명하다. s->b로 치환되고 b->c로 치환된다. c는 D로 치환되고 이게 반복되면 결과 문자열이 나온다. 이 과정을 단축시키면 s->결과문자열이다.

코드

def solve():
    n = int(input())
    arr = [input().rstrip() for __ in range(2*n+1)]
    
    cnt = [0]*26
    
    for x in arr:
        for i in x:
            tt = ord(i)-97
            cnt[tt] += 1
    
    for i in range(26):
        if cnt[i]%2:
            print(chr(i+97))
            return


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

D. The Enchanted Forest

길이가 $n$인 숲이 있다. 길은 $x$축 위에 있고 $1$부터 $n$까지 숫자로 표기된다.
길에는 $a_i$개의 버섯이 있고, 1초마다 각 자리에서 1개의 버섯이 자라난다.
우리는 특정 좌표에서 시작해서 1초에 1칸씩 이동할 수 있다. 우리는 현재 위치에 있는 버섯을 모두 채취할 수 있다.
우리는 최대 $k$번 이동할 수 있을 때, 우리가 채취할 수 있는 버섯의 최대 갯수를 구해라.

풀이

버섯은 매초마다 생긴다. 이럴 경우에, 우리가 채취할 수 있는 버섯을 나눠야 한다. 버섯은 두종류이다. 최초에 있던 버섯들과 0초 이후에 새로 생겨난 버섯들.
0초 이후에 새로 생겨난 버섯 중 우리가 채취한 갯수는 한 번에 알 수 있다. $a_i$ 지점에 마지막으로 방문한 시각이 $t_i$라면, 해당 지점에서 우리가 얻은 총 버섯 갯수는 $k-t_i-1$이다.
이유는 우리가 $a_i$를 여러번 방문해서 마지막 방문 시각이 $t_i$일 때와, 딱 한 번 방해서 마지막 방문 시각이 $t_i$일 때, 우리가 해당 지점에서 얻는 새로난 버섯의 총 갯수는 동일하다.
이 아이디어를 전체로 확장하면, (최초 버섯 중 채취할 수 있는 최대 갯수) + (각 위치 별 마지막 방문 시점에 따른 누적 채취 갯수) 가 정답이 된다.

$(k>=n)$ 일 때, 우리는 모든 위치에 도달할 수 있어 최초 버섯은 모두 채취할 수 있다. 새로 생겨난 누적 채취 버섯 갯수는 $(\sum_{a=k-n}^{k-1} a) *n//2$이다.
$(k<n)$ 일 때, 우리는 모든 위치에 도달할 수 없어서 채취할 수 있는 최초 버섯의 최대 갯수를 구해야 한다. 이건 투포인터로 간단하게 구할 수 있다. 새로 새겨난 누적 채취 버섯 갯수는 위와 유사하게 구할 수 있다.

코드

def solve():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    
    if k >= n:
        ans = sum(arr)+((k*2-n-1)*n//2)
        print(ans)
    else:
        psum = 0
        now = 0
        ret = 0
        for i in range(n):
            psum += arr[i]
            if i-now+1 > k:
                psum -= arr[now]
                now += 1
            ret = max(ret, psum)
        ans = ret+((k-1)*k//2)
        print(ans)
 
 
for __ in range(int(input())):
    solve()