C - Walking Takahashi Editorial by satashun


まず、\(X < 0\) の場合は全ての動きの方向を反転すれば \(X := -X\) と置き換えて解いた場合と対応するので、一般性を失わずに \(X \geq 0\) と仮定します。

最小化を考える前に、\(K\) 回の移動後にいる座標 \(Y\) としてどのようなものがありうるかを考えてみましょう。

まず、各移動で座標を \(D\) で割った余りは変わらないので、 \(Y = X \pmod D\) が必要です。また、\(K\) 回の移動でたどり着ける必要があるので、\(\frac{|Y-X|}{D} \leq K\) も満たす必要があります。

さらに、ちょうど \(K\) 回という条件から、\(\frac{|Y-X|}{D} = K \pmod 2\)

という条件も満たす必要があります。これは、座標を \(x = p * D + r (p, r \in \mathbb{Z}, 0 \leq r < D)\) と表したとき移動の度に \(p\) の偶奇が変化することから従います。

また、これらの条件を全て満たすとき、そのような \(Y\) で移動を終えることができます。これは例えば、\(X\) から \(Y\) へ移動を繰り返した後、余った回数 (これは偶数となる) 回数だけ \(-D\) した座標との間を行き来すれば良いです。

以上から、まず \(\lfloor \frac{X}{D} \rfloor\) 回だけ \(-D\) に移動し \(K := K - \lfloor \frac{X}{D} \rfloor\) としておきます。(この途中で \(K\) 回使い切ればその座標が答えです) その座標を \(A\) としたとき、\(K\) が偶数であれば \(A\) を、奇数であれば \(|A-D|\) を出力すれば良いです。(これは、行き来する部分を \(X=0\) 付近で行うことにすると、余りの性質から偶奇に応じた最適な座標に居続けられることを利用しています)

時間計算量は \(\mathrm{O}(1)\) です。

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);

    ll straight = min(K, X / D);
    K -= straight;
    X -= straight * D;

    if (K % 2 == 0) {
        cout << X << endl;
    } else {
        cout << D - X << endl;
    }

    return 0;
}

posted:
last update: