Codeforces Round #693 (Div. 3) A ~ E

codeforces.com/contests/1472

Codeforces Round #693 (Div. 3) - Codeforces

풀은 문제: A, B, C, D

못 풀은 문제: E, F, G

- 풀이만 보고 풀은 문제: E

- 풀이와 코드 전부 본 문제: F, G

 

난이도

A - 800

B - 800

C - 1100

D - 1200

E - 1700

F - 2100

G - 2100

 

 

 

E, F, G 난이도가 높아서 A~D까지 풀이법만 빨리 생각해냈다면 매우 높은 순위도 가능하여서 아쉬웠다.

C번을 두 번 틀리고 통과했는데, 그거 아니였으면 수백등 더 올라갔을 것 같다

 

F는 다른 코드들도 살펴봤는데 공통적으로 코드에 쓰이는 변수 하나가 무슨 의미를 가지고 잘 모르겠다. 

G는 코드가 쉬운 것 같은데 해석하려고하니까 막히는 곳이 있다.

 

 

A. Cards for Friends

 

w나 h중에 짝수가 있다면 반으로 나눈다고 한다.

만약 4x4 1개 => 2x4 2개 => 2x2 4개 => 1x2 8개 => 1x1 16개

이렇게 짝수가 있을 때마다 답을 출력하는 변수에 2를 곱하면 된다.

for _ in range(int(input())):
    ans = 1
    w,h,n = map(int,input().split())
    while 1:
        if w%2 == 1 and h%2 == 1: break
        if w%2 == 0: w//=2; ans*=2
        if h%2 == 0: h//=2; ans*=2
    if ans >= n:print('YES')
    else:print('NO')

 

 

B. Fair Division

 

Alice와 Bob이 캔디를 적절히 분배하여 같은 무게로 나누어 받을 수 있는지 물어보는 문제이다.

캔디의 수가 100개까지이고, 캔디의 무게가 1아니면 2여서 브루트포스로 알아낼 수 있다.

 

for _ in range(int(input())):
    n = int(input())
    D = [*map(int,input().split())]
    a,b = 0,0
    err = 1
    for i in range(n):
        if D[i] == 1:a+=1
        else: b+=1
    if a%2 == 1:print('NO');continue
    if a != 0:
        for i in range(a+1):
            x, y = i, a-i
            for j in range(b+1):
                x += 2*j
                y += 2*(b-j)
            if x==y:print('YES');err=0
    else:
        for i in range(b+1):
            x, y = 2*i, 2*(b-i)
            if x == y:print('YES');err=0
    if err:print('NO')

 

 

 

C. Long Jumps

 

i = 1부터 n까지 출발하여 가장 큰 값이 무엇인지 찾아내는 문제이다.

이건 거꾸로 n부터 출발하여 가장 큰 값을 구하면 O(n)으로 풀 수 있다.

왜냐면 만약 i=3을 방문한다음 D[3] = 2라서 i=5를 방문하고 끝난다면 i=5를 간 후, D[5]의 값을 i=3일 때의 값에 더해서 업데이트해줘야한다. 저러면 최악의 경우 D의 값이 모두 1일 때 O(n^2)의 시간이 걸린다.

하지만 i=5를 먼저 방문한다면 i=5의 값을 업데이트하고 i=4에서 출발한 후, i=3에서 출발할때 D[3]의 값에 i=5일때의 큰 값을 더해주면 끝이라 값 업데이트를 하지 않은채 바로 가장 큰 값을 구할 수 있다.

 

for _ in range(int(input())):
    n = int(input())
    D = [*map(int,input().split())]
    S = [i+1 for i in range(n)]
    ans = [0]*n
    for i in range(n,0,-1):
        S[i-1] += D[i-1]
        ans[i-1] += D[i-1]
        if S[i-1] <= n:
            ans[i-1] += ans[S[i-1]-1]
    print(max(ans))

 

 

 

D. Even-Odd Game

 

Alice는 짝수를 가져가면 가져간 수만큼 득점이 인정되고, 홀수를 가져가면 아무런 득점이 없다.

Bob은 홀수를 가져가면 가져간 수만큼 득점이 인정되고, 짝수를 가져가면 아무런 득점이 없다.

서로 최선의 선택을 하였을 때, Alice와 Bob중 누가 높은 점수를 얻는지 아니면 동점인지 확인하는 문제이다.

 

먼저 입력값을 받은다음, 짝수 세트와 홀수 세트로 나누고 각각 정렬을 해준다.

그다음 Alice턴일 때, 짝수의 가장 큰 수와 홀수의 가장 큰 수를 비교하여 짝수가 홀수보다 크면 짝수를 가져가서 점수를 챙기고, 홀수가 더 크면 홀수를 가져가서 Bob이 그 점수를 얻지 못하게 한다.

Bob도 마찬가지로 하면 된다.

이때 더이상 가져갈 수 없는 세트가 한 개 존재한다면 남은 세트에서 가장 큰 수를 가져가면 된다.

 

그래서 한 선수가 할 수 있는 경우의 수는 3가지가 있고, 홀수 세트와 짝수 세트에 숫자가 없으면 경기를 종료하는 것으로 만들었다.

 

for _ in range(int(input())):
    n = int(input())
    a = [*map(int,input().split())]
    odd, even = [], []
    for i in range(n):
        if a[i]%2:odd.append(a[i])
        else:even.append(a[i])
    odd = sorted(odd)
    even = sorted(even)
    alice, bob = 0,0
    while 1:
        if len(even):
            if len(odd) and even[-1] < odd[-1]:odd.pop()
            else:alice += even.pop()
        else:
            if len(odd):odd.pop()
            else:break
 
        if len(odd):
            if len(even) and even[-1] > odd[-1]:even.pop()
            else:bob += odd.pop()
        else:
            if len(even):even.pop()
            else:break
    if alice>bob:print('Alice')
    elif alice<bob:print('Bob')
    else:print('Tie')

 

 

 

E. Correct Placement

 

에디토리얼을 봤지만 이해하기가 힘들어서 댓글에 있는 투 포인터로 문제를 풀 수 있다는 것을 이용해 문제를 풀었다.

 

 

 

문제 조건은 h_1 > h_2, w_1 > w_2 이거나, h_1 > w_2, w_1 > h_2이거나 둘 중 하나만 만족하면 사진2를 사진1 앞에 놓을 수 있다고 한다.

이걸 다르게 생각해서 x1 = max(h_1, w_1), y1 = min(h_1, w_1)로 하고 x2 = max(h_2, w_2), y2 = min(h_2, w_2)로 두면 x1 > x2, y1 > y2를 만족하는 숫자를 구하면 된다.

 

x1 > y2, y1 > x2인 케이스도 있지 않느냐 이렇게 생각할 수도 있는데, 일단 x1과 y1는 max(h_1, w_1), min(h_1, w_1)이므로 x1 >= y1이고 마찬가지로 x2 >= y2이다. 그리고 y1 > x2이면 대소관계가 x1 >= y1 > x2 >= y2이기 때문에 이것도 x1 > x2, y1 > y2가 성립하게 된다.

 

그래서 풀이는 min(h,w)값을 기준으로 오름차순, min(h,w)값이 같으면 max(h,w)값을 기준으로 내림차순으로 정리한다.

정렬하는 리스트는 [min(h,w), max(h,w), i]이다.

 

교체할 수 있는 가장 작은 값은 MIN = [D[0][0],D[0][1],D[0][2]]으로 초기화해두고, for문을 돌려서 1부터 n-1까지 돌린다.

min_x, min_y, min_z = MIN으로 하고, x, y, z = D[i]로 준다.

 

그리고 일단 min_x와 x값이 같으면 무조건 답이 아니고, min_y > y인 경우가 있을 텐데 이때는 MIN값을 [x, y, z] 로 값을 변경해준다. 이러면 min_x < x는 무조건 성립하는데 min_y는 그동안 for문으로 훑은 y값중에 가장 작은 y값이므로 이 MIN값을 여부로 사진 앞에 다른 사진이 올 수 있는지 여부를 확인할 수 있다.

 

예를들어서 [1,5,0], [1,3,1], [1,2,2], [2, 5, 3], [2, 2, 4]가 있고 for문을 돌리면

i = 0일 때

min_x, min_y, min_z = 1, 5, 0

x, y, z = 1, 5, 0

이므로 ans[0] = -1이고

 

i = 1일 때

min_x, min_y, min_z = 1, 5, 0

x, y, z = 1, 3, 1

인데 min_y > y 이므로 MIN = D[i]로 변경하여 MIN = [1,3,1]로 변경한다. ans[1] = -1

 

i = 2일 때

min_x, min_y, min_z = 1, 3, 1

x, y, z = 1, 2, 2

인데 어차피 min_x = x니까 값을 업데이트를 못한다. 하지만 min_y > y이므로 MIN = [1, 2 , 2]로 변경한다. ans[2] = -1

 

i = 3일 때

min_x, min_y, min_z = 1, 2, 2

x, y, z = 2, 5, 3

인데 x > min_x 이고 y > min_y 이므로 ans[3] = min_z + 1 = 3이다.

그리고 y > y_min이므로 MIN이 업데이트 되지 않는다.

 

i = 4일 때

min_x, min_y, min_z = 1, 2, 2

x, y, z = 2, 2, 4

인데 x > min_x 이지만 y <= min_y 이므로 ans[4] = -1이다.

그리고 y = y_min이므로 굳이 MIN을 업데이트 해주지 않아도 된다.

 

그래서 답은 -1 -1 -1 3 -1 이다.

 

for _ in range(int(input())):
    n = int(input())
    D = []
    ans = [-1]*n
    for i in range(n):
        h,w=map(int,input().split())
        D.append([min(h,w),max(h,w),i])
    D.sort(key = lambda a: [a[0],-a[1]])
    MIN = D[0]
    for i in range(1,n):
        x, y, z = D[i]
        min_x, min_y, min_z = MIN
        if x > min_x and y > min_y: ans[z] = min_z+1
        elif min_y > y: MIN = D[i]
    print(*ans)