1000
どうも最大値として使う区間と、それに対応する最小値から、N-1個の分割が可能かどうかの判定がまずかったっぽい。
いくつ分割が可能か、という情報ではなく、上限と下限を持つようにしていたのが問題。(後述)
問題は、全部の値について可能かどうか判定すると、上限下限と比較して(N-1)/2倍遅くなること。仕方がないので、最小値として可能な値が2500個程度あるのを、バイナリサーチにすることに。(実際には入力の整数範囲全部をバイナリサーチしてしまったが...。)
ある整数配列をmin以上max以下に分割するとき、A個の分割とB個の分割(A
