[AtCoder] ABC 175 C – Walking Takahashi

問題

方針

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

まず初めに、\( 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 \) が最小値となります。

コード