USACO 2023 February Contest silver div 풀이

봇치 더 록 재밌음 꼭 보세요

섭테만 긁었어도..

유사코가 끝난지 꽤 되었는데, 귀찮아서 풀이를 올리지 않다 이제야 올린다. 당시 대회에서 2, 3번을 1시간 30분정도에 걸쳐 풀고, 1번 문제를 계속 봤는데, 결국 섭테를 하나도 못긁었다. 이상한 관찰을 자꾸 하고 증명도 없이 살면서 풀어본적도 없는 기하적 해석을 했는데, 결국 그냥 뻘짓이었다. 다음부터는 문제가 어려워보이면 섭테 긁을 생각부터 해야겠다.

 

왜 1번이 3번보다 난이도가..

 

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

27847번: Cow-libi

영어 해석을 조금이라도 잘못하면 큰일나는 문제다. 문제의 입력은 항상 적어도 한 마리의 소가 지나갈 수 있게 주어진다. 즉, 시간을 기준으로 정렬하고, 입력인 g.t 마다 이분탐색으로 a.t[i - 1] <= g.t <= a.t[i] 인 i를 찾아주고, 시간 내에 양옆으로 갈 수 있는지만 확인해주면 된다. 만약 시간 내에 양옆으로 갈 수 있다면, 다른 목장으로 이동하는건 입력의 조건 때문에 항상 가능하다.

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

class pos:
    def __init__(self, x, y, t):
        self.x = x
        self.y = y
        self.t = t

def dist(self, other): return (self.x - other.x) ** 2 + (self.y - other.y) ** 2
def timedif(a, b): return (a.t - b.t) ** 2

g, n = map(int, input().split())
crime = [pos(*list(map(int, input().split()))) for _ in range(g)]
tarr = [0] * g
crime.sort(key=lambda x:x.t)

for i in range(g): tarr[i] = crime[i].t

ans = 0
for _ in range(n):
    tmp = pos(*list(map(int, input().split())))
    i = bl(tarr, tmp.t)
    if i == g:
        if dist(tmp, crime[i - 1]) > timedif(tmp, crime[i - 1]): ans += 1
    elif i == 0:
        if dist(tmp, crime[i]) > timedif(tmp, crime[i]): ans += 1
    else:
        if dist(tmp, crime[i]) > timedif(tmp, crime[i]) or dist(tmp, crime[i - 1]) > timedif(tmp, crime[i - 1]): ans += 1
print(ans)

 

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

27848번: Moo Route II

문제를 읽어보면, 음수 간선이 있고 최간거리를 구하면 되니.. 벨만 포드를 돌리면 될 것 같지만.. O(N * M)이면 당연히 시간초과가 난다. 여기서 관찰을 몇개만 하면, 문제를 그리디하게 풀 수 있다.

 

1. 한번 탄 간선을 또 다시 탈 필요는 없다.

이 문제에서는 간선이 추가적인 비용을 발생하거나 감소시키는 것이 아닌, 어떠한 값으로 바꾸는 것이기 때문이다.

 

2. 다익스트라 비슷하게 값을 갱신시켜줄 수 있다.

1 에서 n 까지 현재까지 구한 최솟값을 ans[n]이라 하자. 그럼 노드 u에서 노드 v로 가는 간선을 j라 할 때, ans[v]가 s(j)보다 작거나 같다면, s(j)에서 볼 값은 항상 ans[v]에서 본 값의 부분집합일테니, 갱신시켜 줄 필요가 없다. 이 이유는 문제에서 주어진 a(i)의 값이 양수이기 때문이다. ans[v]의 값을 t라 하고 u 에서 v로 갈때 시간인 s(j)를 t`이라 하면, t <= t` 일 때, t + a(i) <= t` + a(i) 이다. 그러니 u에 t`에 도착했을 때 탈 수 있는 비행기들은 항상 t에 도착했을 때 탈 수 있는 비행기의 부분집합이다.

 

그럼 각 노드마다 간선을 r(j)를 기준으로 정렬시켜주고, 2번에서 관찰한 점을 만족한다면 큐에 넣어주고, 배열에서 삭제시켜주는 bfs를 생각할 수 있다. 간선을 정렬시켜주는 이유는 간선을 삭제시키는 연산을 빠르게 하기 위해서이다.

 

모든 간선을 최대 한번만 타기 때문에, 시간 복잡도는 간선 정렬 + bfs가 될 것 이다. 즉, O(M log M + N) 이 나온다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    c, r, d, s = map(int, input().split())
    adj[c].append((r, d, s))

for i in range(1, n + 1): adj[i].sort()

ans = [float("inf")] * (n + 1)
a = [0] + list(map(int, input().split()))

q = [(1, 0)]
tmp = []
ans[1] = 0
for cur, t in q:
    while adj[cur]:
        tmp.append((adj[cur][-1][1], adj[cur][-1][2]))
        adj[cur].pop()
q = tmp
while q:
    tmp = []
    for cur, t in q:
        ans[cur] = min(t, ans[cur])
        while adj[cur]:
            if adj[cur][-1][0] >= t + a[cur]:
                if ans[adj[cur][-1][1]] > adj[cur][-1][2]:
                    tmp.append((adj[cur][-1][1], adj[cur][-1][2]))
                adj[cur].pop()
            else: break
    q = tmp

for i in range(1, n + 1):
    if ans[i] == float("inf"): print(-1)
    else: print(ans[i])

참고로 다익스트라적인 접근은 필요 없는 접근이라고 한다. 그냥 상수커팅이 조금 된다. 이거까지 따지면 이 문제는 골드2 정도라고 생각하는데.. 흠

 

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

27846번: Bakery

이거 기하아닌가? 하고 뻘짓을 하다 섭테도 못긁었다. 현재 쿠키를 구울 때 걸리는 시간을 x라 하고, 머핀을 구울 때 걸리는 시간을 y라 하면, 각 입력마다 a(i) * x + b(i) * y <= c(i) 를 만족하면 된다.

 

이 문제의 정답인 총 사용한 moomie 양을 w라 할 때, w에 대한 파라매트릭 서치를 생각해보자. 

공식 풀이이다.

이러한 식을 만족해야하고, 우리는 이를 통해 가능한 x의 값의 범위를 구할 수 있다. 만약 x 의 범위가 존재하는 범위라면, w가 가능한 값이 될 것이다.

import sys
import math
input = sys.stdin.readline

def check(w):
    d = tc + tm - w
    lx = max(1, tc - w)
    hx = min(tc, tc + tm - w - 1)
    for i in range(n):
        if a[i] - b[i] < 0: lx = max(lx, math.ceil((-c[i] + b[i] * d) / (b[i] - a[i])))
        elif a[i] - b[i] > 0: hx = min(hx, (c[i] - b[i] * d) // (a[i] - b[i]))
        elif c[i] - b[i] * d < 0: return 0
    return lx <= hx

t = int(input())
for _ in range(t):
    asd = input()
    n, tc, tm = map(int, input().split())
    a, b, c = [0] * n, [0] * n, [0] * n
    for i in range(n): a[i], b[i], c[i] = map(int, input().split())

    lo, hi = -1, tc + tm - 2
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if check(mid): hi = mid
        else: lo = mid
    print(hi)

이렇게 식을 정리해서 범위를 구하는 류의 문제를 처음 풀어봐서 그런지, 굉장히 어렵게 다가왔다.