https://atcoder.jp/contests/abc255/tasks/abc255_e
\(A_1 = \alpha\) とおくと、
- \(A_2 = S_1 - A_1 = S_1 - \alpha\)
- \(A_3 = S_2 - A_2 = S_2 - S_1 + \alpha\) … となることがわかる。
\(T_1 = 0, T_k = \sum_{i=1}^{k-1} (-1)^{i+k+1}S_k\) とおくと、どんな \(A\) に対しても、 ある \(\alpha\) が存在して \(A_k = T_k + (-1)^{k+1} \alpha\) が全ての \(k\) に対して成り立つことがわかる。
\(F(i,\alpha) = |\{ k \mid T_k + (-1)^{k+1} \alpha = X_i \} |\) とする。 これは、 \(i, \alpha\) に対して、\(X_i = T_k + (-1)^{k+1} \alpha\) となる \(k\) を数えていることになる。\(T, X\) の条件から \(F(i,\alpha) \neq 0\) となる \(\alpha\) は絞り込むことができる。
あとは、\(i\) を動かして \(\sum_i F(i,\alpha)\) の最大値を取れば良い。