ABC415:D - Get Many Stickersの解法メモ

問題の本質

• 交換は「$n >= A$ のとき $n ← n - A + B$」
• 制約で $B < A$ なので、交換すると $n$ は必ず減る
• 目的は「交換回数（ステッカー枚数）最大化」＝できるだけ長く交換を続ける

差 d = A - Bに注目する

1回の交換で n は

• n ← n - A + B
• n ← n - (A - B)
• n ← n - d

つまり 交換の本質は「n を d だけ減らす操作」。

だから、

• d が小さいほど 1回で減る量が小さく、回数を稼ぎやすい
• よって $d = A-B$ が小さい交換から使うのが自然な貪欲になる

ループを while で回さない

同じ交換を連続で使うとき、条件は「常に $n >= A$」

交換を k 回した後：

• $n = n - k*d$

最後まで交換できる条件：

• $n - k*d >= A$
• $k*d <= n - A$
• $k_{max} = floor((n - A) / d)$

でも「実行回数」は n>=A の状態から始まるので +1して

• k = (n - A) / d + 1（整数除算）

これで

• ans += k
• n -= k*d
  と一気に進められる（1回ずつ回す必要なし）

コードへの落とし込み手順

1. 入力は全部 long long（最大が (10^{18})）

2. 各交換で d[i] = a[i] - b[i] を作る

3. idx = 0..m-1 を作り、d 昇順にソート

   • sort(idx.begin(), idx.end(), [&](ll x,ll y){ return d[x] < d[y]; });

4. for (id : idx) を回す

   • if (n < a[id]) continue;（そもそも交換できない）
   • k = (n - a[id]) / d[id] + 1;
   • ans += k;
   • n -= k * d[id];

5. cout << ans << "\n";

##　解答

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = (0); i < (n); i++)

int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(m), b(m), d(m), idx(m);
    rep(i, m) {
        cin >> a[i] >> b[i];
        d[i] = a[i] - b[i];
        idx[i] = i;
    }
    sort(idx.begin(), idx.end(), [&](ll x, ll y) { return d[x] < d[y]; });
    ll ans = 0;
    for (int id : idx) {
        if (n < a[id]) continue;
        ll k = 1 + (n - a[id]) / d[id];
        ans += k;
        n -= k * d[id];
    }
    cout << ans;
    return 0;
}