Atcoder Beginner Contest 252 후기

A. ASCII code

 특정 숫자(아스키 코드)를 문자로 변환하는 문제이다

import sys

n = int(sys.stdin.readline())
print(chr(n))

 

B. Takahashi's Failure

 단순한 구현문제이다. 특정 수열의 최대값들 중에서 특정 인덱스에 속하는 최대값이 있는지만 확인하면 된다

import sys

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

# val : 수열의 최대값
val = max(arr)

# flag : Takahashi가 싫어하는 음식을 먹을 수 있는 경우가 없다면 False, 있다면 True인 플래그 변수
flag = False
for idx, i in enumerate(arr):
    # 현재 수가 최대값인 수인 경우
    if i == val:
    	# 현재 수의 인덱스가 싫어하는 음식의 인덱스인 경우
        if idx + 1 in temp:
            flag = True
            
# 정답 출력
print('No' if not flag else 'Yes')

 

C. Slot Strategy

 특정 시간 t마다 임의의 슬롯을 하나 정하여 버튼을 누르면 $(t % 10) + 1$번째의 숫자가 화면에 뜬다. 이 때 모두 같은 숫자가 화면에 뜨게 할 수 있는 경우 중 가장 적은 시간이 얼마인지 묻는 문제이다. 전형적인 그리디 문제이다. 현재 시간이 t라고 하고, 특정 숫자 k로 모두 맞추고 싶을 때, 각 슬롯에서 k의 인덱스가 공식에 따라 맞출 수 있다면 해당 슬롯을 누르면 되고, 그런 슬롯이 하나도 없다면 더 기다려야 한다

import sys

n = int(sys.stdin.readline())
arr = []

# cache : 특정 수를 key, 각 슬롯에서 특정 수의 인덱스 리스트를 value로 갖는 dictionary
cache = dict().fromkeys([i for i in range(10)])

# vid : 특정 수를 key, 각 슬롯을 방문했는지를 나타내는 boolean 리스트를 value로 갖는 dictionary
vis = dict().fromkeys([i for i in range(10)])

# 초기화
for i in cache:
    cache[i] = []
    vis[i] = []
    
for i in range(n):
    temp = sys.stdin.readline().rstrip()
    for j in range(len(temp)):
        # 각 숫자에 해당하는 key에 인덱스 추가
        cache[int(temp[j])].append(j + 1)
        # 각 숫자에 해당하는 슬롯을 아직 방문하지 않았으니 False 추가
        vis[int(temp[j])].append(False)
        
ans = []
# 초기 숫자를 고른다
for i in range(10):
    now = 0
    idx = 0
    while True:
    	# 모든 슬롯을 다 방문했다면 무한루프 탈출
        if vis[i] == [True] * len(cache[i]):
            break
        for j in range(len(cache[i])):
            # 아직 방문하지 않은 슬롯이 있는 경우
            if not vis[i][j]:
            	# 현재 시간에서 방문하면 특정 숫자를 띄울 수 있는 경우
                if cache[i][j] == (now % 10) + 1:
                    # 방문 체크
                    vis[i][j] = True
                    break
        now += 1
        
    # 각 초기숫자 별 결과 저장
    ans.append(now)
    
# 정답 출력
print(min(ans) - 1)

 

D. Distinct Trio

 특정 수열이 주어지고, 아래와 같은 조건을 만족하는 인덱스의 세 쌍을 구하는 문제이다

$$\begin{cases}
 &  1 < i < j < k \leq N \\
 &  A_i, A_j, A_k \text{ are distinct}
\end{cases}$$

 $A_i, A_j, A_k$가 모두 다른 수인 경우를 구해야 하므로, 전체 경우의 수에서 겹치는 경우의 수를 빼주면 문제를 풀 수 있다. 이 때, 겹치는 경우의 수는 세 수가 모두 같거나, 두 수만 같은 경우이다. 따라서, 특정 수가 몇 개 있는지만 저장하는 자료구조가 필요하다. 세 수가 모두 같은 경우라면 단순히 특정 수의 총 갯수에서 3개를 뽑으면 된다. 마찬가지로 두 수가 같은 경우라면 단순히 특정 수의 총 갯수에서 2개를 뽑고, 다른 수에서 하나만 뽑으면 된다. 

import sys

# calc : nCr을 리턴하는 함수, 이때 num이 n, times가 r이 된다
def calc(num, times):
    if times == 3:
        return max(0, num * (num - 1) * (num - 2) // 6)
    if times == 2:
        return max(0, num * (num - 1) // 2)
    return num

n = int(sys.stdin.readline())

# total : 전체 인덱스에서 아무거나 3개를 뽑을 때 발생하는 경우의 수
total = calc(n, 3)
arr = list(map(int, sys.stdin.readline().split()))

# res : arr의 원소값을 key, 그때의 총 원소 갯수를 value로 갖는 dictonary
res = dict().fromkeys(arr, 0)

# 갯수에 따라 갱신
for i in arr:
    res[i] += 1
    
for i in res:
    # 현재 원소가 수열에서 2번 이상 나온 경우
    if res[i] >= 2:
    	# 두 수가 겹치는 경우를 제외
        total -= calc(res[i], 2) * (n - res[i])
        # 세 수가 모두 겹치는 경우를 제외
        total -= calc(res[i], 3)
        
# 정답 출력
print(total)

 

E. Road Reduction

 업솔빙 문제이다. 이후 생각을 많이 했지만 풀이가 떠오르지 않아 에디토리얼을 보았다. 정해는 단순했다. 정점 1에서 시작하여 각 정점의 최단 경로를 구하면 된다. 문제에서 정의하는 "N-1개의 간선으로 이루어진 트리에서 정점 1에서 출발하여 정점 i에 도달하기까지 걸리는 가중치의 합"을 $d_i$라고 하자. 추가로, 정점 1에서 정점 i까지 도달하는데 걸리는 최단거리를 $D_i$라고 하자. 그렇다면 결국에 $d_i$가 $D_i$가 되면 문제에서 요구하는 $d_i$들의 합이 최소가 된다.

<그림 1. 임의의 그래프인 경우>

 위 그림 1에서 빨간색으로 이루어진 간선들의 경로, 즉 1-2-3-4가 정점 1에서 정점 4로 가는 최단거리 경로라고 하자. 이 때, 해당 경로를 버리지 않고 N-1개의 트리의 일부로 채택한다고 하자. 그렇게 된다면 $D_4 = d_4$가 됨은 자명하다. 그런데, 이때, 빨간색으로 이루어진 다른 간선들의 경로, 즉 1-2-3은 정점 3의 입장에서 보았을 때 과연 최적일까? 

 정답은 "그렇다"이다. 귀류법으로 간단히 증명할 수 있다. 만일 1-2-3 경로보다도 더 적은 거리로 이동할 수 있는 경로가 있다고 하자. 그렇게 된다면 우리는 굳이 1-2-3-4를 택할 이유가 없다. 왜냐하면 4의 입장에서는 최적이나, 3의 입장에서는 최적이 아니기 때문이다. 그런데, 만일 1-2-3-4 경로보다 더 작은 거리로 4까지 도달할 수 있었다면, 애초에 다익스트라 알고리즘이 해당 경로를 찾아주었을 것이다. 그런데 실제 다익스트라의 결과와 다르다면 결국 다익스트라 알고리즘이 틀린 알고리즘이거나, 1-2-3-4의 경로보다 더 작은 거리로 갈 수 없거나 둘 중 하나는 참이다. 그런데, 다익스트라 알고리즘에 대한 증명은 이미 수학적으로 완료되었기 때문에 전자가 참이 될 수 없으므로 후자, 즉 1-2-3-4의 경로보다 더 작은 거리로 갈 수 없다는 것이 참이다.

 따라서, 정점 3의 입장에서도 정점 4로 도달하기 위해 거쳤던 경로를 택하는 것이 최적이다. 재귀적으로 정점 2 역시 마찬가지이다. 따라서, 특정 최단 경로에 속하는 정점들은 해당 경로를 이루는 간선을 선택하는 것이 최단거리와 같아진다.

 

import sys, heapq

# go : 정점 1에서 다익스트라 알고리즘을 실행하였을 때 각 정점을 방문하기 전에 어떤 정점을 방문했는지
#      저장한 배열을 리턴하는 함수
def go():
	# d : 최단거리를 저장하는 배열
    d = [-1] * (n + 1)
    # path : 특정 인덱스(정점) i가 최단 경로를 따를 때 이전에 거친 정점 번호를 저장하는 배열
    path = [-1] * (n + 1)
    
    # 다익스트라 실행
    q = []
    heapq.heappush(q, (0, 1))
    while q:
        now_dist, now = heapq.heappop(q)
        if d[now] != -1 and d[now] < now_dist:
            continue
        for (next, next_dist) in adj[now]:
            if d[next] == -1 or d[next] > next_dist + now_dist:
                d[next] = next_dist + now_dist
                # 이전에 방문한 정점 갱신
                path[next] = now
                heapq.heappush(q, (next_dist + now_dist, next))
    return path

n, m = map(int, sys.stdin.readline().split())

# adj : 인접 리스트
adj = [[] for _ in range(n + 1)]
# cache : 특정 간선이 몇번째 간선인지 저장하는 dictionary
cache = dict()
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    cache[(a, b)] = i + 1
    adj[a].append((b, c))
    adj[b].append((a, c))
res = go()

# 각 정점별 이전에 도달했던 정점과 이루는 간선의 간선 번호 출력
for i in range(2, n + 1):
    print(cache[(min(i, res[i]), max(i, res[i]))], end=' ')

 

 후기 : 브라운에서 그린이 되었다! 내용도 나쁘지 않았지만, C번에서 너무 허무하게 페널티를 먹어서 아쉬웠다. d까지 풀었을 때 시간이 대략 55분 남짓 남았어서 기분이 좋았다. 하지만, E번도 충분히 풀 수 있었는데 스스로 뇌절을 많이 해서 아쉬운 문제였다. 남은 대회도 우선은 d번까지 빠르게 푸는 것을 목표로 해야겠다. 어제 참가한 nomura(Atcoder Beginner Contest 253)도 업솔빙한 후 여유가 될 때 포스팅해야 겠다