Atcoder Beginner Contest 270 후기

A. 1-2-4 Test

 1점 문제, 2점 문제, 4점 문제로 이루어진 3개의 문제집에서 A와 B가 각각 득점한 점수를 x, y점이라고 할 때 C는 A와 B 중 한명이라도 맞춘 문제는 무조건 맞춘다고 가정하면 C의 점수는 몇 점이 되는지를 묻는 문제이다. 예를 들어 A가 6점, B가 3점이라고 하자. 그렇다면 A는 4점 문제 하나와 2점 문제 하나를 맞춘 셈이다. 같은 논리로 B 역시 2점까지 문제 하나와 1점짜리 문제 하나를 맞춘 셈이다. 따라서, C는 3문제를 모두 맞추므로 C의 점수는 총 7점이 된다

import sys

a, b = map(int, sys.stdin.readline().split())
t = {4 : False, 2 : False, 1 : False}
ao = {4 : False, 2 : False, 1 : False}
for i in t:
    if a - i >= 0:
        t[i] = True
        a -= i
for i in ao:
    if b - i >= 0:
        ao[i] = True
        b -= i
ans = 0
for i in [1,2,4]:
    if not t[i] and not ao[i]:
        continue
    ans += i
print(ans)

B. Hammer

 현재 수직선 상의 원점에 위치하고, 목적지의 위치가 X, 벽의 위치를 Y, 망치의 위치를 Z라고 하자. 만일 목적지에 도달하기 전에 벽을 만난 경우 망치를 획득하면 벽을 부수고 이동할 수 있다. 이 때 목적지 X까지 가기 위해 얼마나 이동해야하는지 구하는 문제이다. 단, 목적지까지 도달하는 것이 불가능한 경우 -1을 출력하면 된다

 X, Y, Z 모두 양수 혹은 음수가 될 수 있기 때문에, 방향성을 고려해야 한다. 첫번째로 X, Y의 방향이 반대인 경우라면 굳이 망치를 획득하지 않아도 되므로 단순히 X까지 거리가 답이 된다.

 하지만 방향성이 같다면 위치 조건에 따라 답이 갈리게 된다. 가장 명확한 것은 벽을 만나기 전에 망치를 획득할 수 없다면 절대로 목적지 까지 갈 수 없다는 점이다. 또한 벽을 만나기 전에 목적지에 도달할 수 있는 경우도 명확한데, 이 경우 역시 망치를 획득할 필요가 없기 때문에 단순히 X까지의 거리가 답이 된다. 두 경우가 아니라면 충분히 목적지까지 갈 수 있으나, 예를 들어 X와 Y가 양수이고 Z가 음수인 경우를 생각하면 실제 거리는 원점에서부터 Z까지의 거리와 Z부터 X까지의 거리의 합이다. 반대로 X, Y, Z 모두 양수인 경우라면, 단순히 X까지의 거리가 답이 된다

import sys

x, y, z = map(int, sys.stdin.readline().split())
if x * y > 0:
    if x > 0:
        if y < x:
            if z < 0:
                print(abs(2 * z) + abs(x))
            elif z < y:
                print(abs(x))
            else:
                print(-1)
        else:
            print(abs(x))
    else:
        # 둘 다 음수인 경우는 둘 다 양수인 경우와 부등호가 반대됨에 주의
        if y > x:
            if z > 0:
                print(abs(2 * z) + abs(x))
            elif z > y:
                print(abs(x))
            else:
                print(-1)
        else:
            print(abs(x))
else:
    print(abs(x))

C. Simple path

 트리가 주어질 때, 입력으로 주어지는 두 정점의 경로를 구하는 문제이다. 단순하게 bfs나 bfs로 구할 수 있다

import sys, collections

def go():
    q = collections.deque()
    q.append(x)
    vis[x] = True
    while q:
        now = q.popleft()
        for next in adj[now]:
            # 방문하지 않은 경우 방문 여부와 이전 정점 갱신
            if not vis[next]:
                vis[next] = True
                path[next] = now
                q.append(next)

# 입력부
n, x, y = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    adj[a].append(b)
    adj[b].append(a)
    
# vis : 방문 여부를 저장하는 배열
vis = [False] * (n + 1)
# path : 현재 정점을 오기전에 방문한 정점을 저장하는 배열
path = [-1] * (n + 1)
go()

# 정답 출력
ans = []
temp = x
while path[y] != -1:
    ans.append(y)
    y = path[y]
ans.append(temp)
print(' '.join(map(str, ans[::-1])))

D. Stones

 총 n개의 돌이 주어지고, 플레이어가 2명일 때 각각 한 차례에 $1 \leq A_1 \leq A_2 \cdots  \leq A_k \leq N$의 k개의 원소 중 임의의 $A_i$개의 돌을 뺄 수 있다고 하자. 이 때 각 플레이어는 게임이 끝나기 전까지 자신이 뺀 돌의 갯수를 최대화하도록 플레이한다고 할 때, 첫번째로 시작한 플레이어가 뺀 돌의 갯수를 구하는 문제이다. 얼핏 보면 그리디 알고리즘으로 풀 수 있겠다고 생각할 수 있지만 다음과 같은 반례가 있다 $$\left\{\begin{matrix}
 n, k = 25, 4\\ arr = [1,6,13,15]
\end{matrix}\right. $$

 위 반례는 그리디 알고리즘으로는 17이 답으로 나오지만, 실제로 정답은 19이다. 그리디하게 뽑는 경우라면 첫번째 플레이어는 15, 1, 1의 순서대로 돌을 뽑을 것이며, 마찬가지로 두번째 플레이어는 6, 1, 1의 순서로 돌을 뽑을 것이다. 하지만, 실제로는 첫번째 플레이어는 13, 6의 순서대로 돌을 뽑을 것이며, 두번째 플레이어는 6의 순서로 돌을 뽑는다.

 따라서, 이 문제의 정해는 다이나믹 프로그래밍이라고 생각한다. 상태공간을 현재 now개의 돌이 남아있고 status번째 플레이어가 돌을 뽑을 때, 플레이어가 얻을 수 있는 돌의 수의 합의 최대값이라고 정의하자. 따라서, 상태공간의 정의를 잘 생각해보면, 점화식은 어렵지 않게 구할 수 있다.

 우선 현재 돌의 수가 now이고 첫번째 플레이어가 플레이하는 상황을 생각해보자. 그렇다면 뽑을 수 있는 돌의 양은 어렵지 않게 생각할 수 있다. 그 중 하나를 $A_i$라고 하자. 그렇다면 뽑고 남은 돌은 얼마인가? 어렵지 않다. $now - A_i$이다. 이후의 상황은 어떻게 될까? 이 역시 어렵지 않게 유추할 수 있다. 상태공간의 정의에 따라, $dp[now - A_i][1 - status]$가 된다. 그런데 $dp[now - A_i][1 - status]$에 들어있는 값은 결국 첫번째 플레이어가 아닌 두번째 플레이어가 가지는 최대값이 된다. 그런데 생각해보면 두번째 플레이어가 어떻게 뽑는다고 하여도, 결국 남은 돌의 수가 $now - A_i$인 상황에서 첫번째 플레이어와 두번째 플레이어가 최적의 전략으로 플레이를 한다고 할지라도 두 플레이어가 뽑은 돌의 수를 합하면 결국 $now - A_i$가 된다.

따라서 점화식은 아래와 같다.

$$ dp[now][status] = max(dp[now][status], A_i + (now - A_i - dp[now - A_i][1 - status]))\\ = max(dp[now][status], now - dp[now - A_i][1 - status]), \ where \ now - A_i \geq 0$$

import sys

sys.setrecursionlimit(200000)

# go : 현재 수가 now이고 status번째 플레이어 차례일 때 최적의 플레이를 할 경우 
#      얻을 수 있는 돌의 최대값을 리턴하는 함수
def go(now, status):
    # Base Case : 모든 돌을 뺀 경우
    if now == 0:
        return 0
    # Memoization
    if dp[now][status] != -1:
        return dp[now][status]
    dp[now][status] = 0
    # Recursive Case : 점화식
    for i in range(k):
        if now - arr[i] >= 0:
            dp[now][status] = max(dp[now][status], now - go(now - arr[i], 1 - status))
    return dp[now][status]

# 입력부
n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

# dp : 현재 수가 now이고 status번째 플레이어 차례일 때 최적의 플레이를 할 경우 
#      얻을 수 있는 돌의 최대값을 저장하는 2차원 상태 공간 배열
dp = [[-1] * 2 for _ in range(n + 1)]
print(go(n, 1))

 

E. Apple Baskets on Circle

 n개의 원소가 원형으로 연결된 리스트가 있고, 원소가 1 이상이라면 1을 감소시키고 오른쪽으로 계속 이동한다. 마지막 원소에 도달한 경우라면 다시 첫번째 원소로 돌아오는 것을 반복할 때, 총 K번의 감소를 한 이후 리스트의 원소 상태를 출력하는 문제이다. n은 최대 $10^5$, K는 $10^12$이므로 브루트 포스로 접근한다면 시간 초과를 피할 수 없음은 자명하다. 

개인적으로 이 문제의 풀이는 수학적 사고와 적절히 suffix_sum을 조합하는 것이라고 생각한다.

<그림 1. [2, 3, 6, 7] 중 2를 소진하는 경우>

 위 그림 1은 임의의 배열 [2,3,6,7] 중 2를 소진하는 경우를 나타낸 그림이다. 이 때 "소진하다"라는 정의는 2가 최초로 0이 되는 것을 의미하는 것이 아니라, 0이 되었지만 모든 차감할 수 있는 모든 원소는 마지막 원소까지 차감하는 것을 의미한다. 그렇다면 3을 소진한 이후의 리스트는 어떻게 되는가?

<그림 2. [2, 3, 6, 7] 중 3을 소진하는 경우>

 위 그림 2는 3을 소진한 경우의 리스트를 나타낸 그림이다. 결과적으로 [0, 0, 3, 4]가 됨을 알 수 있다. 순차적으로 6을 소진하는 경우, 리스트는 [0, 0, 0, 1]이 되며 마지막으로 7을 소진하는 경우는 [0, 0, 0, 0]이 된다. 각 원소를 소진할 때마다 몇 번의 차감이 이루어질까? 2를 소진할 때는 8번, 3을 소진할 때는 3번, 6을 소진할 때는 6번, 7을 소진할 때는 1번의 차감이 이루어진다.

 그렇다면, 2를 소진할 때 3, 6, 7은 각각 몇번의 차감이 이루어질까? 각각 4번이 이루어짐을 알 수 있다. 3을 소진할 때 6, 7은 각각 몇번의 차감이 이루어질까? 각각 1번이 이루어짐을 알 수 있다.

<그림 3. 각 원소 소진 시 결과 일반화>

 위 그림 3에서는 각 원소를 소진 시 남은 원소들의 변동을 나타내는 그림이다. 각 원소를 key, 원소의 출현 빈도를 value로 하는 dictionary를 cache라고 정의하자. 이 때 cache의 키값은 오름차순으로 정렬되어있다고 가정하자. 이 때, cache의 key값의 마지막부터 빈도 수를 더해나가면 간단히 suffix_sum을 얻을 수 있다. 단, 그림 3에서의 suffix_sum의 아래 첨자 숫자들은 실제 인덱스가 아님을 주의한다. 따라서, 첫번째 소진이 이루어지면 총 차감 횟수는 2 * suffix_sum[2] = 2 * 4 = 8이 되고, 두번째 소진이 이루어지면 총 차감 횟수는 (3 - 2) * suffix_sum[3] = 1 * 3 = 3이 되며 세번째 소진이 이루어지면 총 차감 횟수는 (6 - 3) * suffix_sum[6] = 3 * 2 = 6번, 마지막 소진이 이루어지면 (7 - 6) * suffix_sum[7] = 1 * 1 = 1이 된다. 현재 key의 바로 전 key값을 빼주면서 계산해야 하는 이유는 앞의 key를 소진한 결과를 반영하기 위함이다.

 이렇게 하게 되면 브루트 포스를 하지 않고도 K를 줄일 수 있다. 왜냐하면 각 원소들마다 총 소진되는 횟수를 더해나가다 보면 반드시 K 이상이 되는 부분이 존재하기 때문이다. 가령, 위 그림 3의 예시에서 만약 K가 12였다면, 2와 3을 소진해도 전체 소진 횟수는 11이기에 6을 소진하는 과정에서 K를 모두 소진하는 것이다.

 따라서, 현재 원소를 소진하였을 때 K 이상이 된다면 사실상 현재 원소 이전의 원소는 전부 0이 됨은 자명하다. 누적 차감 횟수가 K 이상인 원소를 모두 제거하면 K보다 많이 차감할 수 있으므로, 누적 차감 횟수가 K 이상인 원소에서는 직접 차감해주면 된다

 단, 여기서도 브루트 포스를 하게 되면 시간초과를 피할 수 없기 때문에 약간의 트릭이 필요하다. 현재 원소를 소진하려하는 시점에서 원소값이 0이 아닌 원소들의 갯수를 파악한 후, 남은 차감 횟수의 몫만큼 각 원소를 차감시킨 다음, 나머지만을 실제로 브루트 포스해주면 시간안에 정답을 구할 수 있다

import sys

# 입력부
n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

# temp : arr의 원소를 key, 원소의 빈도값을 value로 갖는 dictionary
temp = dict()
for i in arr:
    if i == 0:
        continue
    if i not in temp:
        temp[i] = 0
    temp[i] += 1
    
# sf : temp의 key를 오름차순으로 정렬하였을 때의 suffix sum을 저장하는 배열
sf = [0] * len(temp)
key = sorted(temp.keys())
for i in range(len(key)):
    val[i] = key[i]
    
# suffix sum을 채움
sf[-1] = temp[key[-1]]
size = len(key)
for i in range(size - 2, -1, -1):
    sf[i] = sf[i + 1] + temp[key[i]]
    
# 첫번째 key는 이전 key가 없기 때문에 0을 추가
# 파이썬에서 -1 인덱스는 list의 끝 원소를 가리킴
key.append(0)

# now : 누적 차감 횟수가 K이상인 원소값
now = -1
# s : 누적 차감 횟수가 K이상인 원소값 직전의 원소값
s = 0
for i in range(len(key)):
    if k - (key[i] - key[i - 1]) * sf[i] <= 0:
        now = key[i]
        break
    else:
        k -= (key[i] - key[i - 1]) * sf[i]
        s = key[i]
        
# now보다 작은 원소값은 0으로 처리
# now이상의 원소값은 s만큼 감소
for i in range(n):
    if arr[i] < now:
        arr[i] = 0
    else:
        arr[i] -= s
        
# cnt : 현재 arr에서 1 이상의 원소의 갯수
cnt = 0
for i in arr:
    if i > 0:
        cnt += 1
        
# 남은 차감 횟수를 차감
a, b = k // cnt, k % cnt
for i in range(n):
    if arr[i] > 0:
        arr[i] -= a
if b:
    for i in range(n):
        if b <= 0:
            break
        if arr[i] > 0:
            arr[i] -= 1
            b -= 1
            
# 정답 출력
print(' '.join(map(str, arr)))

 후기 : 이번에는 꽤 과거의 대회를 버추얼로 풀어보았다. D번에서 막혀서 꽤나 고생했다. 더군다나 게임 dp의 경우 반례를 찾는게 쉽지 않아서 시간을 굉장히 많이 쏟았지만 결국 버추얼시에 풀지는 못하고 업솔빙으로 풀게 되었다. E번도 atcoder problems의 난이도 확인 결과 D번과 크게 다르지 않아서 업솔빙을 하였는데 생각보다 빨리 풀렸다. 확실히 우아한테크코스 생활을 하면서 PS를 거의 챙기지 못했기에 앞으로도 꾸준히 버추얼을 참여해야겠다.