Code Festival 2015 予選A D - 壊れた電車

企業コンテスト
問題

n両編成の電車にm人の整備士が乗っており、最初i人目の整備士はa[i]両目にいる
各整備士は1分で隣の車両に移動することができ、今いる車両を一瞬で点検できる
全ての車両を少なくとも1人の整備士が点検するには最短何分かかるか
n <= 10^9, m <= 10^5

解法

i人目の整備士が区間[a[i]-L[i], a[i]+R[i]]を点検するとき、m個全ての区間が繋がっていてかつ
a[0]-L[0] = 1
a[m-1]+R[m-1] = n
が成り立てば良い

L[i], R[i]の値の決め方は？
まず一番左の整備士について考える
a[0]-L[0] = 1 より L[0] = a[0]-1が最低限必要で、R[0]は大きくすれば大きくするほどかかる時間は増える
逆に時間が先に決まっていればR[0]の最大値が決まるからやりやすい → 時間は二分探索すればいい
するとt分で全ての区間をカバーできるか判定する問題になる
[a[0]-L[0], a[0]+R[0]] を点検する経路は、a[0]-L[0]まで行ってから戻ってa[0]+R[0]に行くかその逆かの2択
つまり min(2L[0]+R[0], L[0]+2R[0]) 分かかる
これがt以下であるようなR[0]の最大値(=mxとする)を求める
で次の整備士は a[1]-L[1] = min(mx+1, a[1]) としてまた同様にR[1]の最大値を求め、それを新たなmxとする
これを繰り返していき、途中で区間が途切れる(∴ a[i]-mx-1がtを超える)ことなくR[m-1]がn以上になればok
R[i]を決めるときに0,1,2,と順番に試すとO(n)かかっちゃうから、そこも二分探索すればいい

実装

最初時間のニブタンの上限を10^9+10にしてて1ケース(03-09.txt)だけWAになったんだけど、例えば10^9車両あってど真ん中に1人だけ整備士がいる場合、どっちかの端に行ってから戻ってもう片方の端に行くと1.5 * 10^9分ほど必要になるから、多分こういうケースだと思う
で答えの最大値が1.5 * 10^9ということはニブタンの途中でl ≒ r = 1.5 * 10^9になる瞬間があって、intだといろんなとこでオーバーフローが起こり得るから、全体的にlong longにしとく必要もある

#define int long long

int n, m, a[114514], l = -1, r = 1e12+10;

bool ok(int t) {
	int mx = 0;
	rep(i,m) {
		int le = max(0ll, a[i]-mx-1), rl = 0, rr = t+1;
		if (le>t) return 0;
		while (rr-rl>1) {
			int ri = (rl+rr)/2;
			if (min(le*2+ri, le+ri*2)<=t) rl = ri;
			else rr = ri;
		}
		mx = a[i]+rl;
	}
	return n<=mx;
}

signed main() {
	cin >> n >> m;
	rep(i,m) cin >> a[i];
	while (r-l>1) {
		int t = (r+l)/2;
		if (ok(t)) r = t;
		else l = t;
	}
	cout << r << endl;
}