[AtCoder] ABC 175 C – Walking Takahashi

2020年8月16日2020年12月14日

問題

方針

下記の問題と似ています。

まず初めに、\( K \) の値を無視して考えます。また、\( X = |X| \) としても一般性を失わないので、\( X = |X| \) とします。整数 \( t \) を

\[ t = \left \lfloor \dfrac{X}{D} \right \rfloor\]

とすると、最適な座標は

\[ \min(X – tD, (t +1)D – X) \]

となります。次に \( K \) の値を考慮して考えます。

\( K \leq t \) のとき

このとき、\( X – KD \) が最小値となります。

\( t + 1 \leq K \) のとき

\( X – tD \leq (t + 1)D – X \) のとき

このとき、\( (K – t) \bmod 2 = 0 \) ならば、\( X – tD \) が最小値であり、そうでなければ、\( (t + 1)D – X \) が最小値となります。

\( X – tD > (t + 1)D – X \) のとき

このとき、\( (K – t – 1) \bmod 2 = 0 \) ならば、\( (t + 1)D – X \) が最小値であり、そうでなければ、\( X – tD \) が最小値となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);
    if (X / D >= K) {
        cout << X - K * D << "\n";
        return 0;
    }
    ll t = X / D;
    ll A = X - t * D;
    ll B = (t + 1) * D - X;
    if (A <= B) {
        if ((K - t) % 2 == 0) {
            cout << A << "\n";
        } else {
            cout << B << "\n";
        }
    } else {
        if ((K - t - 1) % 2 == 0) {
            cout << B << "\n";
        } else {
            cout << A << "\n";
        }
    }
    return 0;
}