AtCoder Beginner Contest 175 [ C - Walking Takahashi ]をPythonで解く（300点、🟫茶diff）

問題

atcoder.jp

解法

移動回数Kの制約が 1 ≤ K ≤ 10¹⁵ なので、シミュレーションするとO(10¹⁵)。
O(10⁸)を超えるとTLEなので、計算で出す問題だということがわかる。

処理としては * XがDより小さくなるまで移動。移動回数Kを使い切ってるなら、ここで終わり * Xが0を超える方向にD移動、D戻るの繰り返し。Kの偶奇で結果がどちらになるか決まる。

の２つからなる

XがDより小さくなるまで移動する移動回数aを計算式を考える

D >= X - a x D
D + a x D >= X
a x D >= X - D
a >= X/D - 1

aを小数点以下切り上げた数が、XがDより小さくなるまで移動する移動回数。
Kがaを超えていないなら、X - K*Dか答え。

超えているならK = K - a
あとは、Kの偶奇を見て、答えが決まる。

実装