https://atcoder.jp/contests/abc255/tasks/abc255_e

A1=αA_1 = \alpha とおくと、

  • A2=S1−A1=S1−αA_2 = S_1 - A_1 = S_1 - \alpha
  • A3=S2−A2=S2−S1+αA_3 = S_2 - A_2 = S_2 - S_1 + \alpha … となることがわかる。

T1=0,Tk=∑i=1k−1(−1)i+k+1SkT_1 = 0, T_k = \sum_{i=1}^{k-1} (-1)^{i+k+1}S_k とおくと、どんな AA に対しても、 ある α\alpha が存在して Ak=Tk+(−1)k+1αA_k = T_k + (-1)^{k+1} \alpha が全ての kk に対して成り立つことがわかる。

F(i,α)=∣{k∣Tk+(−1)k+1α=Xi}∣F(i,\alpha) = |\{ k \mid T_k + (-1)^{k+1} \alpha = X_i \} | とする。 これは、 i,αi, \alpha に対して、Xi=Tk+(−1)k+1αX_i = T_k + (-1)^{k+1} \alpha となる kk を数えていることになる。T,XT, X の条件から F(i,α)≠0F(i,\alpha) \neq 0 となる α\alpha は絞り込むことができる。

あとは、ii を動かして ∑iF(i,α)\sum_i F(i,\alpha) の最大値を取れば良い。

https://atcoder.jp/contests/abc255/submissions/32403143