AtCoder の 第一回日本最強プログラマー学生選手権決勝 の問題D Minimize Maximum です．
問題を読み間違えていて，「二分探索でできんじゃん」とか思っていたのですが，N だけじゃなくて任意の k について求めよ，という話だったんですね...．
公式の 解説 を読んでもよくわからなかったのですが，いろいろ調べてなんとなくわかってきたような気がするので，解説の行間を埋めてみます．
問題概要
整数列 $A_0, \ldots, A_{N-1}$; $B_0, \ldots, B_{N-1}$ ($A_i < B_i$) が与えられる．各 $k \in [2, N]$ について，整数 $C_i \in [A_i, B_i]$ を選び，$\max \{ C_{i+1} - C_i \mid 0 \leq i \leq k-2 \}$ を最小にせよ．
解法
$k \in [2, N]$ を固定します．$x, y \in [0, k-1]$, $x < y$ について，$\hat{L}_{xy} = (A_y - B_x) / (y - x)$ とします．ここでは，$\hat{L}_{xy}$ は整数とは限りません．ここで，このような $\hat{L}_{xy}$ が最大の値を取るような$x$, $y$ をとり，$L = \lceil \hat{L}_{xy} \rceil$ とすると，この $L$ が求める値であることを示します．そのためには，次の2つが言えれば良いです．
- 任意の列 $(C_i)_i$ について $\max_i(C_{i+1} - C_i) \leq L$ である．
- $\max_i(C_{i+1} - C_i) = L$ となる列 $(C_i)_i$ が取れる．
前者については，各$i$について $C_{i+1} - C_i \leq \hat{L}_{i, i+1}$ であることから明らかです．以下，後者を示します．
最大値を与える列 $(C_i)_i$ を定義するのですが，まず，$x \leq i \leq y$ なる $i$ について，$\hat{C}_i = B_x + (i-x)\hat{L}_{xy}$ とします．そして，以下のように$C_i$を定めます．
- $x \leq i \leq y$ については，$C_i = \lfloor \hat{C}_i \rfloor$．
- $i < x$ については，大きい方から順に，$C_i = \max(C_{i+1} - L, A_i)$．
- $i > y$ については，小さい方から順に，$C_i = \min(C_{i-1} + L, B_i)$．
$C_i \in [A_i, B_i]$ を示します．
まず，$x \leq i \leq y$ についてですが，$A_i$と$B_i$は整数ですから，$\hat{C}_i \in [A_i, B_i]$ を示せば十分です．もしそうでないとすると $\hat{C}_i < A_i$ または $B_i < \hat{C}_i$ になりますが，前者だとしますと $(i-x)\hat{L}_{xi} = A_i - B_x > \hat{C}_i - B_x = (i-x) \hat{L}_{xy}$ となってしまい，$x$, $y$ の取り方に反します．後者も同様です．
次に$i < x$ の場合ですが，$A_i \leq C_i$ であることは定義から明らかです．$B_i < C_i$ として矛盾を導くのですが，このような $i$ で最大のものを取ります．さらに，$i < p$，$C_p = A_p$ となる最小の $p$ を取ります．$C_y = A_y$ ですから，このような $p$ は存在します．すると，$j \in [i, p-1]$ に対して $C_{j+1} - C_j \geq \hat{L}_{xy}$ ですから，$B_i < C_i = A_p - \sum_{j = i}^{p} C_j \leq A_p - (p-i)\hat{L}_{xy} $ で， $\hat{L}_{xy} < \hat{L}_{ip}$ となり，$x$, $y$ の取り方に矛盾します．$i > y$ の場合も同様です．
以上で，$C_i \in [A_i, B_i]$ が示せました．
次に，$\max_{i} (C_{i+1} - C_i) = L$ を示します．$C_{i+1} - C_i \leq L$ であることはどの場合についても明らかですので，$x \leq i < y$ なる $i$ で，$C_{i+1} - C_i = L$ となる $i$ が存在することを言えば良いです．$\hat{L}_{xy}$ が整数である時にはこれは明らかです．そうでないとき，$\varepsilon_i = \hat{C}_i - C_i$ と書くことにします．$0 \leq \varepsilon_i < 1$ です．$C_{i+1} - C_i = \hat{C}_i + \hat{L}_{xy} - \varepsilon_{i+1} - (\hat{C}_i - \varepsilon_i) = \hat{L}_{xy} + (\varepsilon_i - \varepsilon_{i+1})$ なので，$C_{i+1} - C_i$ は，$L$ または $L-1$ に等しいことがわかります．すべての$C_{i+1} - C_i$ が $L-1$ に等しいと仮定すると，$\hat{L}_{x,y} = L-1$ となって，$\hat{L}_{x,y}$ が整数でないとしたことに反しますから，少なくとも一つの $i$ について，$C_{i+1} - C_i = L$ でなければなりません．
以上より，各$k$について，$\max_{0\leq x<y <k} \hat{L}_{xy}$ を求め (て小数部を切捨て) れば良いことがわかりました．$k$ の小さい方から順に求めていきます．
対象となる $\hat{L}_{xy}$ たちは，各$k$ が増えると，単調に増えていきます．(したがって，求める値は$k$に対して単調非減少です．) $k$ のときに増えるのは，$0\leq x < k-1$ に対する $\hat{L}_{x,k-1}$ ですから，これらの最大値を求めて，$k-1$ の時の値との max を取れば良いわけです．$f(x) = \hat{L}_{x,k-1}$ と書くことにします．
$f(x)$ は，2点 $P_x = (x, B_x)$ と $Q = (k, A_{k-1})$ を通る直線の傾きです．今，3点 $P_u$，$P_v$，$P_w$ ($u < v < w$) があったとして，$f(u), f(v), f(w)$ のうち最大のものが$f(v)$であるとすると，$P_v$は，$P_u$ と $P_w$ を結ぶ直線より下になければなりません．下図は $f(u) < f(w)$ の場合の絵ですが，$f(u) \geq f(w)$の時も同様です．つまり，$x \in [0, k)$ に対する点 $P_x$ たちの凸包の下半分に乗っている点だけを考えれば十分ということになります．
さらに，凸包上の点に限れば，$f$ が (上に向かって) 単峰であることがわかります．つまり，$u < v < w$ で $f(u) > f(v) < f(w)$ ということは起こりません．したがって，三分探索 で$f$の最大値を求めることができます．