AtCoder Beginner Contest 255 C問題 ±1 Operation 1

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

初項 $A$ , 公差 $D$ , 項数 $N$ の等差数列を $S$ とする.

最初, 整数 $X$ が与えられる. $X$ が $S$ の要素であるようにするために, 以下の操作は最低でも何回 ( $0$ 回以上) しなければならないか?

次のうちどちらかを選び実行する.
- $X$ に $1$ 加算する.
- $X$ から $1$ 減算する.

制約

$-10^{18} \leq X,A \leq 10^{18}$
$-10^6 \leq D \leq 10^6$
$1 \leq N \leq 10^{12}$

解法

$S$ の情報として必要なのは $S$ にどのような整数が存在するかなので, 必要ならば $D \geq 0$ としても問題ない. なお, $D \lt 0$ のときは以下のようにして $D \geq 0$ とすることができる.

$(A,D) \gets (A+D(N-1), -D)$

ここで, できる操作は $+1$ または $-1$ しかないので, 最小回数を達成させるためには, $X$ に最も近い $S$ の要素に $X$ を目指さなければならない.

今, $D \geq 0$ なので, $S$ は単調増加である. よって, $S$ の初項と末項をそれぞれ $S_{\rm first}, S_{\rm last}$ としたとき,

$X \leq S_{\rm first}$ のとき, 目指すべきは $S_{\rm first}$ となるので, 答えは $S_{\rm first}-X$ である.
$S_{\rm last} \leq X$ のとき, 目指すべきは $S_{\rm last}$ となるので, 答えは $X-S_{\rm last}$ である.
$S_{\rm first} \lt X \lt S_{\rm last}$ のとき, $S$ に存在する $X$ 以下の最大の要素を $\alpha$ , $X$ 以上の最小の要素を $\beta$ としたとき, 目指すべきは $\alpha$ または $\beta$ なので, 答えは $\min(X-\alpha, \beta-X)$ である.

最後に, $\alpha, \beta$ の求め方を述べる. 今, $S_{\rm first} \lt S_{\rm last}$ なので, $D \gt 0$ である. このとき, $A$ を $D$ で割った余りを $R$ としたとき,

$\displaystyle \alpha=D \times \left \lfloor \dfrac{X-R}{D} \right \rfloor+R, \quad \beta=D \times \left \lceil \dfrac{X-R}{D} \right \rceil+R$

である.

補足

なお, $X$ と $S$ の項を全て同じだけスライドさせても結果は変わらないということに注目すると, 最初に $X$ と $S$ の項を $-A$ だけスライドさせると, $S_{\rm first}=0$ 及び, $R=0$ となるので, $\displaystyle \alpha=D \times \left \lfloor \dfrac{X}{D} \right \rfloor, \beta=D \times \left \lceil \dfrac{X}{D} \right \rceil$ となり, 実装がやや楽になる.