C - ±1 Operation 1 Editorial by miscalculation53

数個を全探索する別解

\(D = 0\) のとき、「良い数」は \(A\) しかないので、答えは \(|A - X|\) です。以下 \(D \neq 0\) とします。

「良い数」は、\(0 \leq k \leq N - 1\) を満たす整数 \(k\) を用いて \(A + kD\) と表される整数です。ここで、いったん \(k\) の範囲を無視して考えると、整数 \(k\) を用いて \(A + kD\) と表される整数のうちで \(X\) に「ある程度」近いものとして \(A + \lfloor \frac{X - A}{D} \rfloor D\) がとれます(\(\lfloor x \rfloor\) で実数 \(x\) 以下の最大の整数を表します)。あとはこの付近の数個を探索すれば、\(X\) に最も近い整数が求まります。この付近に \(A\)\(A + (N - 1)D\) の間にある整数が存在しないときは、\(A\)\(A + (N - 1)D\)\(X\) に最も近い整数になります。(\(A + kD\)\(k\) に対して単調性をもつことに注意)

なお実際には、\(D > 0\) のときは \(A + \lfloor \frac{X - A}{D} \rfloor D \leq X \leq A + \lceil \frac{X - A}{D} \rceil D\) が、\(D < 0\) のときは \(A + \lceil \frac{X - A}{D} \rceil D \leq X \leq A + \lfloor \frac{X - A}{D} \rfloor D\) が成り立つため、調べる値は \(A + \lfloor \frac{X - A}{D} \rfloor D\)\(A + \lceil \frac{X - A}{D} \rceil D\)\(2\) つで十分です(\(\lceil x \rceil\) で実数 \(x\) 以上の最小の整数を表します)。

Python による実装例:

import sys

x, a, d, n = map(int, input().split())
if d == 0:
  print(abs(a - x))
  sys.exit()
m = a + (n - 1) * d # 末項
ans = min(abs(a - x), abs(m - x))
y = a + (x - a) // d * d
for i in range(-2, 3): # 周辺 ±2 程度を探索
  z = y + i * d
  if a <= z <= m or m <= z <= a: # 探索している数が範囲内にあるかどうか
    ans = min(ans, abs(z - x))
print(ans)

posted:
last update: