けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 175 C - Walking Takahashi (300 点)

ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう!

問題へのリンク

問題概要

現在、座標  X にいる。以下のいずれかの操作をちょうど  K 回行う。

  • 座標  x にいるとき、 x + D に移動する
  • 座標  x にいるとき、 x - D に移動する

 K 回の移動後の座標の絶対値として考えられる最小値を求めよ。

制約

  •  -10^{15} \le X \le 10^{15}
  •  1 \le K, D \le 10^{15}

考えたこと

とりあえず  X は負の値をとりうるけど、考察対象が「座標の絶対値」なので、 X = abs( X) としてかまわない!!

そして、以下の動きを繰り返すことになる (ちゃんとした証明はeditorialに)。

  •  X D で割ったあまりを  r として、地点  r に到達するまではひたすら  r を目指す
  •  r に到達後は、 r r - D (絶対値は  D-r) とをひたすら往復する

注意点として、 r の方が  D-r よりも小さかったとしても、 r に到達した時点で残り操作回数が奇数回でった場合は絶対に r の方でゴールできない

このあたりのことを慎重に場合分けしながら実装していく。

#include <bits/stdc++.h>
using namespace std;

long long solve(long long X, long long K, long long D) {
    X = abs(X);
    long long q = X/D, r = X%D; // 地点 r に到達するまで
    if (q >= K) return X - D*K;
    long long rem = K - q; // 残り回数
    if (rem % 2 == 0) return r;
    else return D-r;
}
int main() {
    long long X, K, D;
    cin >> X >> K >> D;
    cout << solve(X, K, D) << endl;
}