https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/D
解説
https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3746197
問題を見ると、経験から特殊な性質・規則性を用いる問題だと見える。
こういう時は、実験コードを書くべきなので、実験しよう。
結果はこうなる
ll A, B; //--------------------------------------------------------------------------------------------------- int greedy(int a, int b, int x) { int cnt = 0; cnt += x / b; x %= b; cnt += x / a; x %= a; cnt += x; return cnt; } int opt(int a, int b, int x) { vector<int> dp(x + 1, inf); dp[0] = 0; rep(i, 0, x) { chmin(dp[i + 1], dp[i] + 1); if(i + a <= x) chmin(dp[i + a], dp[i] + 1); if (i + b <= x) chmin(dp[i + b], dp[i] + 1); } return dp[x]; } int naive() { rep(x, 1, A * B * 2) { int g = greedy(A, B, x); int o = opt(A, B, x); if (o < g) return x; } return -1; } void labo() { int ma = 30; rep(a, 1, ma) rep(b, a + 1, ma) { A = a, B = b; printf("%d\t%d\t->\t%d\n", a, b, naive()); } } //--------------------------------------------------------------------------------------------------- void _main() { labo(); }
どう見ても規則性がある。
ここから規則をエスパーすると、
- 答えは、Aの整数倍になっている
- 答えがAのx倍である場合は、Bが[A * (x - 1) + 1, A * x - x]にあるときである
- xはB/Aの切り上げになっている
ということが読み取れるので、これを実装して、場合分けして答えればAC。
ll A, B; //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >> B; ll x = B / A; if (B % A != 0) x++; ll L = A * (x - 1) + 1; ll R = A * x - x; if (L <= R and L <= B and B <= R) cout << A * x << endl; else cout << -1 << endl; }