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()

너무 힘든 날이어서 안하려고 했는데,, 시작 5분 전에 하고 싶어져서 갑자기 참여!

AB가 너무 쉬웠고, C도 이분탐색 웰논이라 금방 풀었다. D는 풀이가 바로 생각났는데, 음,, 살짝 잘못해서 못 풀었다.

이젠 블루 퍼포가 안정적으로 나온다. D의 벽도 조금씩 허물어가는 느낌? 안정적인 4솔까지 열심히 해야겠다!

A. Grass Field

$2*2$ 그리드가 입력된다. $0$과 $1$로 차 있는데, 다음 작업을 최소로 사용해서 모든 그리드의 수를 $0$으로 만들어야 한다. 최소 작업수를 구하라.

작업은 $1$개 행과 $1$개 열을 골라서 $0$으로 바꾼다.

풀이

그리드가 아래와 같을 때, 정답은 $2$

1 1
1 1

그리드가 아래와 같을 때, 정답은 $0$

0 0
0 0

나머지는 정답 $1$

코드

def solve():
    a = [list(map(int, input().split())) for __ in range(2)]
    p = sum([sum(x) for x in a])
    if p==0:
        print(0)
    elif p==4:
        print(2)
    else:
        print(1)

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

B. Permutation

풀이

코드

C. Schedule Management

풀이

코드

D. Permutation Restoration

풀이

코드

# 문자열 입력 받기
s = input()


# 1개의 숫자 입력 받기
n = int(input())


# 2개의 숫자 한 줄에서 입력 받기
a, b = map(int, input().split())


# 3개의 숫자 한 줄에서 입력 받기
a, b, c = map(int, input().split())


# 여러 개의 숫자 여러 줄에서 입력 받기
a = int(input())
b = int(input())


# 한 줄로 리스트 입력 받기
a = list(map(int, input().split()))


# 여러 줄에 걸쳐 들어오는 숫자 리스트로 받기
a = [int(input()) for __ in range(n)]

설명

s = input()

위 코드에서 input()은 입력되는 모든 걸 문자열로 취급해요.

만약에 1을 입력하면, s="1"이 저장되는 거에요.

숫자를 입력 받으려면 input()에 int()를 씌운 형태로 작성해야 해요.

n = int(input())

위 코드에서 1을 입력하면, n=1이 저장돼요.

그럼, 이제 split과 map이라는 함수가 있어요.

split 은 말 그대로 쪼개는 거에요.

split 함수는 안에 주어진 인자를 기준으로 문자열을 쪼개서 리스트로 변환해줘요.

a = input().split()
print(a)

# input >> 1 2 3 4 5
# output >> ["1", "2", "3", "4", "5"]

보이나요? input으로 문자열 "1 2 3 4 5"을 입력 받았어요. split은 "1 2 3 4 5"를 띄어쓰기 단위로 쪼개서 리스트로 변환해줘요.

이제, map을 볼게요. map 함수는 map(자료에 적용할 함수, 변환할 자료) 형태로 이뤄져있어요.

예시 코드를 보고 이해해볼게요.

a = list(map(int, input().split()))

# input >> 1 2 3 4 5
# output >> [1, 2, 3, 4, 5]

위에서 input().split()은 ["1", "2", "3", "4", "5"] 까지 만들어준다고 했어요.

우리가 원하는 건 문자로 구성된 리스트가 아니라, 숫자로 구성된 리스트에요.

위 리스트의 각각 원소를 숫자로 바꿔줘야 해요. 가장 간단한 방법은 다음과 같을 거에요.

a = input().split()
b = []
for i in range(len(a)):
    b.append(int(a[i]))
print(b)

# input >> 1 2 3 4 5
# output >> [1, 2, 3, 4, 5]

그런데, 파이썬에선 이런 방법이 권장되지 않아요. 파이썬엔 map이라는 편한 함수가 있거든요.

위에서 map 함수 구조를 보면 map(자료에 적용할 함수, 변환할 자료) 이런 형태라고 했어요.

map 함수는 두번째 인자인 변환할 자료에 첫번째 인자인 자료에 적용할 함수를 각각 적용해서 돌려줘요.

map 함수에 int 함수와 ["1", "2", "3", "4", "5"]를 인자로 주면 다음과 같은 형태일거에요.

map(int, ["1", "2", "3", "4", "5"])

두번째 인자인 ["1", "2", "3", "4", "5"]에 각각 int 함수를 적용한 결과를 우리에게 돌려줘요.

여기서 한 가지 중요한 점. map 함수는 map 객체라는 걸 반환하기 때문에, 우리는 map 객체를 list로 변환 시켜줘야 해요.

따라서 아래와 같은 결과가 나오게 돼요.

a = list(map(int, input().split()))
print(a)

# input >> 1 2 3 4 5 
# output >> [1, 2, 3, 4, 5]

마지막으로, 여러 줄에 걸쳐서 입력되는 숫자를 하나의 리스트에 저장하는 방법이에요. 아래처럼 N개의 입력되는 숫자들을 하나의 리스트에 넣고 싶어요.

5 <- N
1
2
3
4
5

간단한 방법인 다음과 같을 거에요.

a = []
n = int(input())
for i in range(n):
    a.append(int(input()))

위처럼 해도 좋아요! 그런데, 파이썬엔 더 짧고 간결한 코드가 있어요.

구글에 python list comprehension과 python for in one line 키워드를 치면 더 자세한 설명이 나올 거에요.

반복문을 한 줄로 처리하는 문법인데요. 위 코드를 아래처럼 바꿀 수 있어요!

n = int(input())
a = [int(input()) for i in range(n)]

일단 써보고 익숙해지면, 그 의미를 파악하는 방법도 좋아요!

사실 바로 위 코드도 더 줄일 수 있답니다. 익숙해지면, 사용해보세요!

a = [int(input()) for __ in range(int(input()))]

[12번째 Contest]

방학 안에 100개의 콘테스트에 참가할 수 있을까..?

대회 준비로 코포에 집중을 못하고 있다. 이전에 1일 1버추얼 돌리다가 그린까지 떨어지는 대참사를 겪었기에 버추얼을 함부로 못하겠다..

오늘 코포는 AB가 굉장히 쉬웠는데, C가 C답지 않게 어려웠다.

A. The Third Three Number Problem

$n$이 주어진다. 우리는 다음 수식을 만족하는 $a, b, c$를 결정해야 한다.

$(a \oplus b)+(b \oplus c)+(c \oplus a)=n$

풀이

$n$이 홀수면, 조건을 만족하는 정답은 없다. $return -1$ 이건 $a, b, c$에 홀수, 짝수를 잘 조합해보면 바로 알 수 있다.

$a, b$ 를 $0$으로 고정시키고 풀면 간단하다. 전형적인 코포스타일 문제. $a=0, b=0$으로 두면, 위 식은 간단하게 정리된다. $2*c=n$ 이고, $c = n/2$이다

코드

def solve():
    n = int(input())
    if n%2:
        print(-1)
    else:
        print(0, 0, n//2)

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

B. Almost Ternary Matrix

$n, m$이 주어진다. $n*m$짜리 그리드를 $0$과 $1$로 채워야 한다. 문제는, 이웃한 숫자들 중에 다른 숫자가 딱 $2$개 존재하게 채워야 한다. 예를 들면, $0$으로 채워진 칸은 이웃한 칸에 $1$이 딱 $2$개 존재해야 한다.

풀이

구성적 느낌의 문제다. 다음 패턴을 확장, 반복해서 출력하면 된다. 직접 그림을 그려가며 패턴을 찾아야 한다.

1 0 0 1
0 1 1 0 
0 1 1 0
1 0 0 1

코드

dp = [[1, 0, 0, 1]*50, [0, 1, 1, 0]*50, [0, 1, 1, 0]*50, [1, 0, 0, 1]*50]*50

def solve():
    a, b = map(int, input().split())
    for d in dp[:a]:
        print(*d[:b])  


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

C. The Third Problem

길이가 $n$인 $permutation$ $a$가 주어진다. 우리는 모든 구간에서 $a$와 $similar$한 $permutation$ $b$를 만들어야 한다. $similar$의 조건은 다음과 같다.

모든 구간 $[l, r]$에 대해서 $MEX([a_l, a_{l+1}, ..., a_{r}]) = MEX([b_l, b_{l+1}, ..., b_{r}])$를 만족하면 $similar$하다.

풀이

$a$에서 $i$의 위치를 $p[i]$라고 가정하자. $b$에서 $0$의 위치를 잘 생각해보자. $b$에서 $0$의 위치는 반드시 $p[0]$이다. $MEX([a_{p[0]}])=1$ 이기 때문이다. $b$에서 $1$의 위치도 고민해보자. $1$ 역시 $p[1]$에 위치한다.

구간 $[l, r]$을 정의해보자. $l=p[0], r=p[1] ;\ (p[0]<p[1])$이라고 가정하자. 이때, $a$에서 $2$의 위치를 생각해보자.

$l < p[2] < r$ 이라면, $b$에서 $2$는 구간 $[l,r]$ 안에 존재해야 한다. 이거에 대한 정당성은 에디토리얼에 자세히 적혀 있다. 이 경우에, $ans ; *= (r-l+1-i)$ 해준다. $(r-l+1-i)$은 구간 $[l,r]$에서 $2$가 위치할 수 있는 경우의 수다.

$p[2]$가 구간 밖에 존재한다면, 구간 $[l,r]$을 $p[2]$를 포함하는 구간으로 적절히 갱신해준다.

코드

MOD = 1_000_000_007

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 1

    p = [0]*n
    for i in range(n):
        p[a[i]] = i

    l, r = p[0], p[0]

    for i in range(1, n):
        idx = p[i]
        if l < idx < r:
            ans *= (r-l+1-i)
            ans %= MOD
        l = min(l, idx)
        r = max(r, idx)

    print(ans)

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

오늘 껀 너무 쉬웠다. 다만, C에서 5 WA 맞고 개같이 멸망할 뻔하고, D도 잘못 해석해서 20분 버리고. 그래도 4솔에 블루 퍼포니까 만족.

A. XOR Mixup

길이가 $n-1$인 배열 $a$가 있다. $a$의 모든 원소를 $xor$ 연산한 결과를 $x$라고 하자. $a$에 $x$를 추가하고 무작위로 $a$를 섞었다. $x$를 구해라.

풀이

브루트포스 $O(N^2)$

$n\leq100$이므로 $O(N^2)$으로 풀면 된다. $a_i$가 $a_i$를 제외한 모든 원소에 대해 $xor$ 연산을 한 결과와 동일하면 바로 출력하면 된다.

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    for i in range(n):
        x = 0
        for j in range(n):
            if i==j:
                continue
            x ^= a[j]
        if x==a[i]:
            print(a[i])
            return


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

풀이

그리디를 이용한 O(N)

$a$의 모든 원소를 $xor$하면 $0$이다. 이 말은 $a$의 어떤 원소 $a_i$를 제외하고 $xor$한 결과는 $a_i$라는 뜻이다. 모든 원소가 정답이 될 수 있다.

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    print(a[0])


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

B. Rising Sand

길이가 $n(1\leq n \leq2*10^5)$인 배열 $a$가 주어진다. 정수 $k(1\leq k \leq n)$도 주어진다. $a_i > a_{i+1} + a_{i-1}$를 만족하는 $i$에 대해 $tall$ 하다고 말할 수 있다. 아래 작업을 무수히 반복해서 만들 수 있는 최대 $tall$ 갯수를 구해라.

• 연속된 $k$개의 배열 요소에 대해 모두 $+1$를 한다.

풀이

$k=1$이라면, 작업을 무수히 해서 $(n-1)/2$ 개의 $tall$을 만들 수 있다. $a_1, a_3, a_5, ..., a_{(n-1)/2}$ 을 $tall$하게 만들 수 있다.

$k\geq2$라면, 작업을 하면 손해다. 작업을 통해서 $tall$하지 않은 $a_i$는 $tall$해질 수 없다. $a_i$를 증가시키려면 $a_{i+1}$ 또는 $a_{i-1}$도 같이 증가하기 때문이다.

코드

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    if k==1:
        print((n-1)//2)

    ans = 0
    for i in range(1, n-1):
        if a[i] > a[i-1]+a[i+1]:
            ans += 1

    print(ans)


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

C. 3SUM Closure

길이가 $n$인 배열 $a$가 입력된다. 서로 다른 $i, j, k$를 선택했을 때, $a[i]+a[j]+a[k]$가 배열 $a$ 안에 있는지 확인한다. 모든 $i, j, k$에 대해서 단 하나라도 없으면 "NO", 모두 있으면 "YES"를 출력하라. $a[i]+a[j]+a[k]$를 $3sum$이라고 하겠다.

풀이

구성적 풀이

$n$의 길이에 따라 나눠진다.

$n \leq 4$라면, 모든 경우를 계산해보면 된다.

$n \geq 5$라면, 특정 경우에만 "YES"가 출력된다. 예시를 들어 설명해보겠다.

$a=[0, 0, 1, 2, 3]$ 라면, 성립하지 않는다. 같은 부호를 갖는 수가 $2$개 이상 있으면 항상 $max(a)$보다 큰 $3sum$이 존재하기 때문이다. 부호가 반대일 때도 성립한다.

$a=[0, 0, 0, 0, 0, 4]$ 라면, 성립한다. 같은 부호를 갖는 수가 $1$개 밖에 없고 나머지는 $0$이다. $3sum$은 $0$ 또는 $4$이다.

$a=[-3, 0, 0, 0, 3]$ 라면, 성립한다. 부호가 서로 다른 수가 단 2개 존재하기 절댓값이 같기 때문이다. $3sum$은 $0$ 또는 $-3$ 또는 $3$이다.

이와 같은 예시를 만들어서 예외케이스 처리하면 된다.

코드

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    if n<=4:
        for x in C(a, 3):
            if sum(x) not in a:
                return 0
        return 1
    else:
        b = [x for x in a if x]
        if len(b)>2:
            return 0
        if len(b)<=1:
            return 1
        if b[0]+b[-1]==0:
            return 1
        return 0


for __ in range(int(input())):
    print('YES' if solve() else 'NO')

브루트포스 풀이

풀이

에디토리엄 해설이 더 깔끔해서 정리해봤다.

같은 부호를 갖는 수가 $3$개 이상이라면, 항상 "NO"를 출력한다. 같은 부호를 같은 수들의 $3sum$ 중 $max(a)$보다 큰 수가 항상 존재하기 때문이다.

이외의 경우에 브루트포스를 돌리면 된다. 여기서 주의해야 하는 건, 브루트포스 돌리는 $a$의 길이를 $3$ 이상으로 최소가 되게 해야 한다.

코드

from itertools import combinations as C


def solve():
    n = int(input())
    a, b, c = [], [], []
    for x in map(int, input().split()):
        if x>0:
            a.append(x)
        if x<0:
            b.append(x)
        if x==0 and len(c)<2:
            c.append(x)

    if len(a)>2 or len(b)>2:
        return 0

    c += a+b
    for x in C(c, 3):
        if sum(x) not in c:
            return 0
    return 1


for __ in range(int(input())):
    print('YES' if solve() else 'NO')

D. Fixed Point Guessing

길이가 $n$($n$은 홀수)인 배열 $a=[1, 2, ... , n]$가 있다. $2$개씩 $(n-1)/2$개의 원소 쌍을 고르고 한 쌍의 원소를 $swap$해주었다. $a$의 단 하나의 원소만 원래 자리를 유지하고 있는 상황이다. 다음 쿼리를 사용해서 그 원소를 구하라.

• $l, r$ 쿼리를 날리면, $[a_l, ... , a_r]$이 정렬된 상태로 주어진다.

풀이

눈치채야 할 게 있다. $n \leq 10^4$이고 사용할 수 있는 쿼리 수는 $15$다. 얼추 $log;n=query$ 이니까 $binary;search$를 하면 되는 게 보인다.

$left=1, right=n$으로 초기화하고 $mid=(left+right)/2$로 초기화한다. $left$와 $mid$를 퀴리로 날리면 반환값에 의해 값이 어디있는지 알 수 있다. $a[left:mid]$ 값을 $a_i$라고 하자. $a_i$가 구간 안에 있는 수인지 세야 한다. 즉, $left \leq a_i \leq mid$인 갯수를 구해야 한다.

갯수가 홀수라면, 정답은 구간 $[left:mid]$에 있다. 항상 $2$개 원소를 $swap$을 하는데 갯수가 홀수면 해당 구간에 혼자 남는 원소가 있다는 뜻이고 그 수가 정답이다.

갯수가 짝수라면, 위와 동일한 이유로 정답은 $[mid+1: right]$에 있다.

코드

def query(a, b):
    print('?', a, b, flush=True)
    return list(map(int, input().split()))


def solve():
    n = int(input())

    left, right = 1, n
    while left < right:
        mid = (left+right)//2
        ret = query(left, mid)
        cnt = 0
        for x in ret:
            if left <= x <= mid:
                cnt += 1

        if cnt%2:
            right = mid
        else:
            left = mid+1
    return left


for __ in range(int(input())):
    print('!', solve(), flush=True)

E. PermutationForces II

빠른 3솔로 블루 퍼포냈다. DE는 너무 어렵다.. 특히,, E는 정수론이라 당했다.

지난 3번의 코포에서 떡락으로 300점을 날려서 2주 동안 슬럼프가 있었다.

버추얼을 돌려도 0솔을 했다. 자신감이 많이 떨어진 상황이었다.

어제 하루 코딩을 놓고 넷플과 롤체를 하며 힐링 시간을 가졌다. 오늘은 가볍게 업솔빙하면서 자신감을 회복했다.

그리고 오늘 코포에서 블루 퍼포 회복하고 +100 레이팅을 가져갔다.

A. NIT orz!

길이가 $n$인 배열과 정수 $z$가 입력된다. 다음 작업을 무수히 많이 해서 배열 안에 가장 큰 수를 구하는 문제다.

임의의 $i , (1 \leq i \leq n)$에 대해서, $a_i = (a_i ; or ; z)$, $z = (a_i ; and ; z)$

풀이

$z$는 위의 작업으로 초기의 $z$보다 커질 수 없다. $and$ 연산은 아무리 해도 없던 비트가 생기지 않기 때문이다. 따라서 초기의 $z$와 배열 $a$ 안에 원소를 $or$ 연산을 한 최댓값을 구하면 된다.

코드

def solve():
    a, b = map(int, input().split())
    arr = list(map(int, input().split()))

    c = 0
    for x in arr:
        c = max(c, x|b)
    print(c)


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

B. NIT Destroys the Universe

길이가 $n$인 배열 $a$가 들어온다. 다음 작업을 통해 $a$의 모든 수를 $0$으로 만들어야 한다. 사용하는 작업의 최소갯수를 구하라.

$l, r (1≤l≤r≤n)$를 고른다. $w=mex({a_l,a_{l+1},…,a_r})$ 라고 하면, $a_i = w (l≤i≤r)$로 초기화 한다. $mex(a[l:r])$은 구간 안에 없는 가장 작은 $0$보다 큰 정수이다.

풀이

$0$을 기준으로 접근해야 한다. 연속된 양의 정수 그룹의 갯수에 따라 풀이가 나뉜다. 그룹이 없다면 모두 $0$이므로 작업할 필요가 없다. 그룹이 $1$개 있다면, 그 그룹만 작업을 한 번 실행하면 된다. 그룹이 $2$개 이상이라면, 각 그룹에 대해 작업하면 실행 횟수가 최소화되지 않는다. 이 경우에 전체에 대해서 작업을 두 번만 실행하면 된다.

$a$의 원소가 모두 $0$이라면 작업할 필요가 없다.

$a = [0, 1, 2, 3, 0]$ 이라면 $l=2, r=4$에 대해 작업을 한 번만 실행하면 된다.

$a = [0, 1, 0, 2, 0, 3]$ 이라면 $l=1, r=6$으로 두고 작업을 두 번 실행하면 된다.

코드

def solve():
    n = int(input())
    arr = list(map(int, input().split()))

    l, r = -1, -1
    for i in range(n):
        if arr[i]!=0:
            if l==-1:
                l = i
            r = i

    if l==-1:
        return 0
    for i in range(l+1, r):
        if arr[i]==0:
            return 2
    return 1


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

C. Fishingprince Plays With Array

정수 $n, m, k$ 와 각각 길이가 $n$과 $k$인 배열 $a, b$가 입력된다. 우리는 다음 작업을 무수히 수행해서 $a$를 $b$로 바꿀 수 있는지 확인해야 한다.

• 쪼개기: $m$으로 나눠 떨어지는 $a_i$를 선택한다. $a_i$ 위치에 $a_i/m$ $m$개를 삽입한다.
• 합치기: 연속된 동일한 수 $m$개를 선택한다. 모든 수를 없얘고 그 위치에 $a_i*m$를 삽입한다.

풀이

쪼개기와 합치기는 반대되는 작업이다. 작업을 꼭 a에만 적용할 필요는 없다. a와 b를 적절하게 변형하고 동일한지 확인하면 된다. 가장 간단한 방법은 a와 b를 최소 단위로 쪼개서 확인하는 거다. 최소 단위로 쪼갰을 때, 구성이 같다면 합쳤을 때도 같다.

무지성 쪼개서 저장하면 메모리랑 시간이 터질 수도 있다. 연속된 같은 수가 있다면, 개수를 세서 저장하면 된다.

코드

def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    k = int(input())
    b = list(map(int, input().split()))

    if sum(a)!=sum(b):
        return 0

    c = []
    for i in range(n):
        x = a[i]
        cnt = 0
        while x%m==0:
            x //= m
            cnt += 1
        t = (x, m**cnt)
        if not c:
            c.append(t)
            continue
        if c[-1][0]==t[0]:
            c[-1] = (x, c[-1][1]+t[1])
        else:
            c.append(t)

    d = []
    for i in range(k):
        x = b[i]
        cnt = 0
        while x%m==0:
            x //= m
            cnt += 1
        t = (x, m**cnt)
        if not d:
            d.append(t)
            continue
        if d[-1][0]==t[0]:
            d[-1] = (x, d[-1][1]+t[1])
        else:
            d.append(t)

    if c==d:
        return 1
    return 0


for __ in range(int(input())):
    print('Yes' if solve() else 'No')

D. Permutation Graph

길이가 $n$인 $permutation$ 이 주어진다. $permutation$은 $1$부터 $n$까지 중복된 숫자 없이 구성된 배열이다. $permutation$으로 다음 조건을 만족하면 $edge$를 추가해서 그래프를 구성할 수 있다.

$p = [a_i,...,a_j]$ 라고 하면 $min(p)=a_i, max(p)=a_j$ 또는 $min(p)=a_j, max(p)=a_i$ 인 경우에 $i$와 $j$를 연결하는 $edge$를 추가한다.

우리는 $1$번 $vertex$에서 시작해서 $n$번 $vertex$로 가는 최단 경로를 찾아야 한다.

풀이

여러 풀이가 있고, 어떤 자료구조를 사용하냐에 따라 시간 복잡도가 갈린다.

이 문제의 전반적인 그리디함은 한 번의 이동에서 최대한 멀리 가야 한다. 이것의 정당성은 증명이 간단해서 넘어가도록 한다.

그리디와 투포인터를 이용한 풀이: $O(N)$

$p$의 길이가 $1$이면 시작과 끝이 같아서 최단 경로는 $0$.

$i$부터 $j$까지 잇는 간선이 있다고 하자. 이걸 $edge(i, j)$라고 하자. 그러면 $p[i:j]$를 $minmax$ 조건을 충족하는 하나의 구간이라고 생각할 수 있다.

$p[i]$는 $min(p[i:j])$거나 $max(p[i:j])$이다. $p[i] < p[i+1]$ 라면 $min(p[i:j])=p[i]$이고 $p[i]>p[i+1]$이라면 $max(p[i:j])=p[i]$이다.

$min(p[i:j]) = p[i]$인 경우를 보자. 우리는 가능한 $j$의 가장 큰 값을 구해야 한다. $i+1$부터 $n$까지 포인터를 움직이며 최대한 멀리 가보자. 이 포인터의 위치를 $k$라고 하자.

$p[k]=max(p[i+1:n])$일 때, $j=k$이다. $p[k+1:n]$에서 $p[k]$보다 큰 값이 없어서 간선이 연결될 수 없기 때문이다. 이 경우에 $edge(i, k)$가 존재한다.

$p[k] < p[i]$일 때, $j=k-1$이다. $p[k]<[i]$면 $min(p[i:j])=p[i]$라는 초기 조건이 충족되지 않기 때문이다.

$max(p[i:j]) = p[i]$인 경우는 반대로 하면 된다.

여기서 $min(p[i:j])$와 $max(p[i:j])$는 $p$가 $permutation$이라는 특성을 이용해 투포인터로 관리하면 된다.

코드

# 그리디, 투포인터 풀이 O(N)
def solve():
    n = int(input())
    a = list(map(int, input().split()))

    if n==1:
        print(0)
        return 

    c = [1]*(n+1)
    c[a[0]] = 0
    p, q = n, 1
    ans = 0

    l, r = a[0], a[1]
    for i in range(1, n-1):

        while p>0 and c[p]==0:
            p -= 1
        while q<n and c[q]==0:
            q += 1

        c[a[i]] = 0

        if l < r:
            if r==p:
                ans += 1
                l, r = a[i], a[i+1]
                continue
        else:
            if r==q:
                ans += 1
                l, r = a[i], a[i+1]
                continue

        if l < r:
            if a[i+1] < l:
                ans += 1
                l, r = r, a[i+1]
            if a[i+1] > r:
                r = a[i+1]
        else:
            if a[i+1] > l:
                ans += 1
                l, r = r, a[i+1]
            if a[i+1] < r:
                r = a[i+1]

    print(ans+1)


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

풀이

그리디와 분할정복, 세그먼트 트리를 이용한 $O(N,logN)$

우리는 반드시 $max(p)$를 거쳐야 최적의 답을 구할 수 있다. $max(p) = a_i$를 하자. $i$는 $1$과 $n$이 아니라고 가정한다. 우리는 $1$번 $vertex$에서 시작해서 $i$번 $vertex$를 거쳐서 $n$번 $vertex$에 도달해야 한다. $2$개의 구간으로 나뉘게 된다. $p[1:i]$와 $p[i:n]$.

$p[1:i]$ 구간을 보자. $1$번 $vertex$ $\to ... \to$ $i$번 $vertex$로 이동해야 한다. $max(p[1:i]) = p[i]$이다. $i$번과 연결될 수 있는 가장 최적의 수는 $min(p[1:i])=j$이다.

그럼 또다시 $2$개의 구간으로 쪼개진다. $p[1:j]$와 $p[j:i]$. $p[j:i]$는 더이상 쪼갤 필요가 없고 $1$번의 이동하면 된다. 남은 건 $p[1:j]$이고, $min(p[1:j])=p[j]$이다. 위 작업을 계속 반복하면 된다.

$p[i:n]$ 구간도 동일하게 반복하면 된다.

특정 구간의 $min$, $max$를 구하는 건 세그트리를 이용해서 $O(N,logN)$의 시간으로 구할 수 있다.

코드

// 그리디, 분할정복, 세그먼트 트리 풀이 O(N log N)
#include <bits/stdc++.h>
using namespace std;

vector<int> mintree;
vector<int> maxtree;
vector<int> arr;
vector<int> idx;

int mininit(int start, int end, int node)
{
    if (start == end)
        return mintree[node] = arr[start];
    return mintree[node] = min(mininit(start, (start + end) / 2, node * 2), mininit((start + end) / 2 + 1, end, node * 2 + 1));
}

int getmin(int start, int end, int node, int left, int right)
{
    if (end < left || right < start)
        return 1e9;
    if (left <= start && end <= right)
        return mintree[node];
    return min(getmin(start, (start + end) / 2, node * 2, left, right), getmin((start + end) / 2 + 1, end, node * 2 + 1, left, right));
}

int maxinit(int start, int end, int node)
{
    if (start == end)
        return maxtree[node] = arr[start];
    return maxtree[node] = max(maxinit(start, (start + end) / 2, node * 2), maxinit((start + end) / 2 + 1, end, node * 2 + 1));
}

int getmax(int start, int end, int node, int left, int right)
{
    if (end < left || right < start)
        return 0;
    if (left <= start && end <= right)
        return maxtree[node];
    return max(getmax(start, (start + end) / 2, node * 2, left, right), getmax((start + end) / 2 + 1, end, node * 2 + 1, left, right));
}

int run1(int n, int x)
{
    int f = 1, ret = 0;
    while (x > 0)
    {
        if (f)
            x = idx[getmin(0, n - 1, 1, 0, x)];
        else
            x = idx[getmax(0, n - 1, 1, 0, x)];
        ret++;
        f = !f;
    }
    return ret;
}

int run2(int n, int x)
{
    int f = 1, ret = 0;
    while (x < n - 1)
    {
        if (f)
            x = idx[getmin(0, n - 1, 1, x, n - 1)];
        else
            x = idx[getmax(0, n - 1, 1, x, n - 1)];
        ret++;
        f = !f;
    }
    return ret;
}

void solve()
{
    int n;
    cin >> n;

    arr.resize(n);
    idx.resize(n + 1);
    mintree.resize(n * 4);
    maxtree.resize(n * 4);

    for (auto &x : arr)
        cin >> x;

    for (int i = 0; i < n; i++)
        idx[arr[i]] = i;

    mininit(0, n - 1, 1);
    maxinit(0, n - 1, 1);

    int ans = 0;

    int mmax = idx[getmax(0, n - 1, 1, 0, n - 1)];

    ans += run1(n, mmax);
    ans += run2(n, mmax);

    cout << ans << '\n';

    arr.clear();
    idx.clear();
    mintree.clear();
    maxtree.clear();
}

int main()
{
    ios_base ::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
        solve();
}

슬럼프 시기에 친 버추얼,, 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()

이건 UCPC 팀연습할 겸 pizzaroot와 함께 했다.

빠르지 않은 3솔, D는 넘사로 어렵다

A. Direction Change

$n*m$ 크기 그리디가 주어진다. $(1, 1)$에서 $(n, m)$으로 이동하는데, 상하좌우 모두 움직일 수 있다. 두 번 이상 같은 방향으로 이동할 수 없다. $(n, m)$으로 이동하는 최소횟수를 구하라.

풀이

$n$과 $m$이 $2$ 이상이면 어떻게든 $(n, m)$으로 이동할 수 있다. $n==m$면 계단 모양으로 이동하면 된다. 그 외의 경우엔, 계단 모양으로 맨 아래 층까지 이동하고 남은 거리를 지그재그 모양으로 움직이면 된다.

코드

def solve():
    n, m = map(int, input().split())

    if n>m:
        n, m = m, n
    if n==1 and m>=3:
        print(-1)
    else:
        print((n-1)*2+(m-n)//2*4+(m-n)%2)


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

B. Social Distance

$m$개의 의자가 있고, $n$명의 사람이 있다. 크기가 $n$인 배열 $a$가 입력된다. $i$번째 사람은 좌우로 최소 $a[i]$만큼의 공석이 있길 바란다. 모두가 원하는 대로 배치할 수 있는가?

풀이

$i$번째 사람의 왼쪽 공석 자리 수는 $max(a[i-1], a[i])$이고 오른쪽 공석 자리 수는 $max(a[i], a[i+1])$이다. 모든 사람에 대해서 위 작업을 실행하고 필요한 의자 갯수를 구할 수 있다. 필요 의자 갯수를 최소로 하기 위해서 a를 정렬할 필요가 있다. (예: $a = [1, 2, 1, 4]$ 보다 $a = [1, 1, 2, 4]$의 경우에 필요한 의자 갯수가 적다.)

코드

def solve():
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    arr.sort()

    ans = 0
    for i in range(n):
        ans += 1 + max(arr[i-1], arr[i])

    if ans>m:
        return 0
    return 1


for __ in range(int(input())):
    print('YES' if solve() else 'NO')

C. Make it Increasing

길이가 $n$인 배열 $a$가 입력된다. 배열 $b$는 길이가 $n$이고 모든 원소가 $0$으로 초기화된 배열이다. 우리가 할 수 있는 작업은 두가지 있다.

1. $b[i]=b[i]-a[i]$
2. $b[i]=b[i]+a[i]$

위 작업을 사용해서 배열 $b$를 증가하는 배열로 만들어야 한다. 이때, 최소 작업 갯수를 구하라.

풀이

$n=5000$이라서 $O(N^2)$ 풀이로 풀면 된다. 결과 배열 $b$가 있다고 하면, $b[i]=0$을 만족하는 $i$는 항상 존재한다. $b[i]=0$이라고 가정하고 모든 $i$에 대해서 $b[1,...,i-1]$은 첫번째 작업을 적절히 해주고 $[i+1,...,n]$은 두번째 작업을 적절히 해주면 된다.

코드

def solve():
    n = int(input())
    arr = list(map(int, input().split()))

    ans = int(1e20)
    for i in range(n):
        cnt = 0
        now = 0
        for j in range(i+1, n):
            d = (now+arr[j])//arr[j]
            cnt += d
            now = d*arr[j]
        now = 0
        for j in range(i-1, -1, -1):
            d = (now+arr[j])//arr[j]
            cnt += d
            now = d*abs(arr[j])
        ans = min(ans, cnt)
    print(ans)


solve()

A는 너무 쉬웠고 B도 간단했는데 절고, C 못 풀어서 2솔 마무리

A. Optimal Path

가로 N, 세로 M 그리드가 주어진다. 가로 2, 세로 3 그리드라면, 아래와 그림과 같다. (1, 1)에서 (N, M)으로 가는 경로 중 숫자 합이 가장 작은 경로의 숫자 합은?

풀이

최적 경로는 다음과 같다. (1, 1) -> (1, M) -> (N, M)

코드

def solve():
    n, m = map(int, input().split())
    ans = sum(range(1, m+1)) + sum(range(2*m, n*m+1, m))
    print(ans)

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

B. Palindromic Numbers

길이가 $N$인 정수 $s$가 입력된다. 길이가 $N$인 정수 $a$를 구해야 한다. $a+s$는 펠린드롬이어야 한다. $a$의 첫번째 수는 $0$일 수 없다.

풀이

$s$의 첫번째 수가 $9$라면, $s+a$는 길이가 $n+1$이고 첫번째 수는 $1$이다. 간단하게 $a+s$를 $1$로 구성된 길이 $n+1$인 수라고 가정하면 $a$는 간단하게 구할 수 있다.

정당성 증명: $a[0] > 0$이므로 $a+s$는 반드시 길이 $n+1$이다. $a$와 $s$가 아무리 커도 두 수를 더했을 때, $a+s$의 첫번째 수는 반드시 $1$이다. $a+s$를 $1$로 구성된 길이 $n+1$인 수인 가정은 반드시 성립한다. 앞자리만 떼어놓고 생각하면, $s[0] = 9$, $(a+s)[:2] = 11$ 이다. $s[1]$은 최대 $9$이므로 $a$의 첫번째 수가 $1$보다 작아질 일이 없다.

$s$의 첫번째 수가 $9$가 아니라면, $a+s$를 $9$로 구성된 길이 $n$인 수라고 가정하면 된다.

정당성 증명: $s$가 $899$라고 해도 $a+s$가 $999$라서 $a$의 첫번째 수는 $1$이다.

코드

def solve():
    n = int(input())
    s = input()

    if s[0]=='9':
        print(int('1'*(n+1))-int(s))
    else:
        print(int('9'*n)-int(s))

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

C. Helping the Nature

길이가 $n$인 배열 $a$가 입력된다. 아래 세가지 작업을 최소한으로 사용해서 배열 내 모든 숫자를 $0$으로 만들어야 한다.

1. $i$를 정하고 $a[1,...,i]$ 값을 $1$씩 감소
2. $i$를 정하고 $a[i,...,n]$ 값을 $1$씩 감소
3. $a[1,...,n]$을 $1$씩 증가

풀이

스위핑 풀이:

$a$ 안에 있는 모든 숫자를 동일하게 만들어 줘야 한다. $a[x] < a[x+1]$라면, $a[x]$와 $a[x+1]$ 차만큼 2번째 작업$(i=x+1)$을 해주면 된다. $a[x] > a[x+1]$라면, $a[x]$와 $a[x+1]$ 차만큼 1번째 작업$(i=x)$을 해주면 된다. 위 작업을 다하고 나면, $a$의 모든 값이 하나의 값으로 통일되는데 그 값만큼 3번째 작업을 해주면 된다.

수학적 풀이:

$a$ 안에 있는 모든 숫자를 0 이상이 되도록 맞춰준다. $a$의 최솟값이 0보다 작다면, 3번 작업을 그 수의 절댓값만큼 적용한다. $a$의 모든 수가 0이상이므로, 우리가 할 일은 $a$의 수를 전부 0으로 만들어주는 거다. $a[i]$를 1 감소시키는 방법은 1번 작업을 i퀴리로 적용하고 2번 작업을 i쿼리로 적용하고 3번 작업을 하면 된다. 각 숫자에 대해서 위 작업을 해주면 되는데, 이 경우에 불필요한 작업이 발생하게 된다. 이 작업을 빼줘야 하는데, 1번 작업을 i쿼리로 하고 2번 작업을 i+1쿼리로 한 경우에 3번 쿼리까지 해주면 전체 원소를 1감소시켰다고 1증가시키는 거라 불필요한 작업이다. 이 경우를 세서 빼주면 된다.

코드

# 스위핑 풀이
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    ans = 0
    a, b = 0, 0 
    for i in range(n-1):
        ans += abs(arr[i]-arr[i+1]+b)
        t = min(arr[i], arr[i+1]-b)
        if arr[i] < arr[i+1]-b:
            b += abs(arr[i]-arr[i+1]+b)
        arr[i+1] = t
    print(ans+abs(arr[-1]))


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

# 수학적 풀이
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    dp = [[0]*2 for __ in range(n+1)]

    ans, cnt = 0, 0
    pmin = min(arr)
    if pmin < 0:
        cnt -= pmin
        for i in range(n):
            arr[i] -= pmin

    for i in range(n):
        dp[i][0] += arr[i]
        dp[i][1] += arr[i]
        cnt += arr[i]
    dp[-1] = [int(1e20)]*2

    for i in range(-1, n):
        pmin = min(dp[i][0], dp[i+1][1], cnt)
        cnt -= pmin
        dp[i][0] -= pmin
        dp[i+1][1] -= pmin

    ans = cnt
    for i in range(n):
        ans += sum(dp[i])
    print(ans)


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

AB는 무난하게 풀었는데, C에서 오래 걸렸다.. D는 시간 안에 풀이와 증명도 다 했는데, 인터렉티브 구현을 준비 안해놔서 포기. 요즘 코포 너무 안해서 감각 다시 살리는 중.. 나쁘진 않다.

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

풀이

해설

100 버추얼 챌린지를 시작했다. 이게 첫번째 버추얼이다. 버추얼은 퍼포를 어떻게 보는지 알 수가 없다. 그래서 그냥 몇 솔로 기록하려고 한다. 처음은 무난하게 3솔 했다. B, C를 dfs로 풀었는데, 파이썬 억까를 당해서 개같이 멸망했다.

A. Lex String

두 개의 문자열 a, b가 주어진다. 사전 순으로 가장 앞서는 문자열 c를 만들어라. Operation: a 또는 b에 있는 아무 문자열 하나를 빼고, c의 맨 뒤에 추가할 수 있다. 이 작업은 a나 b 한 문자열에 대해서 최대 k번 연속으로 할 수 있고, 한 문자열에서 k번 작업을 했으면 그 다음은 다른 문자열에서 작업을 실행해야 한다. a 또는 b 가 빌 때까지 위 작업을 계속한다.

풀이

문제에서 제시하는 그대로 하면 된다. a, b를 하나씩 쪼개서 스택에 넣고 사전 역순으로 정렬한다. a, b 스택 마지막 원소를 비교해서 사전 순으로 앞선 문자을 pop해서 c에 push 해주면 된다. k번 이상 동일 문자열에서 작업을 실행할 수 없으므로 잘 처리하면 된다. 난 귀찮아서 좀 길게 처리했지만, 더 똑똑한 방법이 있겠지.

코드

    n, m, k = map(int, input().split())
    a = list(input())
    b = list(input())

    a.sort(reverse=True)
    b.sort(reverse=True)

    c = ''

    cnt1, cnt2 = 0, 0
    while a and b:
        if a[-1] < b[-1]:
            if cnt1==k:
                c += b.pop()
                cnt1, cnt2 = 0, 1
            else:
                c += a.pop()
                cnt1 += 1
                cnt2 = 0
        else:
            if cnt2==k:
                c += a.pop()
                cnt1, cnt2 = 1, 0
            else:
                c += b.pop()
                cnt2 += 1
                cnt1 = 0

    print(c)

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

B. Mystic Permutation

길이가 n인 permutation이 주어진다. permutation은 1부터 n까지 중복이 없는 수가 나열된 거다. 우리가 할 일은 새로운 permutation을 만드는 건데, 주어진 permutation과 모든 위치에 대해 다른 값이어야 한다. 수식으로 표현하면, $p1≠q1, p2≠q2, …, pn≠qn$ 이고, $p_i, q_i$는 각각 주어진 permutation과 새로운 permutation이다. 위 조건을 만족하는 permutation 중에 사전 순으로 앞서는 걸 찾아야 한다.

풀이

간단한 dfs 문제라고 파악했다. (python으로 풀면서 억까 당할까봐 두려웠다,,) 너무 간단해서 자세한 설명은 생략하고, 에디토리얼 풀이도 추가로 정리해봤다.

코드

# 내 무지성 dfs 풀이
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr = [(arr[i], i) for i in range(n)]
    arr.sort()

    visited = [0]*1010

    def dfs(idx):
        if idx==n:
            return [0]

        for i in range(n):
            if not visited[i] and arr[i][1]!=idx:
                visited[i] = 1
                ret = dfs(idx+1)
                if ret!=[-1]:
                    return [arr[i][0]] + ret
                visited[i] = 0
        return [-1]


    ans = dfs(0)
    if ans[-1]==0:
        ans.pop()

    print(*ans)

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

에디토리얼은 반복문으로 풀었다. 실제로 이런 풀이 방식이 웰논 같은데 난 아직 무지성 dfs가 편한가보다,,, 1번째부터 n-2번째까지의 값을 구해준다. 이건 각 i번째 값을 구할 때, 1부터 n까지 탐색하며 아직 쓴 적이 없다면 i번째 값으로 바로 출력한다. 여기서 n-2번째까지 하는 이유가 있는데 n-2번째까지는 위 방식으로 하면 문제가 없다. 마지막 n-1과 n-2번째는 문제가 생길 수 있다.

# 에디토리얼의 예쁜 코드
def solve():
    n = int(input())
    arr = list(map(int, input().split()))

    if n==1:
        print(-1)
        return

    visited = [0]*1010

    for i in range(1, n-1):
        k = 1
        while visited[k] or arr[i-1]==k:
            k += 1
        print(k, end=' ')
        visited[k] = 1

    a, b = 0, 0
    for i in range(1, n+1):
        if not visited[i]:
            if a:
                b = i
            else:
                a = i

    if a==arr[n-2] or b==arr[n-1]:
        print(b, a)
    else:
        print(a, b)


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

마지막으로 $O(n)$ 짜리 풀이도 있다. 주어진 permutation과 [1, ..., n]으로 구성된 permutation을 비교하면서 swap해주는 방식이다. 이것도 마지막 원소에서 예외가 발생할 수 있어서 처리가 필요하다. 예시를 끄적여보면 알 수 있어서 패스,, (사실 다 쓰고 날라감)

// 에디토리얼의 O(n) 짜리 예쁜 코드
import sys
input = lambda : sys.stdin.readline().rstrip()


def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    brr = list(range(1, n+1))

    if n==1:
        print(-1)
        return

    for i in range(n-1):
        if arr[i]==brr[i]:
            brr[i], brr[i+1] = brr[i+1], brr[i]

    if arr[n-1]==brr[n-1]:
            brr[n-2], brr[n-1] = brr[n-1], brr[n-2]

    print(*brr)


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

C. Infected Tree

최상위 루트 노드가 1로 고정된 이진 트리가 주어진다. 노드 1은 감염된 상태이고 자식 노드로 감염은 이동한다. 1번에 1칸씩 감염이 진행되는데, 우리는 트리를 끊어서 감염을 멈춰야 한다. 최대한 많이 살릴 수 있는 노드 수를 구하라.

풀이

코드

D. Lena and Matrix

풀이

코드

A. Cirno's Perfect Bitmasks Classroom

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

$$$ x ,, and ,, y>0 \ x ,, xor ,, y>0 $$$

풀이

첫번째 조건을 만족하려면, $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()