USACO 2014 December

1. Marathon

전체 좌표들의 총 맨하탄 거리를 계산한 후 순서대로 한 점씩 뺀 상태로 계산해서 최소값을 찾으면 된다. 즉 A, B, C 가 있을 경우 B를 뺀다고 가정하면 A-B 거리와 B-C 거리를 빼고 A-C 거리를 더하는 방식으로 O(n)으로 훑으면 된다.

pos = []

with open("marathon.in", "r") as f:
    n = int(f.readline())
    for _ in range(n):
        pos.append(list(map(int, f.readline().strip().split())))

res = []
for i in range(1, n):
    res.append(abs(pos[i-1][0]-pos[i][0]) + abs(pos[i-1][1]-pos[i][1]))
ans = tot = sum(res)

for i in range(1, n-1):
    ans = min(ans, tot - res[i-1] - res[i] + abs(pos[i-1][0]-pos[i+1][0]) + abs(pos[i-1][1]-pos[i+1][1]))

with open("marathon.out", "w") as f:
    f.write(str(ans)+"\n")

2. Crosswords

2차원 리스트를 순서대로 돌면서 조건에 맞으면 정답에 추가하는 단순 구현 문제

b = []
with open("crosswords.in", "r") as f:
    n, m = map(int, f.readline().strip().split())
    for _ in range(n):
        b.append(list(f.readline().strip()))

ans = 0
res = []
for i in range(n):
    for j in range(m):
        if b[i][j] == '#':
            continue
        hori = vert = True
        if i-1 < 0 or (i > 0 and b[i-1][j] == '#'):
            for k in range(3):
                if i+k >= n or b[i+k][j] != '.':
                    vert = False
        else:
            vert = False

        if j-1 < 0 or (j > 0 and b[i][j-1] == '#'):
            for k in range(3):
                if j+k >= m or b[i][j+k] != '.':
                    hori = False
        else:
            hori = False

        if hori or vert:
            ans += 1
            res.append([i+1, j+1])

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

3. Cow Jog

따라잡히는 속도는 최소값에 의해 좌우되므로 입력을 거꾸로 거슬러 올라가며 최소 속도가 갱신될 때 그룹을 하나씩 추가하면 된다.

a = []
with open("cowjog.in", "r") as f:
    n = int(f.readline())
    for _ in range(n):
        a.append(list(map(int, f.readline().strip().split())))

min_s = 1000000001
ans = 0
for i in range(n-1, -1, -1):
    if a[i][1] <= min_s:
        ans += 1
        min_s = a[i][1]

with open("cowjog.out", "w") as f:
    f.write(str(ans)+'\n')

4. Learning by Example

입력된 소의 무게를 정렬하고, 각각의 무게별 구간을 나눈 후 앞의 소가 점이 있으면 앞 절반의 갯수를 ans에 추가하고, 뒤쪽의 소가 spot이 있으면 뒤쪽 절반의 갯수를 ans에 추가한다. 이때 구간은 [S+1, E]의 형태로 잡아서 같은 점이 두번 잡히지 않게 하며, 중앙을 나눌때는 왼쪽 소에 점이 있으면 [S+1, M]까지 추가하고, 오른쪽 소에 점이있으면 [M+1, E]을 추가한다. 이때 오른쪽 소에만 점이 있고, M이 정중앙에 있으면 M의 값이 추가되지 않을 수 있으므로 예외를 처리해줘야 한다.

c = []
with open("learning.in", "r") as f:
    n, a, b = map(int, f.readline().strip().split())
    for _ in range(n):
        s, w = f.readline().strip().split()
        w = int(w)
        s = 1 if s == 'S' else 0
        c.append([w, s])

ans = 0
c.append([-float("inf"), 0])
c.append([float("inf"), 0])
c.sort()

for i in range(n+1):
    s = c[i][0]
    e = c[i+1][0]
    m = (s+e)//2

    if c[i][1]:
        c_s = max(a, s+1)
        c_e = min(b, m)
        if c_e >= c_s:
            ans += c_e-c_s+1
    if c[i+1][1]:
        c_s = max(a, m+1)
        c_e = min(b, e)
        if c_e >= c_s:
            ans += c_e-c_s+1
    if c[i+1][1] and c[i][1] == 0 and s % 2 == e % 2 and a <= m <= b:
        ans += 1


with open("learning.out", "w") as f:
    f.write(str(ans)+'\n')