Atcoder Beginner Contest 272 후기

A. Integer Sum

 길이가 n인 수열이 주어지고, 그 수열의 합을 구하는 문제이다

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
print(sum(arr))

 

B. Everyone is Friends

 n명의 사람이 있고, n명의 사람들이 각각 m개의 파티에 참여한 목록이 주어질 때 모든 쌍의 사람이 같은 파티에 참가하였는지를 출력하는 문제이다. n과 m 제한이 100으로 작기 때문에 간단히 브루트포스로 해결하면 된다

import sys

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

# cache : 파티 번호를 key, 그 때 참여한 사람들의 번호의 set을 value로 갖는 dictionary
cache = dict()
for i in range(m):
    _, *temp = list(map(int, sys.stdin.readline().split()))
    cache[i] = set(temp)
    
# vis : 같은 파티에 참여한 쌍을 저장하는 set
vis = set()
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        for k in cache:
            if i in cache[k] and j in cache[k]:
                vis.add((i, j))
                break
                
# 전체 쌍을 돌면서 정답 출력
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if (i, j) not in vis:
            print('No')
            sys.exit(0)
print('Yes')

 

C. Max Even

 길이가 n인 수열이 주어지고, 중복된 원소가 없는 경우 서로 다른 두 원소를 더해서 만들 수 있는 가장 큰 짝수를 구하는 문제이다. 만약 그런 수가 없다면 -1을 출력해야 한다. 두 홀수와 두 짝수의 합일 때만 더했을 때 짝수이기 때문에 짝수인지 홀수인지의 여부에 따라 수열을 나누고 각 경우를 확인하면 된다

import sys

# 입력부
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
odd = []
even = []
for i in arr:
    if i % 2 == 0:
        even.append(i)
    else:
        odd.append(i)
ans = -1
even.sort()
odd.sort()
# 두 짝수의 합이 가능한 경우
if len(even) > 1:
    ans = max(ans, even[-1] + even[-2])
# 두 홀수의 합이 가능한 경우
if len(odd) > 1:
    ans = max(ans, odd[-1] + odd[-2])
print(ans)

 

D. Root M Leaper

 n x n인 2차원 격자에서 처음에는 (0, 0)에 있고 한 번 이동할 때마다 $\sqrt{M}$의 거리를 정확히 만족하는 좌표로 이동한다고 할 때, 각 좌표에 도달하는 최소 거리를 출력하는 문제이다. 단순한 bfs 문제에서 이동 조건만 살짝 바꾼 문제이다. 현재 (x, y)에서 이동 조건을 만족하는 (a, b)로 간다고 하자. 이동 조건을 만족하기 때문에 $(x - a) ^ 2 + (y -b) ^ 2 = M$를 만족해야 한다. 이 때, (x - a)와 (y - b)를 각각 i와 j로 치환해보자. 그렇다면 $i ^ 2 + j ^ 2 = M$이 되어야 하고, M의 범위가 $10^6$이기 때문에, i와 j의 범위는 최대 $10^3$이 됨을 알 수 있기에 모든 (i, j) 쌍을 구할 수 있다. 

 그런데 이렇게 구한 i, j는 자연수이지만, 음수도 될 수 있음에 주의하여야 한다. 가령, i가 2인 경우라면 i는 원래 (x - a)이므로 a는 x + 2 혹은 x - 2가 될 수 있는 것이다. 따라서, 가능한 부호의 조건은 총 4가지가 되므로 이 부분까지 같이 고려한다면 한 번의 움직으로 갈 수 있는 좌표를 알 수 있기 때문에 이후 bfs로 문제를 풀 수 있다

import sys, collections

# 입력부
n, m = map(int, sys.stdin.readline().split())
val = int(m ** 0.5)

# d : 임의의 위치에서 갈 수 있는 거리쌍을 저장하는 set
d = set()
# temp : 거리쌍이 가질 수 있는 부호쌍을 저장하는 set
temp = [(1, 1), (-1, 1), (1, -1), (-1, -1)]
for i in range(val + 1):
    for j in range(val + 1):
        # 거리 조건을 만족하는 (i, j)의 경우
        if i ** 2 + j ** 2 == m:
            d.add((i, j))
            
# vis : 각 좌표에 대해 최소 거리를 저장하는 2차원 상태 공간 배열
vis = [[-1] * n for _ in range(n)]

# bfs
q = collections.deque()
vis[0][0] = 0
q.append((0, 0))
while q:
    x, y = q.popleft()
    for i in d:
        for j in temp:
            nx, ny = x + i[0] * j[0], y + i[1] * j[1]
            if 0 <= nx < n and 0 <= ny < n:
                if vis[nx][ny] == -1:
                    vis[nx][ny] = vis[x][y] + 1
                    q.append((nx, ny))
                    
# 정답 출력
for i in vis:
    print(' '.join(map(str, i)))

 

E. Add and Mex

 길이가 n인 수열이 주어지고, 각 원소의 위치만큼 더해주는 연산을 m번 하였을 때 각각의 연산마다 현재 수열이 포함하지 않은 음수가 아닌 정수 중 최소값을 출력하는 문제이다. 즉, 현재 수열이 [-3, -1, 4]이고 총 3번의 연산을 한다고 가정하면 첫번째 연산이 끝난 후 수열의 상태는 [-2, 1, 7]이 된다. 왜냐하면 -3은 첫번째 원소니까 1을 더하여 -2가 되고 -1은 두번째 원소니까 2를 더하여 1이 되고 마지막으로 4는 세번째 원소니까 3을 더하면 7이 된다. 따라서 두번째 연산을 하게 되면 [-1, 3, 10], 세번째 연산을 하게 되면 [0, 5, 13]이 된다. 따라서 정답으로는 0, 0, 1을 출력해야 한다.

 문제를 풀기 위해서는 2개의 직관이 필요하다. 첫번째로 음수 값에 대한 직관이다. 현재 수열이 [-1, -3, 1, 2, 4]라고 하자. 이 때 정답은 0이다. 그런데 [1, 2, 4]일 때도 마찬가지로 정답은 0이다. 따라서 음수값은 정답에 아무런 영향을 줄 수 없음을 알 수 있다. 두번째로 양수 값에 대한 직관이다. 현재 수열이 [-1, 0, 3, 7]이라고 하자. 첫번째 직관에 따라 우리는 수열을 [0, 3, 7]로 생각해도 좋다. 이 때 정답은 1이 된다.

 여기서 좀 더 확장해보면 길이가 3일 때 원소값이 3보다 큰 원소 역시 정답에 아무런 영향을 줄 수 없다. 현재 정답이 만일 k라면, 그 말은 결국 현재 수열에는 0이상 k미만의 수가 있다는 뜻이 된다. 다만, k초과의 수는 있을수도 있고 없을수도 있다. 그런데 0부터 k미만의 수의 갯수가 하나씩 있는 경우라면 총 k+1개의 원소가 있다는 의미이고 이것이 전체 수열의 길이를 초과할 수는 없다. 따라서 k의 범위는 0이상 n이하가 된다. 따라서, n을 초과하는 수는 사실상 아무런 의미가 없다. 왜냐하면 현재 수열의 길이가 n이고 n을 초과하는 수를 뻈을 때 전체 수열의 길이가 n-1이 되기 때문에 빠진 한자리에 해당하는 수가 정답이 되기 때문이다.

 또한 각각의 연산에 대해 정답에 아무런 영향을 주지 못하는 수를 제외했을 때 남는 원소의 수는 많아봤자 $N, \left \lceil \frac{N}{2}\right \rceil, \left \lceil \frac{N}{3}\right \rceil, \cdots$로 조화급수의 꼴이 된다. 따라서 실제로 브루트포스를 진행하여도 $O(N\log N)$만에 모든 경우를 구할 수 있다.

import sys, math

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

# cache : 각 연산 시점을 key, 그 때의 배열 중 0이상 n이하의 원소들의 set을 value로 가지는 dictionary
cache = dict()
for i in range(1, m + 1):
    cache[i] = set()
for i in range(n):
    # n을 초과하는 원소는 정답에 영향을 줄 수 없다
    if arr[i] > n:
        continue
    # left : 현재 원소가 최초로 0 이상이 되는 시점으로 원래 양수인 경우는 1로 초기화
    left = 1 if arr[i] >= 0 else math.ceil(-arr[i] / (i + 1))
    # right : 현재 원소가 마지막으로 n 이하가 되는 시점
    right = math.ceil((n - arr[i]) / (i + 1))
    # cache에 각 시점별 원소를 추가한다
    for j in range(left, min(m + 1, right)):
        cache[j].add(arr[i] + (i + 1) * j)
        
# 각 연산 시점 별로 정답을 출력
for i in range(1, m + 1):
    for j in range(n + 1):
        if j not in cache[i]:
            print(j)
            break

 

 후기 : A~D까지는 30분 안에 풀었으나 E번에서 성질을 캐치하지 못하여 대회 중에는 풀지 못하였다. 업솔빙을 해도 도저히 감이 오질 않아서 에디토리얼을 보았는데 상당히 직관적인 접근법과 수학적인 명료함에 감탄했다.. 아무리 생각해도 브루트포스나 dp류의 문제는 아닌거 같아서 그리디쪽으로 생각을 많이 했는데 브루트포스로 풀려서 조금 당황하면서도 재미있었다. E번을 대회안에 풀 수 있도록 노력해야겠다.