USACO 2015 US open (Bronze)

1. Moocryption

보드판을 전부 훑으면서 OXX의 패턴이 나타나는 문자열의 수를 전부 카운트 한다. 암호화가 한번은 되야 하므로 O의 자리에 M이 들어가거나 X의 자리에 O가 들어있으면 카운트하면 안된다.

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

d = dict()
dx = [1, 1, 0, -1, -1, -1, 0, 1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

for i in range(n):
    for j in range(m):
        for k in range(8):
            if 0 <= i+dy[k]*2 < n and 0 <= j+dx[k]*2 < m:
                if b[i][j] != 'M' and b[i][j] != b[i+dy[k]][j+dx[k]] == b[i+dy[k]*2][j+dx[k]*2] != 'O':
                    res = b[i][j]+b[i+dy[k]][j+dx[k]]+b[i+dy[k]*2][j+dx[k]*2]
                    if res in d:
                        d[res] += 1
                    else:
                        d[res] = 1

with open("moocrypt.out", "w") as f:
    if d.values():
        f.write(str(max(d.values()))+'\n')
    else:
        f.write("0\n")

2. Bessie Gets Even

각각의 변수가 짝수냐 홀수냐에 따라 수식의 결과가 달라진다는 점을 이용해서, 각각의 변수의 숫자를 짝수와 홀수의 수로 구분하면 2**7 꼴의 수의 조합만으로 결과를 찾아낼 수 있다.

d = {"B": [0, 0], "E": [0, 0], "S": [0, 0], "I": [0, 0], "G": [0, 0], "O": [0, 0], "M": [0, 0]}

with open("geteven.in", "r") as f:
    n = int(f.readline())
    for _ in range(n):
        w, num = f.readline().strip().split()
        num = int(num)
        if num % 2 == 0:
            d[w][0] += 1
        else:
            d[w][1] += 1

ans = 0
for b in range(2):
    for e in range(2):
        for s in range(2):
            for i in range(2):
                for g in range(2):
                    for o in range(2):
                        for m in range(2):
                            if ((b+e+s+s+i+e)*(g+o+e+s)*(m+o+o)) % 2 == 0:
                                ans += d['B'][b] * d['E'][e] * d['S'][s] * d['I'][i] * d['G'][g] * d['O'][o] * d['M'][m]

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

3. Trapped in the Haybales

일단 짚단의 거리순으로 정렬한 후, 하나의 구간당 왼쪽과 오른쪽을 뚫을 수 있는지 확인하고 전체 크기 안에서 가로막히는 구간이 존재한다면 해당 구간을 정답에 추가하면 된다.

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

a.sort(key=lambda x: x[1])
ans = 0

for i in range(n-1):
    dist = a[i+1][1] - a[i][1]
    lm = i
    rm = i+1

    while lm >= 0 and rm <= n-1:
        broke = False
        curdist = a[rm][1] - a[lm][1]
        if curdist > a[lm][0]:
            lm -= 1
            broke = True
        if curdist > a[rm][0]:
            rm += 1
            broke = True
        if not broke:
            break

    if lm >= 0 and rm <= n-1:
        ans += dist

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

4. Palindromic Paths

N=18 일때 처음부터 끝까지 완전탐색으로 찾아가는 경우의 수는 36!/(18!18!)이다. (아래로 가는 경로를 A, 오른쪽으로 가는 경로를 B라고 하면 결국 A와 B를 18개씩 사용하는 수열이므로, 전체 경우의 수 36!에, A, B가 각각 18번 나오므로 서로 순서가 바뀌어도 동일하니 나누어 주면 됨) 이 상태로는 탐색해야 할 크기가 너무 크므로 시작점에서 출발하고, 끝에서 거슬러 올라오는 탐색을 돌린 후 대각선에서 만나는 것을 탐색하면 경우의 수가 22^17번으로 줄어든다.

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

ans = 0
cand = set()
cand2 = set()

def f(y, x, path):
    path += b[y][x]
    if x+y == n-1:
        cand.add((path, x))
        return
    f(y+1, x, path)
    f(y, x+1, path)


def f2(y, x, path):
    path += b[y][x]
    if x+y == n-1:
        cand2.add((path, x))
        return
    f2(y - 1, x, path)
    f2(y, x - 1, path)

f(0, 0, '')
f2(n-1, n-1, '')

ans = set()
for r in cand & cand2:
    ans.add(r[0])

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