ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう!
問題概要
現在、座標 にいる。以下のいずれかの操作をちょうど
回行う。
- 座標
にいるとき、
に移動する
- 座標
にいるとき、
に移動する
回の移動後の座標の絶対値として考えられる最小値を求めよ。
制約
考えたこと
とりあえず は負の値をとりうるけど、考察対象が「座標の絶対値」なので、
= 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; }