Atcoder Beginner Contest 243 후기

A. Shampoo

 샴푸가 n리터있고 세명이서 각각 a,b,c만큼 돌아가면서 쓸 때, 최초로 샴푸를 사용하지 못하는 사람을 묻는 문제이다. n제한이 작기 때문에 단순 구현문제로 충분하다

import sys

n, a, b, c = map(int, sys.stdin.readline().split())
arr = [a, b, c]
cache = {0 : 'F', 1 : 'M', 2 : "T"}
idx = 0
while True:
    if (n - arr[idx] < 0):
        print(cache[idx])
        break
    else:
        n -= arr[idx]
    idx += 1
    idx %= 3

 

B. Hit and Blow

 특정 배열 A와 B가 있을 때, 같은 인덱스에서 같은 값을 가지는 원소의 갯수와 다른 인덱스에서 같은 값을 가지는 원소의 갯수를 출력하는 문제. 단순 구현문제이다

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
ans1, ans2 = 0, 0
for i in range(n):
    if a[i] == b[i]:
        ans1 += 1
    else:
        for j in range(n):
            if i == j:
                continue
            if a[i] == b[j]:
                ans2 += 1
print(ans1)
print(ans2)

C. Collision 2

 원소들이 x축을 기준으로 각각 정해진 방향을 따라 동시에 무한히 움직일 때, 중간에 부딫히는 원소가 있는지 확인하는 문제이다. 오른쪽을 기준으로 생각한다면, 자신의 y좌표와 똑같은 위치에 있으면서 자신의 x좌표보다 오른쪽에 위치하는 왼쪽으로 전진하는 원소가 있는지 체크하면 된다. 왼쪽을 기준으로 한다면, 동일한 y좌표에 있으면서 자신의 x좌표 보다 왼쪽에 위치하는 오른쪽으로 전진하는 원소가 있는지 체크하면 된다

import sys, bisect

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

# left : 원소의 y좌표를 key, 그 때의 x좌표들의 집합을 value로 갖는 dictionary
left = dict()

# 원소 입력 및 저장
arr = []
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    arr.append((a, b))
temp = list(sys.stdin.readline().rstrip())

# can : 부딪히는 원소가 있는지 확인하는 flag 변수
can = False

# 왼쪽 방향으로 가는 원소들을 left의 정의대로 저장
for i in range(n):
    if temp[i] == 'L':
        if arr[i][1] not in left:
            left[arr[i][1]] = set()
        left[arr[i][1]].add(arr[i][0])
        
# x좌표 집합들을 정렬
for i in left:
    left[i] = sorted(left[i])
    
for i in range(n):
    if temp[i] == 'R':
        # 만약 오른쪽으로 움직이는 원소의 y좌표와 동일한 원소가 있다면
        if arr[i][1] in left:
            # 만약 오른쪽으로 움직이는 원소의 x좌표보다 오른쪽에 위치한 x좌표를 가진 원소가 있다면
            if bisect.bisect_right(left[arr[i][1]], arr[i][0]) != len(left[arr[i][1]]):
                # 부딫히는 원소가 존재
                can = True
                break
                
# 정답 출력
print('Yes' if can else 'No')

D. Moves on Binary Tree

 생각보다 간단한 문제인데, 조급해서 페널티를 2번이나 받은 문제이다. 문제에서 주어진 트리에서 자신의 조상이나 자신의 왼쪽 자식이나 자신의 오른쪽 자식으로 가는 세 연산 중 하나를 할 수 있을 때, 일련의 연산들을 모두 끝마쳤을 때 위치하는 정점번호를 출력하는 문제이다. 

 현재 정점 번호가 x일 때, 왼쪽 자식으로 가면 현재 정점 번호에 $2x$가 되고, 오른쪽 자식으로 가면 현재 정점 번호가 $2x+1$이 된다. 반대로 현재 정점에서 조상으로 간다면 $\left \lfloor\frac{x}{2} \right \rfloor$가 된다. 이 때 정답은 $10^8$을 넘지 않으나, 연산 중간에는 $10^8$을 넘을 수도 있기 때문에, 곧이곧대로 연산을 처리하면 안된다. 이 때, 현재 연산이 U일 때, 직전에 L 혹은 R연산이 있다면 이는 사실상 제자리걸음이기 때문에 연산을 줄이는 효과가 있다. 스택을 이용하면 간단하게 해결이 가능하다

import sys

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

# st : 연산들을 저장하는 스택
st = []
for i in arr:
	# 왼쪽 자식 혹은 오른쪽 자식으로 가는 연산이면 그대로 저장
    if i == 'L' or i == 'R':
        st.append(i)
    else:
    	# 이전에 왼쪽 자식이나 오른쪽 자식으로 갔다면 제자리니까 스택에서 pop
        if st:
            if st[-1] == 'L' or st[-1] == 'R':
                st.pop()
            # 그렇지 않다면 그대로 저장
            else:
                st.append(i)
        # 애초에 스택이 비어있어도 그대로 저장
        else:
            st.append(i)
            
# 규칙에 따라 정점 번호 계산
for i in st:
    if i == 'L':
        x = x * 2
    elif i == 'R':
        x = x * 2 + 1
    else:
        x //= 2

# 정답 출력
print(x)

 

총평 : 저번 대회보다는 퍼포먼스가 좋게 나왔으나, C번이랑 D번에서 페널티를 총 3번이나 내버렸다. 계산하면 15분짜리인데 등수에 치명적이다. 좀 더 빠르고 정확해야 한다. 개인적으로 D번을 풀어서 심적으로 말리지 않았다. 앞으로의 대회도 안정적으로 D까지는 풀 수 있도록 노력해야한다