AtCoder AGC 008 A - Simple Calculator (300 点)

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

問題へのリンク

問題概要 (AGC 008 A)

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

• を 1 増やす
• を にする

解法

最適解は

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

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

    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;
}