USACO 2015 January

1. Cow Routing

입력에서 A, B가 순서대로 존재하는지 확인하면서 이동가능한 루트가 존재하면 최소 가격과 비교해서 갱신하면 되는 문제

ans = float('inf')
with open("cowroute.in", "r") as f:
    a, b, n = map(int, f.readline().strip().split())
    for _ in range(n):
        cost, city_num = map(int, f.readline().strip().split())
        cities = list(map(int, f.readline().strip().split()))
        flag = False
        for city in cities:
            if city == a:
                flag = True
            if city == b and flag:
                ans = min(ans, cost)


with open("cowroute.out", "w") as f:
    if ans == float('inf'):
        f.write(str(-1)+'\n')
    else:
        f.write(str(ans)+'\n')

2. Cow Routing II

전 문제와 동일하나 이번에는 두개의 루트를 선택해서 이동 가능. 단순히 A와 B루트를 덧붙여서 1번 문제와 같은 방식으로 돌리면 TLE가 뜨므로 시간을 줄일 방법을 찾아야 함. 루트에 A나 B가 존재하면 A까지의 루트, A 다음의 루트, B 이전의 루트로 루트를 구분 그 이후 A 다음의 루트와 B 이전의 루트의 교집합이 존재하면 A 에서 B로 이동가능하다는 의미이므로 최소값 계산에 이용하면 됨.

ans = float('inf')
routes = []
costs = []
with open("cowroute.in", "r") as f:
    a, b, n = map(int, f.readline().strip().split())
    for _ in range(n):
        cost, city_num = map(int, f.readline().strip().split())
        costs.append(cost)
        routes.append(list(map(int, f.readline().strip().split())))

se = [[set(), set(), set()] for _ in range(n)] # till_a, after_a, till_b,

for i in range(n):
    s = set()
    s2 = set()
    flag = False
    for city in routes[i]:
        s.add(city)
        s2.add(city)
        if city == a:
            se[i][0] = s
            s = set()
            flag = True
        if city == b:
            se[i][2] = s2
            s2 = set()
        if city == b and flag:
            ans = min(ans, costs[i])
    se[i][1] = s

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if se[i][0] and se[j][2] and (se[i][1] & se[j][2]):
            ans = min(ans, costs[i]+costs[j])

with open("cowroute.out", "w") as f:
    if ans == float('inf'):
        f.write(str(-1)+'\n')
    else:
        f.write(str(ans)+'\n')

3. It’s All About the Base

뭔가 신박한 알고리즘이 있을지 알고 고민하다가 떠오르는게 없어 정답을 봤는데 전혀 그런거 없다. 단순하게 두 숫자를 10진법부터 변환하고 크기가 더 작은 수에 대해 진법을 하나씩 더 올려 계산하며 같은 숫자를 찾으면 된다. python으로 3초 가까운 시간이 걸리는데도 TLE가 뜨지 않는다.

res = []
with open("whatbase.in", "r") as f:
    k = int(f.readline())
    for _ in range(k):
        x, y = f.readline().strip().split()
        X = Y = 10
        while X <= 15000 and Y <= 15000:
            num_x = int(x[0])*X*X + int(x[1])*X + int(x[2])
            num_y = int(y[0])*Y*Y + int(y[1])*Y + int(y[2])
            if num_x < num_y:
                X += 1
            elif num_y < num_x:
                Y += 1
            else:
                res.append([X, Y])
                break


with open("whatbase.out", "w") as f:
    for r in res:
        f.write(str(r[0])+" "+str(r[1])+"\n")

4. Meeting Time

N이 1~16개 이고 단방향으로 가므로 Bessie와 Elsie에 대해 목적지까지 가는 패스를 전부 계산해서 cost를 저장한 후, 두 패스 중 겹치는 최소값을 찾으면 된다. BFS를 이용해서 경우의 수를 찾고, 해당 값을 set에 저장한 후 교집합의 최소값을 출력하는 방식으로 해결했다.

from _collections import deque
b_cost = set()
e_cost = set()
path = dict()
with open("meeting.in", "r") as f:
    n, m = map(int, f.readline().strip().split())
    for i in range(n):
        path[i] = []
    for _ in range(m):
        a, b, c, d = (map(int, f.readline().strip().split()))
        path[a].append([b, c, d])

q = deque([[1, 0]])

while q:
    cur, cost = q.popleft()
    if cur == n:
        b_cost.add(cost)
    else:
        for p in path[cur]:
            q.append([p[0], cost+p[1]])

q = deque([[1, 0]])
while q:
    cur, cost = q.popleft()
    if cur == n:
        e_cost.add(cost)
    else:
        for p in path[cur]:
            q.append([p[0], cost+p[2]])

with open("meeting.out", "w") as f:
    if b_cost & e_cost:
        f.write(str(min(b_cost & e_cost))+"\n")
    else:
        f.write("IMPOSSIBLE\n")