Codeforces Round #699 (Div. 2) ABC

import sys; input = sys.stdin.readline
 
for TEST in range(int(input())):
    N, M = map(int, input().split())
    res = True
    cnt = [0 for i in range(4)]
 
    for c in input().rstrip():
        if c=="R": cnt[0] += 1
        if c=="U": cnt[1] += 1
        if c=="L": cnt[2] += 1
        if c=="D": cnt[3] += 1
 
    if N>=0:
        if N > cnt[0]: res = False
    else:
        if -N > cnt[2]: res = False
    if M>=0:
        if M > cnt[1]: res = False
    else:
        if -M > cnt[3]: res = False
 
    print("YES" if res else "NO")

 

A - Space Navigation

 

주어진 좌표까지 가는 데 충분한 양의 R, U, L, D가 있는지 검사한다.

 

 

import sys; input = sys.stdin.readline
 
for TEST in range(int(input())):
    N, K = map(int, input().split())
    mount = [*map(int, input().split())]
 
    res = -2
    bad = False
 
    for i in range(K):
        bad = False
        for j in range(N):
            if j==N-1:
                bad = True
                break
            if mount[j] < mount[j+1]:
                mount[j] += 1
                if i==K-1: res = j
                break
        if bad: break
 
    if bad or res==-2:
        print(-1)
    else:
        print(res+1)

 

B - New Colony

 

최악의 경우는 길이 100의 수열 1, 1, 1, ..., 1, 100 이 주어지는 경우이고, 결국 O(100N) 정도에 시뮬레이션이 끝난다.

 

 

import sys; input = sys.stdin.readline

for TEST 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())]

    pre = [-1 for i in range(N+1)]
    ex = [False for i in range(N+1)]

    require = {}
    res = True
    arr = []
    deposit = -1

    for i in range(N):
        if A[i]!=B[i]:
            try: require[B[i]].append(i+1)
            except: require[B[i]] = [i+1]
            ex[B[i]] = True
        pre[B[i]] = i+1

    if pre[C[M-1]]==-1 and ex[C[M-1]]==False:
        print("NO")
        continue

    try:
        deposit = require[C[M-1]][0]
    except:
        deposit = pre[C[M-1]]

    for i, c in enumerate(C):
        tar = -1
        try:
            tar = require[c][-1]
            require[c].pop()
        except: pass

        if tar==-1:
            arr.append(deposit)
            A[deposit-1] = c
        else:
            arr.append(tar)
            A[tar-1] = c

    for i in range(N):
        if A[i]!=B[i]: res = False

    if res:
        print("YES")
        print(*arr)
    else:
        print("NO")

 

C - Fence Painting

 

마지막 painter가 수열 B에 없는 색을 칠하려고 한다면 반드시 실패한다.

 

그렇지 않다면, 모든 불필요한 painter가 마지막 painter가 칠할 위치에 색칠하게 하여 시뮬레이션하면 된다.

 

 

 

점수 하락을 감안하고 오랜만에 참여했는데 오히려 살짝 올라서 참 좋았다. ㅎㅎ