良い数列 \(A\) の要素のうちいずれか \(1\) つの値を決めると、\(A\) の全体が一意に決まります。 例えば、\(A_1\) を \(Z\) に決めると、

• 条件 \(A_1 + A_2 = S_1\) より、\(A_ 2 = S_1 - Z\)
• 条件 \(A_2 + A_3 = S_2\) より、\(A_ 3 = S_2 - A_2 = S_2 - S_1 + Z\)
• 条件 \(A_3 + A_4 = S_3\) より、\(A_ 4 = S_3 - A_3 = S_3 - S_2 + S_1 - Z\)
• \(\cdots\)

と \(A_2, A_3, \ldots, A_N\) の値が順次、一意に決まります。 すなわち、\(A_1\) を \(Z\) とおくとき、\(i = 1, 2, \ldots, N\) について\(A_i\) は

\[ A_i = (-1)^{i+1} Z + B_i \]

と表せます。 ここで、数列 \(B = (B_1, B_2, \ldots, B_N)\) は

\[ B_i = \begin{cases} S_{i-1} - B_{i-1} & \text{if}\,\,\, i \geq 2\\ 0 & \text{if}\,\,\, i = 1 \end{cases} \]

で定まる数列です。 よって、本問題は「 \(Z\) をうまく選ぶことで \(A\) の要素のうちラッキーナンバーであるものの個数をどれだけ多くできるか」という問題に言い換えられます。

\(i = 1, 2, \ldots, N\) と \(j = 1, 2, \ldots, M\) の組 \((i, j)\) について、\(A_i\) がラッキーナンバー \(X_j\) と一致することは

\[ A_i = (-1)^{i+1} Z+ B_i = X_j \]

すなわち、

\[ Z = (-1)^{i+1} (X_j - B_i) \tag{1} \]

と同値です。 よって、すべての \(i = 1, 2, \ldots, N\) と \(j = 1, 2, \ldots, M\) の組 \((i, j)\) について、(1) の右辺の値

\[C_{i, j} := (-1)^{i+1} (X_j - B_i)\]

を計算し、得られる\(NM\)個の値を

\[C_{1, 1}, C_{1, 2}, \ldots, C_{N, M} \tag{2}\]

と並べるとき、(2) の中に最も多く登場する値 \(C^{\ast}\) を \(Z\) とすれば、数列 \(A\) の要素のうちラッキーナンバーであるものの個数が最大となります。 したがって、(2) における \(C^{\ast}\) の出現回数が本問題の答えとなります。 この出現回数を求めることは、連想配列を用いて \(\mathrm{O}(NM\log NM)\) 時間で可能です。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
#include <map>
using namespace std;
typedef long long ll;

ll n, m;
ll s[200005], x[15];
ll b[200005];

int main(void)
{
  cin >> n >> m;
  for(int i = 1; i <= n-1; i++) cin >> s[i];
  for(int i = 1; i <= m; i++) cin >> x[i];
  
  for(int i = 2; i <= n; i++) b[i] = s[i-1] - b[i-1];
  
  map<ll, ll> mp;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      ll c = x[j] - b[i];
      if(i % 2 == 0) c *= -1;
      mp[c]++;
    }
  }
  
  ll ans = 0;
  for(auto p : mp) ans = max(ans, p.second);
  cout << ans << endl;
  
  return 0;
}