JMK no matter what

연습도 연습이지만, 과거만큼 연습에 시간을 쏟을 수 없는 지금 했던 셋을 전부 다시 도는 것보다는 문제 리뷰하고, 반드시 필요했던 critical insight 를 모아보고, 그 중 코딩이 중요하겠다 싶은 것만 다시 짜야겠다는... 핑계를 대본다. 이런게 바로 입코딩이라고

2009년 Qualification Round

구현, 구현, 동적 계획법의 구성.

• A: Alien Language: 길이가 일정한 단어들의 corpus 가 주어지고, 단어 패턴이 주어질 때 해당되는 단어의 수를 센다. 그냥 다 돌면서 되나 세어보면 되겠다. 그것도 정 귀찮으면 패턴의 () 를 [] 로 바꾼뒤 re.match(pattern + "$") -_-
• B: Watersheds: Union-find 로 구현하면 간단할듯? 제일 쉬운 방법은 그냥 각 칸마다 시뮬레이션해서 어디로 떨어질지 찾는것.
• C: Welcome to Code Jam: Counting DP.

2009년 Round 1A

brute-force (혹은 precalc), 최단거리, 동적 계획법의 구성.

• A: Multi-base happiness: 입력으로 주어지는 base 가 몇개 없기 때문에 precalc 해도 되고, 3n+1 최적화할때처럼 캐싱해도 된다. 'ㅅ'
• B: Crossing the Road: 신호등 사이클의 길이의 최소공배수를 구해서 해결... 이라고 말하고 싶었지만!! 그냥 최단거리 돌리면 된다. 각 정점까지의 최단거리에 따라 간선의 가중치가 달라진다는게 포인트일까나.
• C: Collecting Cards: 확률 동적 계획법. C[i] = C 개 모아야 하는데 그중 i 개 갖고 있을 때 몇개나 더 모아야 하나? 라고 정의. 하나 깐다고 해보자. 한개도 안겹치고 다 첨보는 카드가 나올 경우의 수는 binomial(C-i, N). x개 겹칠 경우의 수는 binomial(C-i, N-x) * binomial(i, x) 가 된다. 메모이제이션 고고싱.

2009년 Round 1B

파싱+구현, next_permutation, BFS 지만 키포인트는 답의 상한을 증명하는 문제의 구성. (C 는 당시에 풀려다가 걍 잔 문제라.. 해법이 확실하지 않다. -_-;)

• A: Decision Tree: 텍스트 파싱 및 tree traversing.
• B: The Next Number: std::next_permutation() 있으면 끝나는 문제.
• C: Square Math: 맨 뒤에서부터 BFS 해나간다. 만드는 숫자가 일정 범위를 벗어나면 안 만들게 하기. 한 square 에 query 가 여러번 주어지는데, query 마다 BFS 돌리지 말고 한번만 돌리는 게 키포인트. 이거 하고 나서도 좀 느려서 코어 세개로 나눠풀었다. i7 로.. 아 이런 수치스러울 데가.. C++ 로 짰으면 물론 시간안에 쉽게 나왔겠지만요. orz

어쨌건 소스.

lang:py
#!/usr/bin/python
import sys
import string
import numpy as np

def next(n, y, x):
    if y > 0: yield y-1, x
    if x > 0: yield y, x-1
    if y < n-1: yield y+1, x
    if x < n-1: yield y, x+1

M = 550

cache = {}
def reconstruct(n, y, x, make, grid, value, c):
#    import pdb; pdb.set_trace()
    if make == 0: return grid[y][x]
    if (y, x, make) in cache: return cache[(y, x, make)]
    RANGE = M
    length = c[y, x, make + RANGE]
    ret = "z"
    for y1, x1 in next(n, y, x):
        for y2, x2 in next(n, y1, x1):
            val = value[y2, x2]
            if grid[y1][x1] == '-':
                nmake = make + val
            else:
                nmake = make - val
            if nmake < -RANGE or RANGE < nmake: continue
            if c[y2, x2, nmake + RANGE] == length-1:
                ret = min(ret, grid[y][x] + grid[y1][x1] + reconstruct(n, y2, x2, nmake, grid, value, c))
    cache[(y, x, make)] = ret
    return ret

def solve(grid, queries):
    global cache

    min_length = {}
    not_solved = set(queries)

    RANGE = M
    n = len(grid)
    c = -np.ones((n, n, RANGE*2+1), dtype=int)
    value = np.zeros((n, n), dtype=int)
    cells = [(i, j) for i in xrange(n) for j in xrange(n)
             if grid[i][j] in string.digits]
    for y, x in cells: value[y, x] = int(grid[y][x])
    queue = [(y, x, 0) for y, x in cells]
    for y, x, v in queue:
        c[y, x, RANGE] = 0

    for query in queries:
        if any(value[y, x] == query for y, x in cells):
            min_length[query] = 0
            not_solved.remove(query)
    prevval = 0
    while len(queue) > 0:
        y, x, v = queue[0]
        curval = c[y, x, v + RANGE]
        if curval != prevval and len(not_solved) == 0:
            break
        prevval = curval
        queue = queue[1:]
        for y1, x1 in next(n, y, x):
            for y2, x2 in next(n, y1, x1):
                if grid[y1][x1] == '-':
                    nv = v - value[y, x]
                else:
                    nv = v + value[y, x]
                if nv < -RANGE or RANGE < nv: continue
                if c[y2, x2, nv + RANGE] == -1:
                    c[y2, x2, nv + RANGE] = curval + 1
                    if nv + value[y2, x2] in not_solved:
                        not_solved.remove(nv + value[y2, x2])
                        min_length[nv + value[y2, x2]] = curval + 1
                    queue.append((y2, x2, nv))

    cache = {}
    for query in queries:
        print min(reconstruct(n, y, x, query - value[y, x], grid, value, c)
                  for y, x in cells
                  if c[y, x, query + RANGE - value[y, x]] == min_length[query])
    sys.stdout.flush()

#rl = lambda: sys.stdin.readline().strip()
fn = open("C-large-practice.in")
rl = lambda: fn.readline().strip()

cases = int(rl())
lo, hi = 1, cases
if len(sys.argv) > 1:
    lo, hi = map(int, sys.argv[1:])

for case in xrange(cases):
    n, queries = map(int, rl().split())
    grid = np.array([rl() for i in range(n)])
    queries = map(int, rl().split())
    if lo <= case+1 <= hi:
        print "Case #%d:" % (case+1)
        solve(grid, queries)

나중에 위대한 입큰님 소스를 보니 나보다 훨 짧더라는... 신 ㅠㅠ 결론적으로는 뒤에서부터 돌릴 필요가 없었다. 차근하게 답의 바운드를 증명하는 것이 포인트.

2009년 라운드 1C

구현, 수학, 동적 계획법의 구성.

• A: All Your Base: 그냥 그리디하게 심볼 => 숫자 배정.
• B: Center of Mass: 직선의 평균은 직선. 따라서 직선과 점의 거리로 끗 ㄱㅅ
• C: Bribe the Prisoners: 한놈 내보내면 반으로 쪼개진다. Q^2 공간, Q^3 시간.