AtCoder Beginner Contest 234 E 問題 Arithmetic Number

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

整数の10進法表記において, 各桁の数字が左から等差数列になるとき, その整数は等差列であるという. $X$ 以上の最小の等差列を求めよ.

制約

$1 \leq X \leq 10^{17}$

解法

長さが有限の等差数列は初項 $a$ と公差 $d$ と長さ $l$ で完全に決定づけられる. ここで, 各桁の数字は $0$ 以上 $9$ 以下でなくてはならないので, $1 \leq a \leq 9, -9 \leq d \leq 9$ である.

そして, 長さについて, $18$ 桁の等差列 $Y:=\underbrace{111,111,111,111,111,111}_{18}$ は制約から $X \leq Y$ となる. よって, 求めるべき整数は高々 $18$ 桁なので, $l \leq 18$ としても良い.

よって, $1 \leq a \leq 9, -9 \leq d \leq 9, l \leq 18$ なので, 調べるべき等差数列は高々 $9 \times 19 \times 18=3078$ 通りであり, 全列挙も容易にできる. 以上から, $3078$ 通りそれぞれにおいて, その等差数列が等差列 *1 で, $X$ 以上かどうかを見て, そのような等差列のうち最小の整数が答えになる.