Codeforces Round #540 (Div. 3) A ~ F1

codeforces.com/contest/1118

Dashboard - Codeforces Round #540 (Div. 3) - Codeforces

 

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

못 풀은 문제: D1, D2, F1, F2

풀이만 보고 풀은 문제: F1

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

 

 

난이도

A - 800

B - 1200

C - 1700

D1 - 1700

D2 - 1700

E - 1700

F1 - 1800

F2 - 2700

 

 

 

 

 

Div 2인데 Div 3이라고 잘못 적은 라운드 같다.

 

F1에서 파이썬은 재귀로 풀면 sys.setrecursionlimit를 설정해줘야하는데 이거때문에 메모리가 터져서 BFS로 풀어야한다. 다른 사람들 코드를 보니 스택을 이용해서 DFS로 풀 수 있었다.

F1코드는 hello70825.tistory.com/183 D번 문제랑 비슷한 테크닉으로 풀었는데 시간이 더 빠르다.

 

E번은 지문이 길어서 시간관계상 포기했는데 막상 지문과 예제를 보니까 힌트를 볼 필요도 없이 쉬웠다. 하지만 바로 생각해내지 못하고 조건에 계속 허덕이면서 생각했으면 못풀었을 것 같다.

 

 

 

 

A. Water Buying

 

무조건 1리터 아니면 2리터만 채울 수 있어서 1리터 2개의 가격이 2리터의 가격보다 더 큰지 확인하면 된다.

1) 1리터 2개의 가격이 2리터 1개의 가격보다 쌀 때 = n * a

2) 2리터 1개의 가격이 1리터 2개의 가격보다 쌀 때 = n//2 * b + (n이 홀수이면 1을 더하고, 아니면 0을 더함)

def main():
    for _ in range(int(input())):
        n,a,b = map(int,input().split())
        x = n*a
        y = n//2 * b
        if n%2: y+=a
        print(min(x,y))

 

 

 

B. Tanya and Candies

 

1번부터 n번까지 캔디가 있을 때

i번째 캔디를 빼고 다 먹는 경우 i+1부터의 짝수의 인덱스가 홀수의 인덱스로 변하고, 홀수의 인덱스가 짝수의 인덱스로 변한다.

그래서 예시를 들면서 배열을 어떻게 조작할지 구하면 된다.

만약 1 2 3 4 5 6 7 캔디가 있을 때, 홀수의 인덱스는 1, 3, 5이고 짝수의 인덱스는 2, 4, 6이다.

여기서 3번 캔디를 먹으면

1 2 4 5 6 7로 변하므로 홀수의 인덱스는 1, 4, 6, 짝수의 인덱스는 2, 5, 7로 바뀐다.

def main():
    n = int(input())
    a = [*map(int,input().split())]
    even = [0]*(n//2 + 1)
    odd = [0]*(n//2 + 1) if n%2 else [0]*(n//2) 
    for i in range(n):
        if i%2: even[(i+1)//2] = even[(i+1)//2-1] + a[i]
        else:odd[(i+1)//2] = odd[(i+1)//2-1] + a[i]
    odd = [0] + odd
    ans = 0
    for i in range(n):
        if i%2:
            x = odd[(i+1)//2] + even[-1] - even[(i+1)//2]
            y = even[(i+1)//2-1] + odd[-1] - odd[(i+1)//2]
 
        else:
            x = odd[(i + 1) // 2] + even[-1] - even[(i + 1) // 2]
            y = even[(i + 1) // 2] + odd[-1] - odd[(i + 1) // 2 + 1]
        if x==y:ans+=1
    print(ans)

 

 

 

C. Palindromic Matrix

 

행을 반전시켜도, 열을 반전시켜도 같은 행렬이 나올 경우 팰린드롬 행렬이라고 할 때, 입력 값을 적절히 조합하여 팰린드롬 행렬을 만들 수 있는지 여부와 만들 수 있으면 그 행렬을 출력하는 문제이다.

 

이 말은 행렬을 행과 열의 길이가 n//2인 행렬로 4등분하면 전부 데칼코마니처럼 대칭이 나와야한다는 것이다.

그래서 팰린드롬 행렬은 완벽하게 4등분할 수 있는 n이 짝수일 때와 십자가 모양과 4등분한 행렬이 나오는 n이 홀수일 때로 나눌 수 있다.

 

1) n이 짝수일 경우

행렬을 완벽하게 4등분할 수 있다.

4등분한 행렬중 하나를 정해서 각각 x축대칭, y축대칭, 원점대칭이 될 수 있는지 확인해야하는데, 이것은 각 숫자들의 개수가 4의 배수가 나오는지 확인을 해보면 된다.

그래서 이것을 통해 4의 배수가 나오면 행렬을 만들 수 있고, 4의 배수가 아니라면 행렬을 만들 수 없다.

 

이제 YES, NO를 출력했으면 행렬을 출력해야하는데, 만약 i <= n//2, j <= n//2인 (i, j)가 있으면 이 행렬 위치의 x축 대칭, y축 대칭, 원점 대칭에 똑같은 숫자가 있어야하므로 큐에 ( i , j ), ( n - 1 - i , j ), ( i, n - 1 - j ), ( n - 1 - i , n - 1 - j)를 합쳐서 큐에 넣어준다.

그리고 배열 a에 나왔던 숫자를 for문으로 돌리고 while문을 이용하여 행렬을 채워주면 된다.

 

 

2) n이 홀수일 경우

행렬을 4등분한 것에다가 추가로 십자가 모양이 나온다.

4등분한 것은 똑같은 숫자가 4개 필요하고, 십자가 모양은 똑같은 숫자가 2개만 있어도 된다. 그리고 마지막엔 가운데에 있는 숫자가 1개 필요하다.

그러므로 배열 a에 나왔던 숫자의 개수는 홀수가 1개, 나머지가 짝수여야하고, 십자가 모양은 최대 n-1개를 만들 수 있으므로 배열 a에 나온 숫자의 개수중에 4를 나눈 나머지의 개수가 n-1개 이하여야한다.

이것을 통하여 YES, NO를 출력할 수 있다.

 

이제 행렬을 출력하려면 4등분은 n이 짝수일 때와 똑같이하면 되고, 십자가 모양은 2개씩 필요하므로 가로 부분은 (n//2, j), (n//2, n-1-j)로 넣고, 세로 부분은 (i, n//2), (n-1-i, n//2)로 큐에 넣어주면 된다.

그리고 숫자 하나는 그냥 matrix[n//2][n//2]에 넣어주면 된다.

 

from collections import defaultdict
def main():
    n = int(input())
    a = [*map(int,input().split())]
    D = defaultdict(lambda: 0)
    for i in range(n**2):
        D[a[i]]+=1
    if n%2 == 0:
        flag = True
        for x in D.keys():
            if D[x]%4 != 0: flag = False
        print('YES') if flag else print('NO')
        if flag:
            ans = [[0]*n for _ in range(n)]
            path = []
            for i in range(n//2):
                for j in range(n//2):
                    path.append([(i,j),(n-1-i,j),(i,n-1-j),(n-1-i,n-1-j)])
            z = 0
            for x in D.keys():
                while D[x]:
                    for i in range(4):
                        nx, ny = path[z][i]
                        ans[nx][ny] = x
                    D[x]-=4
                    z+=1
            for i in range(n): print(*ans[i])
    else:
        odd = [0,0]
        two = 0
        for x in D.keys():
            if D[x] % 2: odd[0] += 1;odd[1] = x
            if D[x] % 4 == 2: two += 1
        flag = True
        if odd[0] != 1 or two > n-1: flag = False
        print('YES') if flag else print('NO')
        if flag:
            ans = [[0]*n for _ in range(n)]
            ans[n//2][n//2] = odd[1]; D[odd[1]] -= 1
            path1 = []
            path2 = []
            for i in range(n//2):
                for j in range(n//2):
                    path1.append([(i, j), (n - 1 - i, j), (i, n - 1 - j), (n - 1 - i, n - 1 - j)])
            for i in range(n//2):
                path2.append([(n//2,i),(n//2,n-1-i)])
                path2.append([(i,n//2),(n-1-i,n//2)])
            z = 0
            for x in D.keys():
                if z == len(path1): break
                while D[x]:
                    if D[x] < 4 or z == len(path1): break
                    for i in range(4):
                        nx,ny = path1[z][i]
                        ans[nx][ny] = x
                    D[x]-=4
                    z+=1
            z = 0
            for x in D.keys():
                while D[x]:
                    for i in range(2):
                        nx,ny = path2[z][i]
                        ans[nx][ny] = x
                    D[x]-=2
                    z+=1
            for i in range(n): print(*ans[i])

 

 

 

D1. Coffee and Coursework(Easy version)

 

n개의 커피를 필요한만큼만 마시고 m페이지 이상을 쓸 수 있는 최소일을 구하는 문제로 쉬운버전은 n = 100이다.

n = 100이므로 커피를 하루에 한잔씩 최대 100일동안 마실 수 있다는 것이다. 이것을 통해 며칠동안 커피를 마실지 일일이 확인하면서 최소기간을 찾는 브루트포스를 생각해볼 수 있다.

그리고 커피를 마실 때에는 최대한 많은 카페인을 먹을 수 있도록 배열을 내림차순 정렬하고, 만약 k일동안 마신다면 내림차순한 배열을 for문으로 돌려서 1일차, 2일차,.., k일차, 1일차,....에 배정해주면 된다.

 

def main():
    n, m = map(int, input().split())
    a = sorted([*map(int, input().split())], reverse=True)
    for i in range(1, n + 1):
        val = 0
        for j in range(n):
            val += max(0, a[j] - j // i)
        if val >= m:print(i);exit()
    print(-1)

 

 

D2. Coffee and Coursework(Hard version)

 

D1은 브루트포스로 구했는데, D2는 n = 2*10^5라서 브루트포스로는 시간초과가 나온다.

그러므로 이진탐색을 이용하여 val >= m일 경우 최소값이 더 나올 여지가 있으므로 r = mid - 1을 해주고, val < m일 경우 최소값이 아직 안나왔다는 뜻이므로 l = mid + 1을 해준다. 그러면 O(nlogn)으로 통과할 수 있게 된다.

 

def main():
    n, m = map(int, input().split())
    a = sorted([*map(int, input().split())], reverse=True)
    l,r = 1, 2*10**5 + 1
    ans = 2*10**5 + 1
    while l <= r:
        mid = (l+r)//2
        val = 0
        for j in range(n):
            val += max(0, a[j] - j // mid)
        if val >= m:
            ans = mid
            r = mid - 1
        else: l = mid + 1
    print([ans,-1][ans == 2*10**5+1])

 

 

 

E. Yet Another Ball Problem

 

1. 1. 모든 i에 대해서 b[i]와 g[i]는 1이상 k이하이다.
2. 여기엔 완벽히 똑같은 페어는 없다. bi = bj인데 gi = gj인 페어가 없다
3. 모든 i에 대해 b[i] != g[i]이다.
4. 두 개의 연속쌍에 대해 각 성별은 색상이 다릅니다. b[i] != b[i+1], g[i] != g[i+1]입니다.

 

k개의 색깔이 있을 때 위 조건에 해당하는 n개의 페어를 만들 수 있는지 여부와 만들 수 있으면 페어를 출력하면 되는 문제이다.

예제를 보면 눈치챘겠지만 k=3일 때 (1,2), (1,3), (2,3)을 가져온 뒤 전부 뒤집어주면 된다.

그래서 k=3일때 (1,2) (2,1) (1,3) (3,1) (2,3) (3,2)로 최대 6개까지 만들 수 있다. 

이것을 공식으로 표현하면 1부터 k까지 색상중에서 2개를 뽑는 것이므로 kC2와 뒤집어주는 것 때문에 2를 곱하면 최대 k*(k-1)개의 조합을 만들 수 있게 된다.

 

def main():
    n, k = map(int,input().split())
    if n > k*(k-1):print('NO');exit()
    print('YES')
    ans = 0
    for i in range(1,k+1):
        for j in range(i+1,k+1):
            print(i,j)
            ans += 1
            if ans == n:exit()
            print(j,i)
            ans += 1
            if ans == n:exit()

 

 

 

 

 

F1. Tree Cutting(Easy version)

 

트리가 있는데 간선 하나를 잘랐을 때, 한쪽은 빨강색 노드만 있고 다른 한쪽은 파랑색 노드만 있는 2개의 서브트리를 만들 수 있는 간선이 총 몇 개가 있는지 구하는 문제이다.

 

간선을 잘랐을 때 서브트리들의 색깔의 개수를 구하려면 만약 n번 노드와 n-1번 노드를 이어주는 간선을 잘랐을 때, 각각 서브트리의 총 색깔의 개수를 바로바로 파악할 수 있는 방법을 찾아야한다는 것을 알 수 있다.

그래서 누적합이 떠오를 것인데 누적합을 트리에 맞게 만드려면

1) 루트부터 시작해서 리프까지 내려가는 누적합

2) 리프부터 시작해서 루트까지 올라가는 누적합

이 두가지 방법이 떠오를 것이다

 

1번을 예시로 들어보면

이런 트리가 있을 때 답은 간선 아무거나 잘라도 답이 될 수 있다.

루트부터 시작해서 리프까지 내려가는 누적합을 그려보자

첫번째 값은 파랑색 노드의 수이고, 두번째 값은 빨강색 노드의 수일 때

이렇게 나올 것이다.

 

1번 노드와 2번 노드의 간선을 끊으면 2번 노드에서는 [ 0 , 1 ]이 나오지만, 1번 노드에서는 [ 0 , 0 ]이라서 사진에서는 파랑색 노드가 왼쪽 서브트리에 있는 것을 알 수 있지만 컴퓨터는 파랑색 노드가 어디있는지 모른다

그림이 작아서 그럼 1번 노드 말고 2번 노드를 보면 되는 것이 아니냐라고 생각할 수 있다.

더 큰 트리를 그려보면

답은 똑같지만 3번과 6번 노드를 자르면 각각 [ 1, 0 ]과 [ 1, 0]이 나와서 빨강색 노드의 행방은 모르고, 파란색 노드는 각각 서브트리에 1개씩 있다고 착각할 수 있다.

서브트리의 노드를 하나하나 확인하면 되지 않나 싶은데 그러면 시간초과가 나올 것이다.

그래서 1번 방법은 틀렸다.

 

이번엔 2번 방법인 리프노드부터 올라가는 누적합을 구해보자

 

 

여기서 1번 노드와 2번 노드 사이에 있는 간선을 없애면 각각 [ 0, 2 ]와 [ 2, 2 ]가 나올 것이다.

2번 노드의 값인  [ 0, 2 ]는 해당 서브트리에 있는 색깔을 모두 합한 값이고, 1번 노드의 값인 [ 2, 2 ]는 2번 노드의 누적합까지 포함한 값이다.

그러므로 2번 노드의 누적합을 빼주면 1번 노드가 있는 서브트리의 값은 [ 2 , 0 ]이므로 둘이 나누어 질 수 있게 된다.

 

이번엔 3번 노드와 5번 노드 사이의 간선을 잘라보자

일단 5번 노드가 루트노드인 서브트리는 5번 노드의 값인 [ 1, 0 ]이 해당 서브트리의 모든 색깔을 구한 것이다. 3번 노드쪽은 루트노드에 5번 노드의 값을 빼면 된다. 그래서 [ 1, 2 ]임을 알 수 있다.

 

이 아이디어를 이용하여 코드를 짜면 된다.

여기서 루트노드는 1번이라고 정했다.

def main():
    n = int(input())
    a = [0] + [*map(int, input().split())]
    adj = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        x, y = map(int, input().split())
        adj[x].append(y)
        adj[y].append(x)
    num = [[0, 0] for _ in range(n + 1)]
    q = deque([1])
    visit = [0]*(n+1);visit[1] = 1
    for i in range(n-1):
        x = q[i]
        for nx in adj[x]:
            if visit[nx]: continue
            q.append(nx)
            visit[nx] = 1
    while q:
        x = q.pop()
        if a[x] == 1: num[x][0] += 1
        if a[x] == 2: num[x][1] += 1
        for nx in adj[x]:
            num[x][0] += num[nx][0]
            num[x][1] += num[nx][1]
    ans = 0
    for i in range(2, n + 1):
        if num[i][0] == num[1][0] and num[i][1] == 0: ans += 1
        if num[i][0] == 0 and num[i][1] == num[1][1]: ans += 1
    print(ans)