まず,漸化式に出てくる項を減らしたい.
\(a_{i} \geq 0\) の条件を無視する. \(S_{i}, S_{i+1}\) の変化を調べると, \(a_{i}, a_{i+3}\)だけが異なり,\(a_{i+1}, a_{i+2}\) は共通している. 式 \(-a_{i} + a_{i+3} = - S_{i} + S_{i+3}\) を得るので, 3つおきに \(a\) が決まることが分かる. \(a_{i}\) たちは, 基本的に\(i \ mod \ 3\) で分けて考えてよさそうで, \(a_{i}, i \ \in \ 3\) だけ決めれば残りは \(S\) から一意に決まる.
次に \(a_{i} \geq 0\) の条件を考える. \(a_{j}, j \ \in \ 3\) を決めると,
\(x_{j} := [ a_{j+k} \vert \ (k = 0, 3, 6, \cdots) ] \)
が決まるので, \(a_{j}\) を水増しして \(a_{j+k}\) が \(0\) 以上になるように 調整する. 暫定的に \(a_{j} = 0\) としてしまい, \(a_{j}\) を \(min(x_{j})\) で取り直せばよい.
ただし, \(a_{0} + a_{1} + a_{2} = S_{0}\) にしないといけないので, \(a_{0}, a_{1}\) を上の決め方をして, \(a_{2} := S_{0} - (a_{0} + a_{1})\) とする. ここで \(a_{2} \geq 0\) を満たしているのが, 条件を満たす \(a\) が取れる必要十分条件.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"