USACO 2015 February

1. Censoring

글자에서 해당 문자가 나타나는지 확인 후, 나타나면 삭제하는 문제. 문제에서 주어진 순서대로 문자를 삭제할 경우, 문자열 전체를 훑어야 하므로 TLE가 뜬다. 결과 문자열의 뒷부분이 일치하는지를 확인하는 방식으로 시간을 줄일 수 있다.

with open("censor.in", "r") as f:
    s = f.readline().strip()
    t = f.readline().strip()

r = ''
for i in range(len(s)):
    r += s[i]
    if len(r) >= len(t) and r[-len(t):] == t:
        r = r[:-len(t)]

with open("censor.out", "w") as f:
    f.write(r+"\n")

2. Cow

C가 나타나면 C의 개수를 하나 올리고, O가 나타나면 지금까지 센 C의 개수만큼 O의 개수를 올리고, W가 나타나면 O의 개수만큼 W를 증가시키면 W의 갯수가 총 COW의 개수이다.

with open("cow.in", "r") as f:
    n = int(f.readline().strip())
    s = f.readline().strip()

c = o = w = 0

for i in range(n):
    if s[i] == 'C':
        c += 1
    elif s[i] == 'O':
        o += c
    elif s[i] == 'W':
        w += o

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

3. Cow Hopscotch

N이 15이하로 매우 작으므로 BFS 이용해서 0, 0에서 도착점까지 도착하는 모든 경로를 세면 된다.

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

def bfs(y, x):
    if y == r-1 and x == c-1:
        return 1

    ans = 0
    for i in range(y+1, r):
        for j in range(x+1, c):
            if b[i][j] != b[y][x]:
                ans += bfs(i, j)
    return ans

with open("hopscotch.out", "w") as f:
    f.write(str(bfs(0, 0))+'\n')