CODE FESTIVAL 2015 予選A D - 壊れた電車 (python)

二分探索で最小値を探すやつ。蟻本３－１－３
二分探索は値の探索をするだけなので、最小回数で動作終わるようにするための必要十分な動作方法を、主に貪欲法で見つけてくる方に難易度が関わってくる。
今回は左端 ( X0 ) から順に arg回で、それより左側の列車の点検が全て終わっているもの中で、最も右側に進んでいるときの位置を毎回求めた。図を書いて必要十分になるように条件を作るのが大変だった。
あと python3 だと TLE した。( pypy だと 300ms で通った）

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
c = []
for i in range(m):
  x = int(input())
  c.append(x-1)
  
def is_ok(arg):
    global n,m
    new = -1
    for i in range(m):
      d = c[i]
      p = min(d,new+1)
      if d-arg > p:
        return False
      new = max(2*p-d+arg,d+(arg+p-d)//2)
    return new >= n-1


def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
  
print(meguru_bisect(-1,15*10**8))