もれなく正確に解くための考え方とかが問われる感じ。
問題概要
整数 が与えられる。 に以下のいずれかの操作を最小回数行って に一致させよ:
- を 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; }