問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 個の整数 $A_1, \dots, A_N$ は全て $1$ または $-1$ である.

以下を満たすような整数列 $x=(x_1, \dots, x_N)$ は存在するか? 存在するならばその一例を求めよ.

$i=1,2, \dots, N$ に対して, $\lvert x_i \rvert \leq 10^{12}$
$x_1 \lt \dots \lt x_N$
$\displaystyle \sum_{i=1}^N A_i x_i=0$

制約

$1 \leq N \leq 2 \times 10^5$
$A_i \in \{1, -1\}$

解法

この問題において, 必要ならば $A_i$ の全ての符号を反転させることによって, $A_N=1$ と仮定しても一般性を失わない. 以降ではこの仮定のもとで問題を解くことにする.

$B=(B_i)_{i=1}^N$ を $\displaystyle B_i:=\sum_{j=i}^N A_j$ とする. また, 見やすさのため, $\alpha:=B_1$ とする.

ここで, 整数列 $y$ に対して, 第 $i$ 項以降に一様に $K$ を加えた整数列の総和は $y$ の総和に $B_i K$ を加えたものになることを利用して存在する場合の一例を構築する.

$\alpha \neq 0$ のとき

この場合は必ず存在する.

長さ $N$ の整数列 $y=(y_1, \dots, y_N)$ を次のように定める.

$i=1,2, \dots, N-1$ に対しては $y_i=i$ とする.
$\displaystyle \sum_{i=1}^N A_i i$ を $\lvert \alpha \rvert$ で割ったあまりを $r$ とする. このとき, $y_N=N+(\lvert \alpha \rvert-r)$ とする.

このようにすると, $y$ は以下を満たす.

$0 \leq y_1 \lt \dots \lt y_N \leq 2N$
$A_N=1$ であるから, $\displaystyle M:=\sum_{i=1}^N A_i y_i$ は $\lvert \alpha \rvert$ の倍数である.

そして, $x$ を

$x_i:=y_i-\dfrac{M}{\alpha}$

と定めると,

$\lvert x_i \rvert \leq 2N+\dfrac{\lvert M \rvert}{\lvert \alpha \rvert} \leq 2N+\dfrac{1}{2}N(N+1)=\dfrac{1}{2}N(N+5) \leq 10^{12}$
$x_1 \lt \dots \lt x_N$
$\displaystyle \sum_{i=1}^N A_i x_i=M-\alpha \cdot \dfrac{M}{\alpha}=0$

であるから, 要求されている条件全てを満たす.

$\alpha=0$ のとき

$B_1, \dots, B_N$ について, 以下のような場合分けが発生する.

(a) 任意の $i$ に対して, $B_i \geq 0$ の場合

条件を満たす列 $x$ が存在したとする.

このとき, $A_i=1$ である $i$ を昇順に $j_1, \dots, j_{N/2}$ , $A_i=-1$ である $i$ を昇順に $k_1, \dots, k_{N/2}$ とする. すると, 場合分けの仮定から, $l=1,2, \dots, \frac{N}{2}$ に対して, $j_l \gt k_l$ であるので,

$\displaystyle \sum_{i=1}^N A_i x_i=\sum_{l=1}^{N/2} (x_{j_l}-x_{k_l}) \gt 0$

となってしまい矛盾する. よって, 条件を満たす列 $x$ は存在しない.

(b) ある $i$ が存在して, $B_i \lt 0$ の場合

$B_i$ の定め方から, $B_p=-1$ となる $p$ が存在する. このとき, $\displaystyle M':=\sum_{i=1}^N A_i i$ として, $q$ を $M' \geq 0$ ならば $q=p$ , $M \lt 0$ ならば, $q=N$ とすると, 以下の $x$ が条件を満たす.