Codeforces Round #699 (Div. 2) A ~ C

codeforces.com/contest/1481

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

풀은 문제: A, B

못 풀은 문제: C, D, E

풀이를 보고 풀은 문제:

코드와 풀이를 보고 풀은 문제: C

 

난이도

A - 

B - 

C - 

D - 

E - 

 

 

 

C번 에디토리얼을 봤는데 아이디어는 맞았지만 코드 한 줄을 추가 안해서 틀렸다...

 

 

 

 

A - Space Navigation

 

문자열 s를 일부 지워서 목적지까지 도착할 수 있는지 물어보는 문제이다.

그래서 U, D, R, L 의 개수를 각각 전부 세준다음 목적지까지 이동할 수 있는지 찾으면 된다.

주의할 점은 px와 py가 음수일 때 -를 붙여서 U,D,R,L 갯수보다 작으면 된다.

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

 

k의 값은 크지만 n의 값은 100이기 때문에 for문으로 그냥 시뮬레이션 돌려주면 된다.

끝까지 부딪치지 않는다면 그때부터 -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)

 

 

 

 

C. Fence Painting

 

c배열은 j시간에 화가가 와서 색깔을 하나 무조건 칠해야하는 것이므로 마지막 화가가 중요하다.

마지막 화가가 b배열에 없는 숫자를 색칠하면 NO를 출력해야하고

마지막 화가가 b배열에 있는 숫자를 색칠한다면 그전까지 쓸모없는 화가들을 마지막 화가가 숫자를 색칠하는 인덱스에 색칠하면 된다.

그다음 만약 마지막 화가가 a배열과 b배열 값이 다른 인덱스가 있다면 그것을 우선으로 설정해주고, 없으면 위에 for문 했던 값을 그대로 사용한다.

 

이제 예외처리를 하나 해줘야하는데 (x번 색깔로 바꿔야하는 울타리의 수) > (x번 색깔을 칠할 수 있는 화가의 수)이면 NO를 출력해야한다.

 

다 칠해졌으면 YES를 출력하고 답을 출력하면 된다.

 

그래서 확인해야할 예외처리는

1.마지막 화가가 b배열에 없는 값을 들고 있는지

2.어떤 값으로 새로 색칠해야하는 울타리의 수가 그 색깔을 칠하는 화가의 수보다 많은지

를 확인하면 된다. 그 이후는 구현의 문제이다.

 

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)