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

問題原文

解法

$T$ 分で作業が終えることができる時、 $T + 1$ 分でも作業を終えられる。
つまり単調性があるので、答えを二分探索できる。

次に二分探索内の判定を考える。
これは左詰め（あるいは右詰め）をするように貪欲的に点検していくのが最適。
ただし以下の点に注意する必要がある。

答えの上界は $N$ ではない。
例えば $N = 100$ で $X_1 = 50$ とかだと折り返しが発生する。
だいたい $1.5N$ ぐらいに設定しておけばいい。（ $2N$ にしたけど）
まず左に残っている点検し残りを処理 → 元の位置まで折り返し → 余った分右に進んで続きを点検、
だけでなく、「（左に残っている点検し残りを処理できるように）右に進んで続きを点検 → 元の位置まで折り返し → 左に残っている点検し残りを処理」 がある。

２にたいそうやられてしまった。

実装

N, M = map(int, input().split())
X = [int(input()) for _ in range(M)] + [N + 1]  # 番兵
 
# にぶたん: T分で点検作業が終わるか？
ok, ng = 2 * 10 ** 9, -1
while abs(ok - ng) > 1:
    T = (ok + ng) // 2
    done = 0
    for i in range(M):
        left_remain = X[i] - done - 1
        if left_remain > T:
            break
 
        done = X[i] + max(max(0, T - 2 * left_remain), (T - left_remain) // 2)
        done = min(done, X[i + 1] - 1)
 
    if done >= N:
        ok = T
    else:
        ng = T
 
print(ok)