AtCoder Beginner Contest 255 E問題 Lucky Numbers

問題

提出解答

問題の概要

次を満たす長さ $N$ の整数列全体 $A=\left(A_i \right)_{i=1}^N$ の集合を $\mathcal{A}$ とする.

$i=1,2, \dots, N-1$ に対して, $A_i+A_{i+1}=S_i$ となる.

$A=\left(A_i \right)_{i=1}^N \in \mathcal{A}$ に対して, $\pi(A)$ を $A_j \in \{X_1, \dots, X_M\}$ となる $1$ 以上 $N$ 以下の整数の個数と定める.

このとき, $\displaystyle \max_{A \in \mathcal{A}} \pi(A)$ を求めよ.

制約

$2 \leq N \leq 10^5$
$1 \leq M \leq 10$
$-10^9 \leq S_i, X_j \leq 10^9$
$X_1 \lt X_2 \lt \dots \lt X_M$

解法1

実は次の定理が成り立つ.

定理 F.1.

$\mathbb{Z}$ を整数全体の集合とする. このとき, $\varphi: \mathcal{A} \to \mathbb{Z}, \psi: \mathbb{Z} \to \mathcal{A}$ を以下のようにして定めると, $\varphi, \psi$ は互いに逆写像になる. つまり, $\mathcal{A}, \mathbb{Z}$ の間には1対1対応がある.

$\varphi(A)$ を $A$ の初項とする.
$\psi(x)$ を初項が $x$ であり, $\mathcal{A}$ の元であるような整数列とする.

証明は各整数 $x$ に対して, $\psi(x)$ が well-defined であること. つまり $x$ を初項とし, 条件を満たすような整数列が唯一存在することを示せば良い. このとき, 和に関する条件を $i=1,2, \dots, N-1$ の順に見ていくことにより,

$A_1=x$
$A_1+A_2=S_1 \iff A_2=-x+S_1$
$A_2+A_3=S_2 \iff A_3=x+(-S_1+S_2)$
$\vdots$
$\displaystyle A_{i-1}+A_i=S_{i-1} \iff A_i=(-1)^{i-1} x+\sum_{j=1}^{i-1} (-1)^{i-j-1} S_j$
$\vdots$
$\displaystyle A_{N-1}+A_N=S_{N-1} \iff A_N=(-1)^{i-1} x+\sum_{j=1}^{N-1} (-1)^{N-j-1} S_j$

と一意に定まる. 以降では $\displaystyle T_i:=\sum_{j=1}^{N-1} (-1)^{N-j-1} S_j$ とする.

この定理 F.1. から, 求めるべきは

$\nu: \mathbb{Z} \to \mathbb{Z};~\nu=\pi \circ \psi$ としたときの, $\displaystyle \max_{x \in \mathbb{Z}} \nu(x)$ .

であることがわかる.

$E:=\{X_1, \dots, X_M \}$ としたとき, 整数 $x$ に対して,

$\displaystyle \begin{align} \nu(x) &=\sum_{i=1}^N \left[(-1)^{i-1} x+T_i \in E\right]\\ &=\sum_{i=1}^N \left[\exists j {\rm ~s.t.~} (-1)^{i-1} x+T_i=X_j \right]\\ &=\sum_{i=1}^N \sum_{j=1}^M \left[(-1)^{i-1} x+T_i=X_j \right] \\ &=\sum_{i=1}^N \sum_{j=1}^M \left[x= (-1)^{i-1} (X_j-T_i) \right]\\ \end{align}$