問題概要
$N$ 個のマスが一列に並んでいる．これらの $N$ 個のマスははじめ，白または青で塗られている．青色のマスは $M $ 個あり，それらの座標は数列 $A_i$ で与えられる（位置 $J$ について，$A_i = j$ なる $i$ が存在するとき，位置 $j$ のマスは青色である）．
この状況で，正整数 $k$ を一つ選び，幅 $k$ の判子を作る．判子を使うことで，連続する $k$ マスの色を赤に塗り替えることができる．ただし，このとき元々青色だったマスの色を塗り替えてはいけない．また、マス以外のものを塗ってもいけない（はみ出してはいけない）．
すべての白マスを赤マスに変えるとき，必要な判子の使用回数の最小値はいくらか？
制約
- $1 \leq N \leq 10^9$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq A_i \leq N$
- 各 $A_i$ は相異なる
解法
すぐに分かることとして，$k = 1$ とすることで $N - M $ 回の操作で目標を達成できることが確かめられます．従って，（達成できない場合に出力するべきものについての言及が無いことから推測（邪推？）可能ですが，）目標は常に達成可能です．また，直感的には，できるだけ大きい $k$ を選んで判子を作った方が，一度の操作でより多くのマスを塗り替えられるため有利に思えます．
（極大な）連続する白マスに着目しましょう．各白マスの塊の幅が $w_i$ だったとします．このとき，$\max\{ w \} < k$ なる $k$ を選んでしまうと，$k$ より小さい幅の白マスの塊に対して操作できないため，不適です．逆に，$k \leq \max\{ w \}$ なる $k$ を選べば，白マスの塊に対して判子がはみ出してしまうという事態は起こらず，適切に操作を行えば目標を達成できることが，いくつか例をイメージすると確かめられます（これだとやや議論が甘い気はしますが……）．
$k$ が定まったとき，幅 $w_i$ の白マスの塊について，必要な操作回数は $\lceil \frac { w_i } k\rceil$ です．式の導出がやや天下り的ですが，すでに塗り終わったマスとなるべく被らないようにしつつ，塊からはみ出ないように判子を使う様子を想像すると確かめられます．この式の値は，分母の $k$ を大きくすることで小さくできるため，$k = \max\{ w \}$ としておくのが最適です．
よって，$k = \max\{ w \}$ の値を値を求められれば，あとは算数（？）で問題を解くことができます．連続する白マスの幅というのは，基本的には，$A$ を昇順ソートしたときの隣接する要素の差に着目すると求められます．さらに言えば，$A_0 = 0, A_{ M + 1 } = N + 1$ だと思う（番兵を加える）ことで，盤面の端も統一的に扱えます．
従って，$A$ に番兵を追加した上でソートし，隣接する要素の差を使って算数をすることで問題を解くことができます．（このとき，隣接する要素が隣り合う整数であるときにはその部分を無視しないといけないことに注意します（「連続する白マス」がそもそも存在しないので）．）
このアルゴリズムは，$A$ のソートに一番時間がかかり，その時間計算量は $O( M \log M )$ です．算数部分は（適当な計算モデルを仮定すれば*1）それぞれ $O( 1 )$ 時間で計算できます．よって，$k$ が定まってからの答えの計算は $O( M )$ 時間です．
コード
int main() { IN( int, N, M ); VI A( M ); cin >> A; A.PB( 0 ); A.PB( N + 1 ); sort( ALL( A ) ); int k = N; REP( i, SZ( A ) - 1 ) { const int w = A[ i + 1 ] - A[i] - 1; if ( w == 0 ) { continue; } chmin( k, w ); } int res = 0; REP( i, SZ( A ) - 1 ) { const int w = A[ i + 1 ] - A[i] - 1; res += ( w + k - 1 ) / k; } cout << res << endl; return 0; }
*1:ビット長とかの話は考えたくないので……
