2012년 당시보다는 푸는 것이 수월했다.
접기
A는 2012년 당시보다 매우 쉽게 정석대로 풀었다.
수식만 세우고, 필요한 계산만 하면 쉽게 풀렸다.
1시간도 안 걸렸던 것 같다.
B는 문제를 제대로 이해 못해서 한참 헤맸다.
sample input은 쉽게 통과했는데, 로직에 틀린 부분이 있어서 small input 푸는 것에 시간을 많이 보냈다.
틀린 부분을 못 찾고, 3시간 이상 걸려서 답 안 보고 푸는 것은 포기했다.
B-small-practice.out 을 github에서 찾아내고, 틀린 test case를 diff로 찾았다.
손으로 푼 결과랑 비교할 수 있게 로그를 남겼다.
답 등을 graph로 남겨서 변화를 알기 쉽게 만드는 것도 도움이 되겠다.
C는 무리다..
L, R 무시하고, 수식으로 풀 수 있을 것 같았는데, 머리가 잘 안 돌아간다.
해답을 보니, 수식만으로 푼 것 같지도 않다. 나중에 시간이 날 때, 해답을 읽어보고 다시 풀어봐야 하겠다.
L, R이 주어진 만큼, 이용을 해서 풀어야 하겠다.
접기 접기
#https://code.google.com/codejam/contest/1645485/dashboard import sysimport os sample = "sample" small = "A-small-practice" large = "A-large-practice" current = large fin = open (current + ".in" , "r" ) fout = open (current + ".out" , 'w' ) f1out = open (current + "1.out" , 'w' ) f2out = open (current + "2.out" , 'w' ) T = int (fin.readline())def solve(typed, N, ps): acc_ps = [] acc_p = 1 for p in ps: acc_p *= p acc_ps.append(acc_p) ss = [] for b in range (typed): strokes = acc_ps[typed - b - 1 ] * (N - typed + 2 * b + 1 ) + (1 - acc_ps[typed - b - 1 ]) * (N - typed + 2 * b + 1 + N + 1 ) ss.append(strokes) ss.append(2 + N) return min (ss)for i in range (T): typed, N = map (int , fin.readline().split()) ps = map (float , fin.readline().split()) solution = solve(typed, N, ps) answer = "Case #%d: %s" % (i+1 , str (solution)) fout.write(answer + ' \n ' ) fin.close() fout.close() f1out.close() f2out.close()
접기 접기
# https://code.google.com/codejam/contest/1645485/dashboard#s=p1 import sysimport osimport numpy as np sample = "sample" small = "B-small-practice" large = "B-large-practice" current = large fin = open (current + ".in" , "r" ) fout = open (current + ".out" , 'w' ) f1out = open (current + "1.out" , 'w' ) f2out = open (current + "2.out" , 'w' ) T = int (fin.readline()) completed = [] star1s = [] sorted_star2_indices = []def next_rush1(score): global star1s global sorted_star2_indices global completed if not sorted_star2_indices: return -1 for level in reversed (sorted_star2_indices): if (not completed[level]) and star1s[level] <= score: return level return -1 def next_challenge(): global star1s global sorted_star2_indices global completed if not sorted_star2_indices: return -1 return sorted_star2_indices[0 ]def rush1(level, stars, score): global star1s global sorted_star2_indices global completed if level >= 0 : completed[level] = True next = next_challenge() # print 'rush1+1', level, score, completed, sorted_star2_indices, next n_moves, more_scores = rush(next, stars, score + 1 ) return 1 + n_moves, 1 + more_scores return 0 , -1 def rush(level, stars, score): global star1s global sorted_star2_indices global completed if stars[level][1 ] <= score: sorted_star2_indices.remove(level) if completed[level]: # print 'rush2+1', level, score, completed, sorted_star2_indices, stars[level][1] return 1 , 1 else : # print 'rush2+2', level, score, completed, sorted_star2_indices, stars[level][1] return 1 , 2 return rush1(next_rush1(score), stars, score)def greater(a, b): global star1s if a[1 ] > b[1 ]: return 1 elif b[1 ] > a[1 ]: return -1 return star1s[b[0 ]] - star1s[a[0 ]]def solve(n_stars , stars): global star1s global sorted_star2_indices global completed n_moves = 0 total_score = 0 star1s = np.array(stars).T[0 ] star2s = np.array(stars).T[1 ] #sorted_star2_indices = [v[0] for v in sorted(enumerate(star2s), key=lambda x:x[1])] sorted_star2_indices = [v[0 ] for v in sorted (enumerate (star2s), cmp =greater)] sorted_star2_values = [v[1 ] for v in sorted (enumerate (star2s), cmp =greater)] # print "" # print star1s # print star2s # print sorted_star2_indices # print sorted_star2_values while sorted_star2_indices: level = next_challenge() move, more_scores = rush(level, stars, total_score) if move <= 0 : return 0 , -1 n_moves += move total_score += more_scores return n_moves, total_scorefor i in range (T): N = int (fin.readline()) stars = [] completed = [] for j in range (N): stars.append(map (int , fin.readline().split())) completed.append(False ) solution, score = solve(N, stars) solutionText = str (solution) if (solution > 0 ) else "Too Bad" answer = "Case #%d: %s" % (i+1 , solutionText) fout.write(answer + ' \n ' ) fin.close() fout.close() f1out.close() f2out.close()
접기
RECENT COMMENT