もれなく正確に解くための考え方とかが問われる感じ。
問題概要 (AGC 008 A)
整数 が与えられる。
に以下のいずれかの操作を最小回数行って
に一致させよ:
を 1 増やす
を
にする
解法
最適解は
- 最初に反転する (かしないか)
- 「1 増やす」を繰り返す
- 最後に反転する (かしないか)
のいずれかの形のみを考えれば良いことが比較的簡単に示せる。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; }