AtCoder Beginner Contest 239 후기

A. Horizon

 매우 단순한 문제. 단순히 주어진 공식에 입력을 대입하면 된다

import sys
 
x = float(sys.stdin.readline())
print((x * (12800000 + x)) ** 0.5)

 

B. Integer Division

 역시 문제에서 주어지는 공식에 입력을 대입하면 된다

import sys, math
 
x = int(sys.stdin.readline())
print(x // 10)

 

C. Knight Fork

 약간의 관찰이 필요한 브루트포스 문제이다. 현재 점을 $(a, b)$라고 할 때, $(x_1, y_1)$에 대해 거리가 $\sqrt5$가 되는 경우는 $a$가 $x_1$의 절댓값과 차이가 2만큼 나고, $b$가 $y_1$의 절댓값과 차이가 1만큼 나는 경우거나, $a$가 $x_1$의 절댓값과 차이가 1만큼 나고, $b$가 $y_1$의 절댓값과 차이가 2만큼 나는 경우이다. 왜냐하면 $(a, b)$는 정수로 이루어진 좌표이기 때문이다. 이 때, 각 경우에 대해 $(a, b)$와 $(x_2, y_2)$의 거리가 $\sqrt5$가 되는지 확인하면 된다. 

import sys
 
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
dx = [2, 2, -2, -2, 1, 1, -1, -1]
dy = [1, -1, 1, -1, 2, -2, 2, -2]
find = False
for i in range(8):
    a, b = x1 + dx[i], y1 + dy[i]
    if (a - x2) ** 2 + (b - y2) ** 2 == 5:
        find = True
        break
print('Yes' if find else 'No')

 

D. Prime Sum Game

 자칫 게임 DP로 풀기 쉽지만, 전형적인 브루트포스 문제이다. 입력값 제한이 매우 작은 점과 게임의 차례가 2번밖에 일어나지 않기 때문이다. 따라서, 간단한 2중 for문으로 해결가능하다.

import sys

# is_prime : 현재 num이 소수인지 아닌지 리턴하는 함수
def is_prime(num):
    for k in range(2, int(num ** 0.5) + 1):
        if num % k == 0:
            return False
    return True

# 입력부
a, b, c, d = map(int, sys.stdin.readline().split())

# arr : i번째 수를 골라서 Takahashi가 이기면 True, 아니면 False를 저장하는 배열 
arr = [True] * 101

# 브루트포스
for i in range(a, b + 1):
    for j in range(c, d + 1):
        if is_prime(i + j):
            arr[i] = False
            
taka = False
for i in range(a, b + 1):
    # 만일 Takahashi가 고를 수 있는 숫자 중 하나라도 이길 수 있는 수가 있다면 Takahashi 승리
    if arr[i]:
        taka = True
        
# 정답 출력
print('Takahashi' if taka else 'Aoki')

 

E. Subtree K-th Max

 문제에서 K의 제한이 최대 20이기 때문에 DFS를 통해 각 서브트리의 값을 20개만 저장하면 쉽게 정답을 구할 수 있다. 이번 대회에서 가장 아쉬운 문제였는데, 생각보다 간단한 풀이에 비해 스스로 생각을 복잡하게 만들어서 시간을 많이 썼기 때문이다. 

import sys

# 재귀깊이 해제
sys.setrecursionlimit(200000)

# dfs : 현재 정점을 now, 이전 정점을 past로 할 때 now의 서브트리 중 최대 20개의 값을 저장하는
#       한 리스트를 리턴하는 함수
def dfs(now, past):
    # 방문 체크
    vis[now] = True
    # 자기자신은 반드시 포함시켜야 하므로 추가
    res[now].append(arr[now])
    for i in adj[now]:
        # 만일 자신의 부모 노드인 경우면 continue
        if i == past:
            continue
        # 이미 방문한 노드의 경우면 continue
        if vis[i]:
            continue
        res[now] += dfs(i, now)
        
    # 정렬 후 최대 20개만 저장
    res[now].sort(reverse=True)
    res[now] = res[now][:min(20, len(res[now]))]
    return res[now]

# 입력부
n, q = map(int, sys.stdin.readline().split())
arr = [-1] + list(map(int, sys.stdin.readline().split()))

# adj : 인접 리스트
adj = [[] for _ in range(n + 1)]

# vis : 방문 체크 배열
vis = [False] * (n + 1)

# res : i번째 정점의 서브트리의 값을 최대 20개 저장하는 이차원 배열
res = [[] 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)
    
# 전처리
dfs(1, 0)

# 쿼리 별 정답 출력
for _ in range(q):
    v, k = map(int, sys.stdin.readline().split())
    print(res[v][k - 1])

 

총평 : 매우매우 오랜만에 한 대회치고는 E번을 푸는 선방을 했으나 시간 관리가 아쉬웠음. 개인적으로 평소의 D,E 보다 쉬운 느낌. 오랜만에 했으나 한창 할 때보다 등수가 좋게 나와 혼란스러웠고 Unrated로 등록한게 아쉬웠다

 

## 2022. 03. 04 추가

 

F. Construct Highway

 업솔빙 문제. 큰 맥락은 정해에 가까웠으나 세부사항을 놓쳐 계속 WA를 받아서 에디토리얼을 봤다. 내가 놓쳤던 부분은 은 같은 연결 요소끼리 재연결을 하지 말아야 한다는 점이다. 에디토리얼의 예시 코드를 봐도 자력으로 구현하는 것은 힘들어보여 같은 파이썬 유저의 코드를 참고하여 작성하였다. 보면서 깔끔한 구현에 감탄을 했다.. 특히 핵심적으로 트리를 만들어주는 부분의 코드를 이해하는 것이 중요하다고 생각한다

<그림 1. N = 6, M = 3인 예시>

 위 그림 1에서 1,2,3과 4,5는 각각 트리를 형성하고 있다. 이 때 만일 1,2,3,4,5,6이 전체가 트리가 되야 하고 3의 차수는 3, 6의 차수는 2, 5의 차수가 2가 되려면 어떻게 해야 할까? 이미 자기 자신을 제외한 연결 요소가 있는 3은 이미 2개의 선분이 연결되어 있기 때문에 실질적으로 필요한 차수는 1이 된다. 정점 5의 경우도 마찬가지이다. 이 때 만일 자신이 속한 연결 요소의 임의의 한 정점과 연결된다면 반드시 사이클을 형성하게 되고, 전체는 트리가 될 수 없음은 자명하다. 추가적으로 입력으로 만들어지는 서브그래프(위 그림 기준 1,2,3과 4,5)에 사이클이 주어질 수도 있으므로 이를 체크해야 한다

<그림 2. N = 6, M = 3인 예시>

 위 그림 2는 전체를 트리로 형성하는 과정 중 일부를 나타내는 그림이다. 그림 1에서 "같은 연결요소 끼리는 연결되어서는 안된다"라는 명제를 얻었기 때문에 서로 다른 연결 요소에 속하는 6과 5를 연결해야 한다. 물론 6과 3을 연결해도 상관없다. 이어진 두 정점은 서로 같은 연결 요소가 된다

<그림 3. N = 6, M = 3인 예시>

 위 그림 3은 최종적으로 전체가 트리가 되는 모습을 나타내는 그림이다. 그림 2에서의 과정의 반복이 된다. 따라서, 일반화를 하면 실질적으로 이어야 하는 정점이 1이상인 정점들을 연결 요소를 기준으로 모은 후 실질적 차수가 2 이상인 정점들에 대해 실질적 차수가 1인 정점들을 연결해주는 것을 반복하면 된다. 최종적으로는 실질적 차수가 1인 정점 2개만 남아야 문제에서 요구하는 차수를 만족하는 트리를 만들 수 있다. 만일, 그렇지 않다면 문제에서 요구하는 차수를 만족하는 트리를 만들 수 없으므로 -1을 출력하면 된다.

 또한 애초에 모든 차수를 더했을 때 2(N - 1)이 되지 않으면 트리의 정의에 만족하지 않기 때문에 -1을 출력해야 한다.

 

import sys
# 재귀깊이 해제
sys.setrecursionlimit(200000)

# find : 현재 정점의 부모 정점을 리턴하는 함수
def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

# union : 임의의 두 정점 x, y를 하나의 공통 부모로 합치는 함수
def union(x, y):
    x, y = find(x), find(y)
    parent[y] = x

# 입력부
n, m = map(int, sys.stdin.readline().split())
arr = [-1] + list(map(int, sys.stdin.readline().split()))

# total : 전체 차수의 합
total = 0
for i in range(1, n + 1):
    total += arr[i]
parent = [i for i in range(n + 1)]

# one : 추가해야하는 차수가 1인 정점들을 모은 리스트
one = []
# not_one : 추가해야하는 차수가 2이상인 정점들을 연결 요소 별로 모은 2차원 리스트
not_one = []
# ans : 정답 배열
ans = []
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    # 이미 입력으로 주어진 정점은 차수를 감소
    arr[a] -= 1
    arr[b] -= 1
    # 사이클 형성 시 트리 생성 불가능
    if find(a) == find(b):
        print(-1)
        sys.exit(0)
    # 그것이 아니라면 두 정점을 이어준다
    union(a, b)
    
# 만약 전체 간선의 갯수가 n-1개가 아니라면 무조건 트리가 아니므로 -1 출력
if total != 2 * (n - 1):
    print(-1)
    sys.exit(0)
    
# temp : 연결 요소 번호 별로 정점들을 저장한 2차원 리스트
temp = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
    # 만약 추가해야할 간선이 남은 정점이라면
    if arr[i] > 0:
        # 추가해야하는 간선 수 만큼 정점을 추가
        for j in range(arr[i]):
            temp[find(i)].append(i)
            
for i in range(1, n + 1):
    if temp[i]:
    	# 만약 실질적 차수가 1이라면 one에 추가
        if len(temp[i]) == 1:
            one.append(temp[i][0])
        # 만약 실질적 차수가 2이상이라면 not_one에 "연결 요소"를 추가
        else:
            not_one.append(temp[i])
            
for i in not_one:
	# 실질적 차수가 하나만 남은 정점의 갯수가 
    # 현재 연결 요소의 정점들의 갯수에서 하나 뺀 갯수보다 더 작으면
    # 절대로 조건을 만족하는 트리를 만들 수 없으므로 -1 출력
    if len(one) < len(i) - 1:
        print(-1)
        sys.exit(0)
    # 실질적 차수가 하나만 남은 정점들을 차례대로 연결
    for j in range(len(i) - 1):
        ans.append((one.pop(), i[j]))
    # 남은 정점의 남은 차수는 1이므로 one에 추가
    one.append(i[-1])
    
# 마지막 두 정점이 남았다면 정답 출력
if len(one) == 2:
    ans.append((one[0], one[1]))
    for i in ans:
        print(i[0], i[1])
        
# 그게 아니라면 불가능한 경우이므로 -1 출력
else:
    print(-1)