Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 240 F問題 Sum Sum Max

AtCoder ABC ABC240 F問題 500 pts

問題

提出解答

問題の概要

長さが $M$ の整数列 $A,B,C$ がある. これらはそれぞれ以下で与えられる.

$C$ の最初の $y_1$ 項は $x_1$ , 続く $y_2$ 項は $x_2, \dots,$ 最後の $y_N$ 項は $x_N$
$B$ は $C$ の累積和
$A$ は $B$ の累積和

このとき, $\max A$ を求めよ.

制約

$1 \leq T \leq 2 \times 10^5$
$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 10^9$
$|x_i| \leq 4$
$y_i \geq 1$
$\displaystyle \sum_{i=1}^N y_i=M$

解法

整数列 $A,B,C$ をそれぞれ $y_1$ 項, $y_2$ 項, $\dots, y_N$ 項で分割する. 分割した各列を $A^{(j)}, B^{(j)}, C^{(j)}$ とすると,

$C^{(j)}$ は定数列
$B^{(j)}$ は等差列
$A^{(j)}$ の一般項は $j$ の2次式で表される.

であることがわかる. 以降, 初項は第 $0$ 項であるとし, $A^{(j)}_k=p_j+q_j k+r_j k^2$ とする.

$p+q k+r k^2$ について考える. 実関数 $f(x)=p+qx+rx^2$ を考えることにより, $L \leq x \leq R$ における $f$ の最大値は

$r \geq0$ のとき, $\max(f(L), f(R))$ .
$r \lt 0$ のとき, $L \leq -\frac{q}{2p} \leq R$ ならば, $f(-\frac{q}{2p})$ , そうでなければ $\max(f(L), f(R))$

である.

ただし, $x$ は整数なので, $p \lt 0, L \leq -\frac{q}{2p} \leq R$ のとき, 基本的には

$\max \left(f \left(\left \lfloor -\frac{q}{2p} \right \rfloor \right), f \left(\left \lceil -\frac{q}{2p} \right \rceil \right)\right)$

である (引数が範囲外のときに注意).

このことに注意し, $B^{(j)}, A^{(j)}$ の各項を求め, $A^{(j)}$ の最大値を求め, 統合することにより, 計算量 $O(N)$ で解くことができる.