USACO 2020 December Contest silver 파이썬 풀이

어제 다른 분들이 쓴 USACO 후기를 조금 찾아봤는데, USACO 2020 December Contest 후기글을 찾았습니다. 일단 문제를 풀고 글을 읽고 싶었어서, 틈틈히 풀었습니다. 문제가 상당히 재밌었던 것 같습니다.

 

실제 풀이에 쓴 시간은

1번 10분

2번 30분

3번 1시간

정도 된 것 같습니다.

 

https://www.acmicpc.net/problem/20647

20647번: Cowntagion

재밌는 트리 문제입니다. 요즘 트리 문제를 많이 풀고 있는데, 저한테 잘 맞는 것 같습니다.

한 노드에서 다른 노드로 오직 한마리의 소만 보낼 수 있다는 조건이 중요합니다.

첫번째 감염이 발생하는 노드 1을 루트로 하는 트리를 생각해보면, 루트의 차수 + 1 >= 루트 감염자 수

가 되어야 합니다. 그래야 자식 노드들에 감염자를 보낼 수 있습니다.

그 후, 각 자식들의 차수를 1씩 줄여주고, 똑같은 과정을 반복해 주면 됩니다. dfs로 쉽게 풀 수 있습니다.

이 과정이 최적해임은 귀류법을 사용해 증명할 수 있습니다. 

시간복잡도는 O(n) 입니다.

import sys
input = sys.stdin.readline

def dfs(cur, p=-1):
    global ans
    x = 1
    while x < degree[cur]:
        x *= 2
        ans += 1
    for nxt in adj[cur]:
        if nxt != p:
            degree[nxt] -= 1
            ans += 1
            dfs(nxt, cur)

n = int(input())
adj = [[] for _ in range(n + 1)]
degree = [1] * (n + 1)
for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
    degree[u] += 1
    degree[v] += 1
ans = 0
dfs(1)
print(ans)

 

https://www.acmicpc.net/problem/20648

20648번: Rectangular Pasture

어떤 부분집합이 만들어질 수 없을지를 생각해보면 쉽게 풀 수 있습니다. 세 점 (x, y), (x', y'), (x'', y'')에 대해서, x < x' < x'', y < y' <. y''이라 하면, (x, y), (x'', y'')만이 존재하는 부분집합은 만들어질 수 없습니다. 입력에서 x와 y의 점들은 유일하니, 등호를 고려해줄 필요는 없습니다.

우선 좌표의 범위가 너무 크니 좌표 압축을 해줍시다.

그리고 x에 대해 정렬을 시켜주고, 어떤 점 x 보다 오른쪽에 있는 점들만 고려해줍시다. (x, y)와 (x, y)의 오른쪽에 있는 어떤 점 (x', y')에 대해, 각 점을 꼭짓점으로 하는 직사각형을 고려해봅시다. 그 직사각형 위와 아래에 있는 점들 또한 집합을 만들어줄 수 있습니다. 항상 x가 증가하는 순서로 방문해주면, 중복을 탐색할 여지가 없습니다. y좌표에 대한 세그먼트 트리나 2차원 부분합 배열을 전처리해주면 쉽게 해결할 수 있습니다.

시간복잡도는 O(N^2 log n) 입니다. 

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline

def query(l, r):
    l += n
    r += n
    ret = 0
    while l < r:
        if l & 1:
            ret += st[l]
            l += 1
        if r & 1:
            r -= 1
            ret += st[r]
        l //= 2
        r //= 2
    return ret

def update(x, v):
    x += n
    st[x] = v
    while x > 1:
        st[x // 2] = st[x] + st[x ^ 1]
        x //= 2

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
x = sorted(list(map(lambda k: k[0], a)))
y = sorted(list(map(lambda k: k[1], a)))
for i in range(n): a[i] = [bl(x, a[i][0]), bl(y, a[i][1])]

a.sort()
ans = 1
for i in range(n):
    st = [0] * n * 2
    lx, ly = a[i][0], a[i][1]
    ans += 1
    for j in range(i + 1, n):
        rx, ry = a[j][0], a[j][1]
        l, r = min(ly, ry), max(ly, ry)
        down, up = query(0, l), query(r, n)
        ans += 1 + down + up + down * up
        update(ry, 1)
print(ans)

down, up은 현재 보고 있는 점(x, y)와 (x', y')에 대해 만들어진 직사각형에 대해, x'보다 작고 y'보다 크거나, 작은 점들의 개수 입니다.

 

https://www.acmicpc.net/problem/20649

20649번: Stuck in a Rut

의외로 유니온 파인드가 필요 없는 문제입니다. 처음 문제를 읽었을 때 당연히 유니온 파인드를 사용해야겠구나.. 생각했는데 아니었습니다. 

오른쪽으로 움직이는 소들과 위로 움직이는 소들을 분리해줍시다. 오른쪽으로 움직이는 소들을 X, 위로 움직이는 소들을 Y라고 하겠습니다. X를 y에 대해서 ,Y를 x에 대해서 정렬해줍시다. 정렬해주는 이유는 X에서 밑에 있는 소들부터 Y에서 오른쪽에 있는 소와 만나기 때문입니다. 누가 누굴 멈출지는 X의 점에서 기울기가 -1인 직선을 그릴 때, Y가 어디 있는지로 알 수 있습니다. 만약 멈춘다면, 그 소에 연결되어있는 컴포넌트의 개수만큼 더해주면 됩니다. 유니온 파인드와 비슷한 과정을 거칩니다.

시간복잡도는 O(n^2) + O(n log n) = O(n^2) 입니다. 상수가 작아 굉장히 빨리 돕니다.

import sys
input = sys.stdin.readline

class Line:
    def __init__(self, x, y):
        self.b = x + y

    def f(self, x):
        return -x + self.b

n = int(input())
r = [1 for i in range(n)]
X = []
Y = []
for i in range(n):
    s, a, b = map(str, input().split())
    if s == "N": Y.append([int(a), int(b), i])
    else: X.append([int(a), int(b), i])

X.sort(key=lambda k: k[1])
Y.sort(key=lambda k: k[0])

v = [0] * n
for ex, ey, ei in X:
    l = Line(ex, ey)
    for nx, ny, ni in Y:
        if v[ni] or nx < ex or ny > ey: continue
        if ny < l.f(nx):
            r[ei] += r[ni]
            v[ni] = 1
        elif ny > l.f(nx):
            r[ni] += r[ei]
            break

for i in range(n): print(r[i] - 1)

여담으로, 딱히 숏코딩을 하진 않았지만 이 문제에서 숏코딩 1등을 먹었습니다. 파이썬 기준 실행시간 1등도 먹었습니다.