AtCoder Beginner Contest 267 C問題 Index × A(Continuous ver.)

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ が与えられる.

$A$ の長さ $M$ の連続部分列 $B=(B_1, \dots, B_M)$ における $\displaystyle \sum_{i=1}^M i \times B_i$ の最大値を求めよ.

制約

$1 \leq M \leq N \leq 2 \times 10^5$
$-2 \times 10^5 \leq A_i \leq 2 \times 10^5$

解法

長さ $N$ の整数列における長さ $M$ の連続部分列の個数は $(N-M+1)$ 個である. $B=(B_1, \dots, B_M)$ に対して,

$\displaystyle \operatorname{score}(B):=\sum_{i=1}^M i \times B_i$

とする.

このとき, $i=1,2, \dots, N-M+1$ に対して, $C_i$ を

$C_i=(A_i, A_{i+1}, \dots, A_{i+(M-1)})$

とする. なお, $C_1, \dots, C_{N-M+1}$ が $A$ における長さ $M$ の連続部分列全てである.

$i=2,\dots, N-M+1$ において,

$\displaystyle \begin{align} \operatorname{score}(C_i)-\operatorname{score}(C_{i-1}) &=\sum_{j=1}^M j \times A_{i+j-1}-\sum_{j=1}^M j \times A_{(i-1)+j-1} \\ &=M \times A_{i+M-1}+\sum_{j=1}^{M-1} j \times A_{i+j-1}-\left(A_{i-1}+\sum_{j=2}^M j \times A_{(i-1)+j-1} \right) \\ &=M \times A_{i+M-1}-A_{i-1}+\sum_{j=1}^{M-1} (j-(j+1)) \times A_{i+j-1} \\ &=M \times A_{i+M-1}-A_{i-1}-\sum_{j=1}^{M-1} A_{i+j-1} \\ \end{align}$

となるから,

$\displaystyle \operatorname{score}(C_i)=\operatorname{score}(C_{i-1})+ \left(M \times A_{i+M-1}-A_{i-1}-\sum_{j=1}^{M-1} A_{i+j-1} \right)$

である.

ここで, $\widetilde{A}=\left(\widetilde{A}_i, \right)_{0 \leq i \leq N}$ を

$\displaystyle \widetilde{A}_0=0, \quad \widetilde{A}_i=\sum_{j=1}^i A_j$

とすることによって,

$\displaystyle \sum_{j=1}^{M-1} A_{i+j-1}=\widetilde{A}_{i+M-2}-\widetilde{A}_{i-1}$

である.

よって,

$\operatorname{score}(C_1)$ を定義通り愚直に求める.
$i \geq 2$ に対しては $\displaystyle \operatorname{score}(C_i)=\operatorname{score}(C_{i-1})+ \left(M \times A_{i+M-1}-A_{i-1}-\left(\widetilde{A}_{i+M-2}-\widetilde{A}_{i-1} \right)\right)$ で求める.