2009년 라운드 3
A. EZ-Sokoban
별다른 트릭 없이도 상태 공간 탐색으로 풀 수 있다. 최대 상태의 크기는 144^5 같지만 물론 이것보다 훨씬 작다. 대회 당시에도 그렇게 무리없이 풀었다.
B. Alphabetomials
당시엔 이지만 무식하게 돌려서 풀었던 듯싶다. 한참 고민해서 결국 풀긴 풀었다. thought process 를 대충 적어보면..
- 모든 p(S) 의 합을 계산하는 것인데, 각 텀별로 따로 계산하고 그 값을 더해도 된다는 것을 아는 것이 첫 번째 포인트.
- 이렇게 저렇게 부분 문제를 생각해 보려 했지만 별로 잘 되지 않았다. 가장 먼저 생각해본 건 C[k][S] = k개 골랐고, 각 글자의 출현 회수의 집합이 S 일 때.. 로 부분 문제를 잡아서 동적 계획법을 돌리는 건데. S 의 크기가 너무 커서 infeasible.
- 다른 방향으로 간단하게 풀어보면.. K=1 이면 쉽게 풀 수 있다. 다 돌아보면서 해 볼 수 있으니까. 이 경우의 답을 갖고 있다고 하자. K=2 를 쉽게 풀 수 있을까? 다 안해보고?
- 결국 답의 실마리를 발견한 것은 작은 예제에 대해 손으로 전개해 보는 것이었다. 여기서 내가 ab 와 cd 를 알고 있다고 하자. 이 때 (a+c)(b+d) 를 쉽게 알 수 있을까? 전개해 보면 ac+ad+bc+bd 가 나온다. abc 와 def 가 있으면 (a+d)(b+e)(c+f) 는 abc+abf+aec+aef+... 2^3 개의 텀으로 나온다.
- 좀더 일반화한 한두개에 대해서 해보자. aab 와 ccd 를 알고 있을 때 (a+c)(a+c)(b+d) 도 같은 꼴로 나온다. 당연하지만..
- 그러면 모든 단어 조합에 대해서 aab, ab, b, aa, 1 의 합을 알고 있으면 쉽게 둘을 합칠 수 있겠네.
- 남은 건 이게 여러 조합의 합이 있을 때 가능한가 한 것인데.. 이건 비교적 쉽게 증명한거 같다.
- 여기까지 와서 손으로 작은 거 하나 돌려보고 코딩했다.
lang:py
#!/usr/bin/python
import sys
rl = lambda: sys.stdin.readline().strip()
M = 10009
def solve(term, words):
chars = len(term)
c = [[0] * (2**chars) for i in range(k+1)]
# fill c[1]
for subset in range(2**chars):
for w in words:
mult = 1
for i in range(chars):
if subset & (2**i):
mult *= w.count(term[i])
c[1][subset] += mult
c[1][subset] %= M
for i in range(2,k+1):
for subset in range(2**chars):
for subsubset in range(2**chars):
if (subset & subsubset) != subsubset:
continue
a = c[i-1][subsubset]
b = c[1][subset - subsubset]
c[i][subset] += a*b
c[i][subset] %= M
total_set = (2**chars)-1
return [c[i][total_set] for i in range(0,k+1)]
def brute(term, words):
sol = [0] * (k+1)
cnt = [0] * len(term)
def recur(selected, cnt):
m = reduce(lambda a, b: a*b, cnt)
sol[selected] += m
if selected < k:
for w in words:
next_cnt = list(cnt)
for i in range(len(term)):
next_cnt[i] += w.count(term[i])
recur(selected+1, next_cnt)
recur(0, cnt)
return sol
t = int(rl())
for cc in range(t):
expr, k = rl().split()
k = int(k)
expr = expr.split("+")
n = int(rl())
words = [rl() for i in range(n)]
ret = [0] * (k+1)
for term in expr:
#sol = brute(term, words)
sol = solve(term, words)
for i in range(k+1):
ret[i] = (ret[i] + sol[i]) % M
print "Case #%d: %s" % (cc+1, " ".join(map(str, ret[1:])))
sys.stderr.write("did %d\n" % (cc+1))
결국 해결점은 작은 예제를 손으로 해 보면서 얻을 수 있었다.
C. Football Team
그래프를 그려보니 어? 이거 평면그래프네. 그럼 4컬러링은 무조건 되고 3컬러링만 하면 되겠구나. 싶었는데 컬러링 되나를 어떻게 알지.. 평면그래프 3컬러링도 np 컴플릿일텐데... 하고 orz 실제로 푼 사람들을 보니 bmerry 는 무려 그리디고 (헐, 이게 되나?) 백트래킹도 있고.. 다양하다.
easy 를 스위핑 하면서 dp 로 풀어볼까 했는데 어려워서 포기했는데, 오른쪽에서 왼쪽으로 쓸면 된단다. 아 맞다! 완전 천재 orz
한번 쭉 훑어보면서 괜찮은 솔루션을 배워봐야 할 듯.
D 는 이지를 당시에 풀긴 했지만 들여다 보지도 않았따. -_-
