Google Code Jam 2011 Round1B B. Revenge of the Hot Dogs
位置PにV個のホットドッグ屋がある時、それらを間隔Dで並べてさらに他のグループとも間隔Dなので、V*Dの幅の板を重ならないように、かつなるべく元の位置から動かさないように敷き詰めるイメージ。秒数が与えられたなら、なるべく左端に寄せて置いていくことが最善で、敷き詰めが可能かどうか判定できる。秒数を変えながら二分探索。DとPを倍にしておくと整数のまま計算できる。
class empty: pass; def check(C,D,V,t): p = -(10**100) for v in V: w = D*v.V r = t - D*(v.V-1)/2 if r<0 or p+w/2-v.P>r: return False p = max(v.P-r+w/2,p+w) return True T = input() for case in range(1,T+1): C,D = map(int,raw_input().split()) D *= 2 V = [] for i in range(C): t = map(int,raw_input().split()) V += [empty()] V[-1].P = t[0]*2 V[-1].V = t[1] l = 0 r = 10**100 while (r-l>1): m = (l+r)/2 if check(C,D,V,m): r = m else: l = m if check(C,D,V,0): r = 0 print "Case #%s: %.1f" % (case,r*0.5)