[Boot camp for Beginners] C - Replacing Integer [Rust]

概要

AtCoder Problems: Boot camp for Beginners をRustで解いてみる

• 今回の問題：C - Replacing Integer
• 書いたコード： AtCoder_Problems_Boot_Camp_for_Beginners/easy100/c-replacing-integer at main · homura10059/AtCoder_Problems_Boot_Camp_for_Beginners

学んだことmemo

• 普通に再帰かループで計算すれば良さそうだが...?
  • 再帰だとnが大きい時にoverflowする
  • ループだと時間がかかりすぎて終わらない
• 考え方を変える必要がある
• N から x と x - K の絶対値で置き換える
  • 最初はKづつ減っていく
    • NからKの倍数を引けるだけ引いたら？ → N%K
  • N%K まできたら次は？
    • N%K < K なので K - N%K
    • このどっちが小さいか
• これを初手で思いつくの無理じゃね...?
  • N <= 10^18 なのでループとかじゃ解けないと気づくべきなのか...
  • これは嗅覚を鍛える必要がある