くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 175 C - Walking Takahashi

Python3で解く AtCoder Beginner Contest 175 C - Walking Takahashi

AtCoder 競プロ ABC-C 偶奇 座標移動

移動している様子を書きながら、考えればできそう。 {\displaystyle x}は正として考えればいいし、{\displaystyle k}が小さめな時は0へどんどん向かっていけばいいし、動ける回数が余ったら、余った回数の偶奇で場合分けする。

概要

問題
1. 座標上の{\displaystyle x}にいる。
1. {\displaystyle k}回動かなければいけない。
1. 1回で動ける距離は{\displaystyle d}で+にも-にも動ける。
1. {\displaystyle k}回動いた後に0からの距離が最小となるように動き方をした時の距離は？

解くときに考えた内容

  • まずは {\displaystyle x}は負もあり得るが、条件から考えて、負でも正として考えて問題がないのでそのようにする。
    • 負で考えると絶対値の計算で符号を逆にしなくてはいけないのでめんどくさい）
  • 0の方向へ向かえばいいが{\displaystyle x}がマイナスの値にならないように動ける最小回数は{\displaystyle x // d}である（{\displaystyle count}とする）。（距離 // 移動距離ってこと）
  • {\displaystyle count \geqq k}の時、つまり{\displaystyle k}が小さいので、ただ0へ向かい続けられるだけ動いた時の0からの距離が最小値。
  • {\displaystyle count \lt k}の時、動ける回数が余っているということ。
    • 動ける回数の余りが偶数なら、{\displaystyle (-d, d)}か{\displaystyle (-d, d)}の動きを続ければ{\displaystyle x - (count \times d)}に必ず戻って来ればよく、それが最小値。
    • 動ける回数の余りが奇数なら、{\displaystyle count}はマイナスの値にならないように動ける最小回数なのであり、0までの距離を、{\displaystyle a}とすると{\displaystyle |a-d| \leqq |a+d|}（等号成立は{\displaystyle a = 0}のとき、つまり{\displaystyle x - (count \times d) = 0}のとき）であるので、{\displaystyle +d}側に向かうよりも{\displaystyle -d}側に向かう{\displaystyle x - (count \times d) - d = x - (count+1) \times d }が最小値となる。

f:id:black_tank_top:20200817062306j:plain
移動パターンの概略図

コード

x, k, d = map(int, input().split())
# xを正の数として考えても問題ない
x = abs(x)
# xから0へ向かって、マイナス方向に超えない範囲で最小の値になるために必要な移動数
count = x // d
# kがcountより小さかったら、0へ向かって動けるだけ動く
if count >= k:
    ans = x - (k*d)
else:
    # 動ける回数が余って、かつ余りが偶数なら同じ位置に戻るように動き続ければいい。
    if (k - count) % 2 == 0:
        ans = x - (count*d)
    # 動ける回数が余って、かつ余りが奇数なら+dより-dへ進む
    # a = abs(x - (count*d))とすると |a - d| ≦ |a + d| だから
    else:
        ans = x - (count+1) * d
print(abs(ans))