Facebook Hacker Cup 2011 Round 1A First or Last

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]