けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 008 A - Simple Calculator (300 点)

もれなく正確に解くための考え方とかが問われる感じ。

問題へのリンク

問題概要 (AGC 008 A)

整数  x, y が与えられる。 x に以下のいずれかの操作を最小回数行って  y に一致させよ:

  •  x を 1 増やす
  •  x -x にする

解法

最適解は

  1. 最初に反転する (かしないか)
  2. 「1 増やす」を繰り返す
  3. 最後に反転する (かしないか)

のいずれかの形のみを考えれば良いことが比較的簡単に示せる。3 番目のやつは反対に  y の方を反転すればいい。よって、

    if (x <= y) res = min(res, y-x);
    if (-x <= y) res = min(res, y+x+1);
    if (x <= -y) res = min(res, -y-x+1);
    if (-x <= -y) res = min(res, -y+x+2);

という感じで OK

#include <iostream>
using namespace std;

long long x, y;
int main() {
    cin >> x >> y;
    long long res = 1LL<<60;
    if (x <= y) res = min(res, y-x);
    if (-x <= y) res = min(res, y+x+1);
    if (x <= -y) res = min(res, -y-x+1);
    if (-x <= -y) res = min(res, -y+x+2);
    cout << res << endl;
}