USACO 2016 US open (Bronze)

1. Diamond Collector

시작과 끝에 두개의 포인터를 두고 크기 차이가 k 이하면 뒤쪽을 전진, 이상이되면 앞쪽을 전진하는 방법으로 풀었다.

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

a.sort()
f = l = 0
tot = 1
ans = 0
while True:
    if f == n or l == n-1:
        break
    if a[l+1] - a[f] <= k:
        l += 1
        tot += 1
    else:
        f += 1
        tot -= 1
    ans = max(ans, tot)

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

2. Bull in a China Shop

입력이 크지 않아서 리스트를 회전시키면서 전부 탐색했다. 실제 리스트를 회전시키지 않고 a[j%n]의 형태로 인덱스만 탐색하는 방법도 있다.

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

ans = float("inf")

for i in range(n):
    cur = 0
    for j in range(1, n):
        cur += a[j]*j
    ans = min(ans, cur)
    l = a.pop()
    a.insert(0, l)

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

3. Load Balancing

N의 값은 작으나 좌표의 값이 크므로 좌표를 일일히 스캔할수는 없다. 각각의 소의 위치를 기준으로 x, y를 가로지르는 펜스를 구성하고 사분면에 해당하는 소의 수를 세는 방식으로 구성하면 100*100개의 조합에 대해서만 각각의 소가 어떤 사분면에 해당하는지 세면 된다.

xpos = []
ypos = []
with open("balancing.in", "r") as f:
    n, b = map(int, f.readline().strip().split())
    for _ in range(n):
        x, y = map(int, f.readline().strip().split())
        xpos.append(x)
        ypos.append(y)

ans = n # 한점에 모든 소가 모여있는 경우가 최악의 경우
for x in xpos:
    for y in ypos:
        xdiv = x+1
        ydiv = y+1
        d1 = d2 = d3 = d4 = 0
        for i in range(n):
            if xpos[i] < xdiv and ypos[i] > ydiv:
                d1 += 1
            elif xpos[i] > xdiv and ypos[i] > ydiv:
                d2 += 1
            elif xpos[i] < xdiv and ypos[i] < ydiv:
                d3 += 1
            else:
                d4 += 1
        m = max(d1, d2, d3, d4)
        ans = min(m, ans)

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