[1] 連立 \(1\) 次方程式の解の構造

まずは \(A_i < 0\) となる場合も含めて、\(S_i = A_i + A_{i+1} + A_{i+2}\) が成り立つ数列 \(A\) がどのようなものかを考えます。

この等式は \(A_{i+2} = S_i - A_i - A_{i+1}\) と表すこともできます。したがって \(A_1, A_2\) を定めると、漸化式 \(A_{i+2} = S_i - A_i - A_{i+1}\) によって条件を満たす数列をちょうどひとつ作ることができます。

\(A_1 = a\), \(A_2 = b\) として計算すると、ある定数列 \((x_1, \ldots, x_{N+2})\) とパラメータ \(a, b\) によって、解は次のように表せることが分かります。

\[\begin{cases} A_i = x_i + a & (i = 1, 4, 7, \ldots)\\ A_i = x_i + b & (i = 2, 5, 8, \ldots)\\ A_i = x_i - a - b & (i = 3, 6, 9, \ldots)\\ \end{cases} \]

[2] 本問の解法

本問では、上の形の解のうち、任意の \(i\) に対して \(0\leq A_i\) となるものの存在判定・構築が求められています。これをパラメータ \(a, b\) に関する条件に書き直すと、次のような問題になります。

定数 \(c_1, c_2, c_3\) が与えられる。次の不等式をすべて満たすような \((a, b)\) の存在判定・構築をせよ：

• \(c_1\leq a\)
• \(c_2\leq b\)
• \(a+b\leq c_3\)

この問題の解は、以下のようになります：

• \(c_1 + c_2 > c_3\) ならば、解は存在しない
• \(c_1 + c_2\leq c_3\) ならば、\((a, b) = (c_1, c_2)\) が解のひとつを与える

以上をまとめると、本問は \(\Theta(N)\) 時間で解くことができます。

• 解答例 (Python)：https://atcoder.jp/contests/arc135/submissions/29021066