トップ > AtCoder > ABC255E - Lucky Numbers

ABC255E - Lucky Numbers

AtCoder AtCoder-Beginner Contest 全探索 手計算 Python

考え方

問題文から，
  • $A_{i}$を一つ決めれば「良い数列」はきまる
  • $O(MN)$くらいは許される
がわかる．よって，$A_{i} = X_{j}$となる$(i, j)$の組み合わせを全探索できそう．

$A_{i} = X_{j}$となるそれぞれの場合について，$A_{1}$が何になるかを求める．このとき，逆に$A_{1}$をこの値に選べば，$A_{i} = X_{j}$となる．つまり，

  1. 全ての$(i, j)$の組み合わせについて「$A_{i} = X_{j}$とした場合の$A_{1}$の値」を求め，
  2. 登場回数が最も多い$A_{1}$の値を選ぶのが最適となり，
  3. この「最大の登場回数」が求める答え
となる．

あとは，$A_{1}$の計算式を導けば良い．

0-indexedで考えると

\begin{aligned}
A_{1} &= S_{0} - A_{0} \\
A_{2}
&= S_{1} - A_{1} \\
&= S_{1} - S_{0} + A_{0} \\
A_{3}
&= S_{2} - A_{2} \\
&= S_{2} - S_{1} + S_{0} - A_{0} \\
\vdots \\
A_{n}
&=(-1)^{n+1} \sum_{i = 0}^{n-1} (-1)^{i} S_{i} + (-1)^{n} A_{0}
\end{aligned}
より，
\begin{aligned}
A_{0}
&=(-1)^{n} A_{n}
+ \underbrace{\sum_{i = 0}^{n-1} (-1)^{i} S_{i}}_{ = SS_{n}\;(SS_{0} = 0)}
\end{aligned}
と表せる．これを使えば，$A_{n}=x\in X$のときの$A_{0}$を計算できる．

回答例

from collections import defaultdict

N, M = map(int, input().split())
S = list(map(int, input().split()))
X = list(map(int, input().split()))

SS = [0] * N
for i in range(N - 1):
    add = - S[i] if i % 2 else S[i]
    SS[i + 1] = SS[i] + add

d = defaultdict(int)
for x in X:
    for i in range(N):
        key = SS[i]
        if i % 2:
            key -= x
        else:
            key += x
        d[key] += 1

print(max(d.values()))

参考

以下がわかりやすい．