二分探索で求めることを考える.

このためには, \(k\) 匹のカエルが渡りきれるかどうかを判断しなければならない.

今ここで, \(i\) 番目の石の位置を \(x_i\) とする. このとき, カエルの最大ジャンプの距離をできるだけ小さくするには, \(0 \rightarrow x_i \rightarrow x_{i+k} \rightarrow \cdots\) と渡る方法になる. これで渡り切るためには, \(x_{i+k}-x_i \leq l\) とならなければならない. (ただし, \(x_0 = 0, x_{m+1} = w, m = \sum a_i\) である)

さて, これをすべての石について確認すると \(O(m)\) の計算量となって間に合わないが, よく見ると \(x_i = j\) となる最小の \(i\) についてだけ調べればいいことが分かる. すなわち, 区間 \([j-l, j)\) の石の数の和が \(k\) 以上であればいい. これは累積和を計算しておけば高速に計算できる.