AtCoder ABC 175 C - Walking Takahashi (茶色, 300 点)

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

問題へのリンク

問題概要

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

• 座標 にいるとき、 に移動する
• 座標 にいるとき、 に移動する

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

制約

• 
• 

考えたこと

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

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

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

注意点として、 の方が よりも小さかったとしても、 に到達した時点で残り操作回数が奇数回でった場合は絶対に 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;
}