Codeforces Round #699 (Div. 2)

문제링크

codeforces.com/contest/1481

Dashboard - Codeforces Round #699 (Div. 2) - Codeforces

 

A. Puzzle From the Future

 

문제

우주선으로 (0,0)에서 (px, py)로 이동하려고 한다.

우주선은 문자열 s에 입력된대로만 이동할 수 있고, 우주선이 문자열을 읽는 순서는 왼쪽에서 오른쪽으로 읽는다.

현재 좌표가 (x,y)이고, 읽어야하는 문자열의 위치가 s[i]일 때, 아래와 같은 규칙으로 이동한다고 한다.

- s[i] == U이면 (x, y) -> (x, y+1)로 이동

- s[i] == D이면 (x, y) -> (x, y-1)로 이동

- s[i] == R이면 (x, y) -> (x+1, y)로 이동

- s[i] == L이면 (x, y) -> (x-1, y)로 이동

 

우주선에서 문자열 s에 있는 여러 문자들을 삭제할 수 있을 때, 우주선이 목적지에 도착할 수 있는지 여부를 확인하시오.

 

풀이1

이 문제는 문자들을 삭제할 수 있으므로 U, D, R, L이 각각 입력되는 개수를 세어보고 목적지 (px, py)에 맞게 문자를 전부 삭제하거나 일부를 삭제하면 된다.

만약 (3,3)이 목적지이고 U, D, R, L의 입력횟수가 각각 5번이라면 U와 R은 2번 삭제하고, D와 L은 전부 삭제시켜주면 목적지로 이동이 가능하다.

 

그러므로 경우의 수를 나누어서

- px >= 0, py >= 0 일 때

- px >= 0, py < 0 일 때

- px < 0, py >= 0 일 때

- px < 0, py < 0 일 때

총 4가지로 나누어서 답을 출력하면 된다.

px나 py가 음수일 경우 -부호를 붙여줘서 +부호로 만들어준다음 U, D, R, L과 비교해야하는 것을 잊지말자

소스 코드1

def main():
    for _ in range(int(input())):
        px,py = map(int,input().split())
        s = input()
        U,D,R,L = 0,0,0,0
        for i in range(len(s)):
            if s[i]=='U':U+=1
            if s[i]=='D':D+=1
            if s[i]=='R':R+=1
            if s[i]=='L':L+=1
        if px >= 0:
            if py >= 0:
                if R >= px and U >= py:print('YES')
                else:print('NO')
            else:
                if R >= px and D >= -py:print('YES')
                else:print('NO')
        else:
            if py >= 0:
                if L >= -px and U >= py:print('YES')
                else:print('NO')
            else:
                if L >= -px and D >= -py:print('YES')
                else:print('NO')
main()

 

 

B. New Colony

 

문제

당신은 새로운 행성에 새로운 식민지를 건설하고 싶습니다. 행성에는 많은 산이 있는데 식민지를 건설하려면 평평한 곳에만 건설할 수 있어서 바위를 떨어뜨려서 행성을 평평하게 만들려고 합니다.

 

산의 높이를 결정하는 배열 h의 입력을 받고 k는 굴러 떨어뜨릴 바위의 수입니다.

첫번째 산 꼭대기에서 바위를 k번 떨어뜨리는데 다음 규칙을 따릅니다. (현재 산의 위치를 h[i]라고 가정)

- 만약 h[i] >= h[i+1]이면 돌이 다음 산으로 넘어갑니다.

- 만약 h[i] < h[i+1]이면 돌이 멈추고, h[i]의 높이가 1이 증가합니다.

- 만약 돌이 마지막 산까지 도달했는데 위의 두 조건에 해당하는 경우가 없으면 돌이 수거되어 사라집니다.

 

당신은 k번째 돌을 떨어뜨렸을 때, 돌이 산에 자리잡게 되는지 혹은 수거되는지 궁금합니다.

돌이 수거되는 경우 -1을 출력하고, 산에 자리잡게 되는 경우 몇번째 산에 자리잡게 되는지 출력하시오.

 

 

풀이1

문제 입력값에 주어진 범위를 살펴보면 최대값은 n = 100, k = 10^9, h[i] = 100 인 것을 알 수 있습니다.

그러므로 대충 계산해봐도 바위의 개수인 k =10000개 이후, 제대로 계산하면 배열 h의 값이 1, 2, ..... , 100이면 k = {99*(99+1)}/2개 이후 무조건 -1을 출력해야 한다는 것을 알 수 있습니다.

 

n의 값과 h의 값 때문에 2중 for문으로 구현해도 최대 100번씩 돌아가므로 시뮬레이션으로 충분히 시간내에 돌아갈 수 있다는 것을 캐치할 수 있습니다.

그러므로 시뮬레이션으로 코드를 구현한다음, 돌이 세번째 규칙에 해당될 때부터 무조건 -1을 출력하게 만들면 됩니다.

소스 코드1

def main():
    for _ in range(int(input())):
        n,k = map(int,input().split())
        h = [*map(int,input().split())]
        q = deque([0])
        z = -1
        flag = False
        for i in range(k):
            if flag == True:break
            for j in range(n-1):
                if h[j] < h[j+1]:
                    z = j
                    h[j]+=1
                    break
            else: flag = True
        if flag:print(-1)
        else:print(z+1)
main()

 

 

 

C. Fence Painting

 

문제

당신은 울타리를 새로 색칠하려고 한다.

울타리는 n개의 널빤지로 이루어져있고, 현재 i번째 널빤지의 색깔은 a[i]입니다. 당신은 i번째 널빤지의 색깔을 b[i]로 바꾸고 싶어합니다

당신은 m명의 화가를 불렀습니다. j번째 화가는 j의 순간에 도착하여 정확히 하나의 널빤지에만 c[j]의 색깔을 칠할 수 있습니다. 각 화가들은 당신이 선택하는 널빤지의 위치에만 색을 칠할 수 있지만 화가들에게 색을 칠하지 말라고 거절할 수는 없습니다.

당신이 원하는 대로 배열 b에 맞게 널빤지들을 칠할 수 있나요? 칠할 수 없으면 NO만 출력하고, 칠할 수 있으면 YES를 출력한다음 각 화가들이 몇번째 널빤지를 칠해야하는지 입력하시오.

 

 

풀이1

이 문제에서 제일 중요한 내용은 j번째 화가는 j의 순간에 도착하여 딱 하나의 널빤지의 색깔만 칠한다는 부분이다.

이 말은 c배열 왼쪽부터 오른쪽까지 순서대로 색깔을 칠한다는 것으로 마지막 화가의 번호가 중요해진다.

마지막 화가가 칠하려는 색깔의 번호가 배열 b에 없는 숫자이면 무조건 NO를 출력해야하고, 배열 b에 있는 숫자라면 배열c에 있는 필요없는 숫자들을 전부 마지막 화가가 칠하려는 널빤지의 위치에 칠해주면 된다.

 

n = m =100,000이지만 코드는 모든 것을 전처리해주면 O(max(N,M))으로 시뮬레이션을 할 수 있다는 것을 알 수 있다.

 

NO를 출력해야하는 조건

1. 울타리에 바꿔서 칠해야하는 색깔의 종류가 화가들이 칠할 수 있는 색깔의 종류보다 많을 때

2. 울타리에 바꿔서 칠해야하는 색깔의 수가 화가들이 칠할 수 있는 색깔의 수보다 많을 때

3. 마지막 화가가 색칠하는 색깔의 번호가 배열 b에 있는 번호가 아닐 때

 

전처리 해줘야할 것들

1. 바꿔야할 색깔의 수(a[i] != b[i])

2. 색깔 k로 바꿔야하는 울타리의 위치

3. 색깔 k로 바꿀 수 있는 화가의 수

4. 마지막 화가가 칠하는 널빤지의 위치(없으면 -1)

 

주의할 점은 마지막 화가가 칠해줘야하는 널빤지의 위치는 1순위로 새로 칠해야하는 울타리의 인덱스이고, 없으면 for문을 이용하여 마지막 화가가 칠하는 색깔의 번호와 같은 널빤지의 위치를 찾아주고 설정해준다.

 

파이썬에서 dict에 key값 1이 없으면 dict[1]을 출력시 KeyError가 나오지만 defaultdict를 이용하면 defaultdict[1]을 출력시 초기설정한 값으로 출력하게 된다.

defulatdict(lambda: 0)이면 defaultdict[1] = 0이 나오고, defaultdict(lambda: [])이면 defaultdict[1] = []이 나온다.

소스 코드1

from collections import defaultdict
def main():
    for _ in range(int(input())):
        n,m = map(int,input().split())
        a = [*map(int,input().split())]
        b = [*map(int,input().split())]
        c = [*map(int,input().split())]
        change_color = defaultdict(lambda:0)
        paint = defaultdict(lambda:[])
        painter = defaultdict(lambda:0)
        last_paint = -1
        for i in range(n):
            if a[i] != b[i]:
                change_color[b[i]]+=1
                paint[b[i]].append(i)
            if last_paint == -1 and b[i] == c[m-1]:
                last_paint = i
        if last_paint == -1:print('NO');continue
        if len(paint[c[m-1]]): last_paint = paint[c[m-1]].pop()
        for i in range(m):
            painter[c[i]] += 1
        flag = True
        for x in change_color.keys():
            if change_color[x] > painter[x]:flag = False
        if not flag:print('NO');continue
        ans = [-1]*m
        for i in range(m):
            if len(paint[c[i]]):ans[i] = paint[c[i]].pop()+1
            else:ans[i] = last_paint+1
        print('YES')
        print(*ans)
main()