貪欲が最適？ [Hokkaido University Programming Contest 2019 Day 1 D]

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