問題

整数列 $A_0, A_1, \cdots, A_{N-1}, B_0, B_1, \cdots, B_{N-1}$ が与えられ、 $C_0, C_1, \cdots, C_{N-1}$ を、 $A_i \leq C_i \leq B_i$ を満たすようにとる。 $k (2 \leq k \leq N)$ に対し、整数列 $C_0, C_1, \cdots, C_{k-1}$ の「 $C_{i+1} - C_i$ の最大値」の最小値を求める。

考察

ある区間 $l, r(0 \leq l \lt r \lt k)$ で、「[tex: C{i+1} - C_i] の最大値」の最小値を考える。また、[tex: C{i+1} - C_i]は $(i, C_i)$ グラフの変化率と考えることができる。

$C_{r}$ はなるべく小さく、 $C_l$ はなるべく大きい方がいい。よって、 $C_l = B_l, C_{r} = A_{r}$ 。ここで、他の $C_i$ について、 $A_i \leq C_i \leq B_i$ を無視すると、

$C_{r} - C_l = \sum_{i = l}^{r-1} C_{i+1} - C_i$

より、有理数の範囲で $C_{i+1} - C_i$ の最大値を最小にするには、全ての $C_{i+1} - C_i$ を一定にすればよい。このとき $C_{i+1} - C_i = \frac{C_{r} - C_l}{r-l} = \frac{A_{r} - B_l}{r-l}$ より、 $C_i = C_l + (i-l) \cdot \frac{A_r - B_l}{r-l}$ 。

この区間で、全ての $i$ について条件が満たされているとする。すると、変化率の最大値の最小値 $m$ は $m = \frac{A_{r} - B_l}{r-l}$ 。任意の $i, j(l \leq i \lt j \leq r)$ について、 $C_i \leq B_i, A_j \leq C_j$ より $\frac{A_j - B_i}{j-i} \leq \frac{C_j - C_i}{j-i} = m$ 。よって、このような区間で、 $m = \max_{l \leq i \lt j \leq r}\frac{A_j - B_i}{j-i}$ 。これは、

つぎに、 $A_i \leq C_i \leq B_i$ を満たさない最小の $i$ について考える。 $C_i \gt B_i$ のとき、 $C_i \leftarrow B_i$ で更新する。すると、

$l$ から $i$ の区間での変化率は $\frac{C_{i} - C_l}{i-l} \lt \frac{A_{r} - B_l}{r-l}$
$i$ から $r$ の区間での変化率は $\frac{C_r - C_i}{r-i} \gt \frac{A_{r} - B_l}{r-l}$

前者は、変化率が減少しているので、変化率の最大値はこの区間ではない（この区間では変化率は真に減少するので）。後者は、この区間で変化率の平均をこれ以上小さくできないでの、これよりも最大値を小さくする更新はない。また、 $B_i$ 未満で更新するとき、変化率がより大きくなってしまうので、 $B_i$ をとることが最善である。

$l$ から $r$ の区間での変化率の最大値の最小値 $m$ は、 $m \geq \frac{C_r - C_i}{r-i} \gt \frac{C_i - C_l}{i-l} \geq \frac{A_q - B_p}{q-p} (l \leq p \lt q \leq i)$ 。

同様に、 $C_i \lt A_i$ のとき、 $C_i \leftarrow A_i$ で更新すると、

$l$ から $i$ の区間での変化率は $\frac{C_{i} - C_l}{i-l} \gt \frac{A_{r} - B_l}{r-l}$
$i$ から $r$ の区間での変化率は $\frac{C_r - C_i}{r-i} \lt \frac{A_{r} - B_l}{r-l}$

今度は、後者で変化率が減少し、前者は $A_i$ で更新するのが最前であることがわかる。

この更新後、 $l$ から $i$ の区間での変化率の最大値は、条件を満たさなくなる $s(l \lt s lt i)$ もうち、 $\max \frac{A_s - B_i}{s-i}$ である。 $m \geq \max \frac{A_s - B_i}{s-i} \gt \frac{C_i - C_l}{i-l} \geq \frac{A_q - B_p}{q-p} (l \leq p \lt q \leq i)$

以上より、帰納法によって、ある区間 $l, r(0 \leq l \lt r \lt k)$ で $m = \max_{l \leq i \lt j \leq r} \frac{A_j - B_i}{j-i}$ であることが示せた。求めるのは $0$ から $k-1$ の区間なので、各 $k$ についての答えは $\max_{0 \leq i \lt j \leq k-1}\frac{A_j - B_i}{j-i}$

有理数の範囲で議論したが、結局 $m$ を小数以下切り上げすれば整数の範囲での解が得られる。

解法

$k \geq 2$ について、

$m_k = \max_{0 \leq i \lt j \leq k-1}\frac{A_j - B_i}{j-i} = \max(\max_{0 \leq i \lt j \leq k-2}\frac{A_j - B_i}{j-i}, \max_{0 \leq i \lt k-1}\frac{A_{k-1} - B_i}{k-i-1})=\max(m_{k-1}, \max_{0 \leq i \lt k-1}\frac{A_{k-1} - B_i}{k-i-1})$

より、 $\max_{0 \leq i \lt k-1}\frac{A_{k-1} - B_i}{k-i-1}$ を高速で求められればよい。

$p, q, r (0 \leq p \lt q \lt r \lt k-1)$ において、 $\frac{A_{k-1} - B_q}{k-q-1} \geq \frac{A_{k-1} - B_p}{k-p-1}$ かつ $\frac{A_{k-1} - B_q}{k-q-1} \geq \frac{A_{k-1} - B_r}{k-r-1}$ となるためには、 $B_q$ が $(p, r)$ を結んだ線分より下側にある必要があるので、このような点（凸包）だけ保持して三分探索を行う。