No.72

$S$ が最大になる $x$ を求めるまでは No.71 と同様である. ただし, 制限が厳しいので全探索は使えない. そこで,

$$\begin{align*} S &= (x + 1)(N - x + 1) \\ &= -x^2 + Nx + N + 1 \\ &= -\biggl(x - \frac{N}{2}\biggr) + \frac{N^2}{4} + N + 1 \end{align*}$$

となるので, $S$ は $x = N/2$ のときに最大となる. ただし, $x$ は整数でなければならないので, $N \equiv 1 \pmod{2}$ のときは, $S$ は $x = \lfloor N/2 \rfloor$ のときに最大となる.