ABC175 C問題

C - Walking Takahashi

要約

K <= 10^15より，普通にループを回してシミュレーションすると当然アウト

そこで，for文で探索するのではなく，ある程度，if分岐で求める問題と分かる．

まず，一次元の話なので，最初のXが負の位置にいても絶対値を取って正の値を考えても問題ない．

次に，目標としてできるだけ0に近づいて行けば良いことが分かるので，

X - K*D > 0:

を満たすか否かで分岐すれば良い．

最大量移動しても0までつかないときは，その位置が最小値である．

逆に0を超すときが問題である．

次に0を超す時の考察．

汚くて申し訳ないが全てはこの写真に書いてあるとおりである．

ギリギリ正の位置に来たとき，残りの移動回数で求める答えがきまる．

偶数回残っていたら元の位置に戻る．

奇数回残っていたら0を超す場所の絶対値が最小値である．

注意として，最大まで0に近づいてきて0に来るときは少し例外処理になるので注意．これで一発ACを食らった．

import math
X, K, D = map(int, input().split())

X = abs(X)
if X - K*D > 0:
 print(X - K*D)
else:
 #---ガウス関数で0を超すor越さないギリギリを見極める----
 if X % D != 0:
   step_m = math.ceil(X/D) #0を超す移動回数(-の位置に来る)
   step_p = math.floor(X/D) #ぎりぎり0を超えない移動回数(+の位置にとｄフォ丸)
 else:
   step_p = math.floor(X/D) #ぴったり0
   step_m = step_p + 1
 #-----------------------------------
 x_m = X - D * step_m #-ぎりぎり
 x_p = X - D * step_p #+ぎりぎり
 rem = K - step_m
 #print(step_m, step_p)
 if rem % 2 == 0:
   print(abs(x_m))
 else:
   print(abs(x_p))