【競プロ精進ログ】ABC161-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC161-C「Replacing Integer」です。

ポイント

実装量は少ないものの，少しだけ頭を悩ませる問題でした。差で置き換えるという操作は，実は割り算で表すことができます。

まず簡単なケースとして，3番目のサンプルにあるように$N \geq K$かつ$N$が$K$で割り切れる場合を考えてみましょう。この場合は，常に差を取っていけば最終的に0になります。これは，$N$を$K$で割ったあまりに相当します。

すると，$K$で$N$を割り切れない場合も，$N$を$K$で割った余り$x$が最小値の最終候補になると考えられます。ただし，あまりの数$x$は$K$より小さいことが保証されているものの，最大で$K-1$の値を取ります。

その場合は，青木君が行える操作$|K-x|$という操作も行えるため，最小値の最終候補としては$|K-x|$も考えられます。実際には，あまりの大きさが$K$の半分を超えてしまった場合には，$|K-x|$という操作を行なった方が最終結果は小さくなります。

一方で，$N \leq K$の場合は，もうすでに割り算の余りの結果が出ているとみなせます。すると，こちらの最終候補は$N$そのものが$x$とみなせます。少し見方を変えると，これは$N \leq K$の条件下で$N$を$K$で割ったあまりそのものです。こうすることで，先ほどの$N \leq K$の場合と全く同様の状況と捉えることができます。ですので，先ほどと同様に，最小値の最終候補としては$|K-x|$も考えられます。以上をまとめます。

最小値の候補は…
・$N$を$K$で割ったあまり（x = N % K）
・$K$から$N$を$K$で割ったあまりを引いたものの絶対値（y = |K - x|）

これらの小さい方を最小値として出力すればOKです。ちなみに，常に$K > x$が保証されていますので，y = K - xの絶対値は必要ありません。

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int main(){
  ll N, K;
  cin >> N >> K;
  // 割り算の結果
  ll x = N % K;
  // あまりがKの半分よりも大きかった場合に備えて
  ll y = K - x;
  // 小さい方を出力する
  cout << min(x, y) << endl;
}