AtCoder Regular Contest 135 B問題 Sum of Three Terms

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次を満たす長さ $N+2$ の整数列 $A=\left(A_i \right)_{i=1}^{N+2}$ は存在するか? 存在するならばその一例を挙げよ.

$0 \leq A_i \quad (i=1,2, \dots, N+2)$
$A_i+A_{i+1}+A_{i+2}=S_i \quad (i=1,2, \dots, N)$

制約

$1 \leq N \leq 3 \times 10^5$
$0 \leq S_i \leq 10^9$

解法

$A_1=\alpha, A_2=\beta$ と固定すると, 2つ目の条件から, $A_3, A_4, \dots, A_{N+2}$ は (整数の範囲で) 一意に定まる. 以降では $\alpha, \beta$ を固定した際の $A$ を $g(\alpha, \beta)$ と書くことにする. このとき, $g(\alpha, \beta)$ のすべての項が非負になるような整数 $\alpha, \beta$ が存在するかを調べる.

ここで, 任意の非負整数 $\alpha, \beta$ に対して, ある整数 $F_1, F_2, \dots, F_{N+2}$ が存在して,

$g(\alpha, \beta)_i=\begin{cases} F_i+\alpha & (i=1,4,7,10,\dots) \\ F_i+\beta & (i=2,5,8,11, \dots) \\ F_i-\alpha-\beta & (i=3,6,9,12,\dots) \end{cases}$