Facebook Hacker Cup 2011 Round 1A First or Last
動的計画法。t番目の曲がり角で抜いたときのクラッシュの確率をp1[t]、抜かなかったときのクラッシュの確率をp2[t]、直後にr番目である確率をP[t][r]とすると、
P[t][r] = max(P[t-1][r+1]*(1-p1[t]),P[t-1][r]*(1-p2[t]))。
Pythonだと分数が使えるので楽。
N = input() from fractions import Fraction for testcase in range(N): tmp = map(int,raw_input().split()) R,T = tmp[:2] p1,p2 = [],[] for i in range(T): p1 += [Fraction(1,tmp[i*2+2])] p2 += [Fraction(1,tmp[i*2+3])] P = [Fraction(0)]*R+[Fraction(1),Fraction(0)] for t in range(T): B = P[:] for r in range(1,R+1): P[r] = max(B[r+1]*(1-p1[t]),B[r]*(1-p2[t])) print P[1]