실제로 돌지 않았던 온사이트가 몇 개 있어서 하나 돌아봤다. 2008년 아메리카 로컬 온사이트 셋인데.. 구현 A 와 퍼즐 B, 탐색 C 와 이지만 풀 수 있을 듯한 D 의 구성이었다. A 랑 C 는 금방 풀었는데 B 에서 디버그하느라 시간을 한참 소비. 2시간 10분 정도 걸려서 D1 까지 다 풀었는데.. 2시간 반인줄 알고 여유롭게 했는데 실제론 2시간이었다. -_-; 젠장.
B 에서의 패인은.. 답이 안나왔을때 헐 이거 왜이래 하고 그냥 대충 고쳐버린 것. 나중에 예제를 손으로 풀어보니.. 이것은 나의 실수. -_-; 바보다... ㅠㅠ 실제론 B 는 제끼고 D1 까지만 풀었어도 온사이트에 갈 수 있었다. B 를 좀 더 빨리 풀었으면 페널티로 3~4등일듯..
A: Mixing Bowls
구현.
lang:py
#!/usr/bin/python
import sys
from collections import defaultdict as ddict
f = sys.stdin
rl = lambda: f.readline().strip()
def go(mixture):
bowls_needed = []
for needed in recipe[mixture]:
if needed.islower(): continue
bowls_needed.append(go(needed))
bowls = list(reversed(sorted(bowls_needed)))
if len(bowls) == 0: return 1
have = bowls[0]
ret = have
for b in bowls:
if have < b:
add = b - have
have += add
ret += add
have -= 1
if have == 0: ret += 1
#print "%s => %d" % (mixture, ret)
return ret
def solve(cc):
global recipe, ingredients
recipe = {}
ingredients = set()
n = int(rl())
for i in range(n):
line = rl().split()
recipe[line[0]] = line[2:]
for elem in line[2:]:
ingredients.add(elem)
for mixture in recipe.keys():
if mixture not in ingredients:
sol = go(mixture)
print "Case #%d: %d" % (cc, sol)
def main(case):
t = int(rl())
for cc in range(1,t+1):
if case == -1 or case == cc:
solve(cc)
if __name__ == "__main__":
args = sys.argv[1:]
if len(args) >= 1: f = open(args[0])
case = -1
if len(args) >= 2: case = int(args[1])
main(case)
B: Code Sequence
구현을 어떻게 할까 고민을 한참 했다. 결국 2^10 번만 돌아보면 된다는 것은 명확하다. 가장 쉬운 방법은 첫 번째 애의 하위 10비트가 무엇일까를 다 고민해보는 방법. 어느 경우에도 같은 답이 나오면 반환하고, 모호한 경우가 하나라도 있거나 다른 답이 나오면 unknown 을 찍으면 된다.
이 때, 마지막 숫자가 2진수로 1000 이고 그 다음에 출현할 것이 1001 차례면.. 4번째 비트에 해당하는 숫자가 뭔지 몰라도 다음 숫자를 찾을 수 있는데, 이걸 그냥 모호 처리했다가 예제가 안나왔다. 그래서 10비트를 적당히 n 에 비례해서 바꾸니 나오긴 나오는데.. 이게 바꾸는 게 말이 될 리가 없지 않은가? -_-; 결국 나중에 코드를 보면서 이거 맞나? 하고 예제 손으로 풀어보니 삽질이었다. 그거 하곤 가뿐히 둘다 패스.
lang:py
#!/usr/bin/python
import argparse, sys
from collections import defaultdict as ddict
f = sys.stdin
rl = lambda: f.readline().strip()
M = 10007
# None means doesn't make sense
# False means makes sense, but can't determine
def solve_for(seq, leftmost):
c = []
n = len(seq)
for bit in range(100):
value = False
for i in range(len(seq)-1):
me = leftmost + i
next = leftmost + i + 1
if (((me >> bit) & 1) == 0
and (me >> bit) + 1 == (next >> bit)):
me_value = seq[i]
next_value = seq[i+1]
for lower in range(bit):
if me & (1<<lower): me_value -= c[lower]
if next & (1<<lower): next_value -= c[lower]
hypothesis = (next_value - me_value + M) % M
if value == False:
value = hypothesis
elif value != hypothesis:
return None
if value == False:
break
c.append(value)
next = leftmost + n
last = next - 1
sol = seq[-1]
for i in range(100):
if (next ^ last) & (1<<i):
if i >= len(c):
return False
for i in range(len(c)):
if ((next ^ last) & (1<<i)):
if next & (1<<i):
sol += c[i]
else:
sol -= c[i]
sol = (sol + M) % M
sol = (sol + M) % M
return sol
def go(seq):
sols = set()
up = 1024
for leftmost in range(up):
cand = solve_for(seq, leftmost)
if cand != None:
sols.add(cand)
if len(sols) != 1: return False
return sols.pop()
def solve(cc):
rl()
seq = map(int, rl().split())
ret = go(seq)
print "Case #%d:" % cc,
if ret == False:
print "UNKNOWN"
else:
print ret
def main(case):
t = int(rl())
for cc in range(1,t+1):
if case == -1 or case == cc:
solve(cc)
if __name__ == "__main__":
args = sys.argv[1:]
if len(args) >= 1: f = open(args[0])
case = -1
if len(args) >= 2: case = int(args[1])
main(case)
C: Test Passing Probability
각 답의 조합들이 서로 상관이 없다는 것을 스스로에게 설득시키고.. 그러면 그냥 제일 가능성 있는 것부터 해나가면 된다. 우선 순위 큐로 탐색.
lang:py
#!/usr/bin/python
from operator import mul
import argparse, sys, heapq
from collections import defaultdict as ddict
f = sys.stdin
rl = lambda: f.readline().strip()
def solve(cc):
k, n = map(int, rl().split())
probs = [map(float, rl().split()) for i in range(n)]
for prob in probs: prob.sort(cmp=lambda a,b: cmp(b,a))
ret = 0.0
heap = []
init = (-reduce(mul, [prob[0] for prob in probs]), [0] * n)
seen = set()
heapq.heappush(heap, init)
for i in xrange(k):
if len(heap) == 0: break
prob, answers = heapq.heappop(heap)
prob = -prob
if prob == 0: break
ret += prob
#print prob, answers, ret
for question in xrange(n):
ans = answers[question]
if ans < 3:
nanswers = list(answers)
nanswers[question] += 1
if tuple(nanswers) in seen: continue
seen.add(tuple(nanswers))
np = prob * probs[question][ans+1] / probs[question][ans]
heapq.heappush(heap, (-np, nanswers))
print "Case #%d: %.12lf" % (cc, ret)
def main(case):
t = int(rl())
for cc in range(1,t+1):
if case == -1 or case == cc:
solve(cc)
if __name__ == "__main__":
args = sys.argv[1:]
if len(args) >= 1: f = open(args[0])
case = -1
if len(args) >= 2: case = int(args[1])
main(case)
D: King
하드는 안드로. 이지는 캐쉽다.
lang:py
#!/usr/bin/python
import argparse, sys
from collections import defaultdict as ddict
f = sys.stdin
rl = lambda: f.readline().strip()
def wins(king, state):
key = (king, state)
if key in cache: return cache[key]
ret = False
y, x = king / w, king % w
for ny in range(y-1,y+2):
for nx in range(x-1,x+2):
if 0 <= ny < h and 0 <= nx < w:
if state & (2**idx[ny][nx]):
continue
if not wins(idx[ny][nx], state + (2**idx[ny][nx])):
ret = True
break
if ret: break
cache[key] = ret
return ret
def solve(cc):
global h, w, board, idx, cache
cache = {}
h, w = map(int, rl().split())
board = [rl() for i in range(h)]
idx = [[i*w+j for j in range(w)] for i in range(h)]
state = 0
king = -1
for i in range(h):
for j in range(w):
if board[i][j] != '.':
state += (2**idx[i][j])
if board[i][j] == 'K':
king = idx[i][j]
print "Case #%d: %s" % (cc, "A" if wins(king, state) else "B")
def main(case):
t = int(rl())
for cc in range(1,t+1):
if case == -1 or case == cc:
solve(cc)
if __name__ == "__main__":
args = sys.argv[1:]
if len(args) >= 1: f = open(args[0])
case = -1
if len(args) >= 2: case = int(args[1])
main(case)
