ABC175C - Walking Takahashiを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 175 C - Walking Takahashiを解いてみました。

まず問題文をみます。

座標$X$にいる高橋君をできるだけ原点に近づけるように移動させると、どこまで近づけることができるかという問題です。

移動には距離($D$)と回数($K$)の制限があります。

次に制約をみます。

$1 \le K \le 10^{15}$より、愚直に移動を繰り返すとTLEになります。

まず、問題を単純にするためにXが負の値のときは$-1$を掛けて正の値にします。

次に高橋君を原点を超えない範囲で負の方向に移動し、その座標を$G$とします。このとき、$G$を引き算で求めようとすると$O(K)$で間に合わないので割り算を使います。

移動回数: $X \div D$

$G$: $X - (D \times 移動回数)$

この時点で移動回数を使い切ったとき、$G$が答えになります。

まだ移動回数が残っているとき、$G$とさらに1回だけ負の方向に移動した座標を往復することになります。すなわち、残りの移動回数が偶数であれば$G$が答えになり、奇数であれば$G$引く$D$の絶対値が答えになります。

(let* ((x (read))
       (k (read))
       (d (read)))
  ;; 単純化するためにxを正の値にそろえる
  (when (< x 0)
    (setf x (* x -1)))

  ;; できるだけ原点に近づく
  (let* ((move-count (min k (floor x d)))
         (g          (- x (* d move-count))))
    (cond ((zerop (- k move-count))
           ;; これ以上移動できないとき
           (format t "~A~%" g))
          ((oddp (- k move-count))
           ;; 残りの移動回数が奇数のとき
           (format t "~A~%" (abs (- g d))))
          (t
           ;; 残りの移動回数が偶数のとき
           (format t "~A~%" g)))))