ABC415のD問題Get Many Stickers

2025-07-25

日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415）に参加しましたが、当日回答できなかったD問題 Get Many Stickersに改めて挑戦しました。

Get Many Stickers

コーラの空き瓶をN本もっている。これを与えられたルールに従って新しいコーラを引き換える。この時一番うまく交換した時に得られる景品の「棒」の本数を答える問題。

考え方

ルールから$B \lt A$なので、新しいコーラと交換する毎に手持ちのコーラの本数が減少します。そこで、最も手持ちの本数を減らさない交換ルールが、一番うまく交換するためのルールとなります。

そこで、交換に必要な空き瓶の本数Aと新しくもらえる本数Bの差$\Delta = A - B$に注目して、ルールを整理します。この時、同じ$\Delta$で必要な空き瓶の本数が異なるルールが存在する可能性があります。そこで、$\Delta$が同じ時には必要な空き瓶の本数が少ないほうが最後までルールを適応できるので、必要な空き瓶の本数が最小のルールのみを残して他を削除して調べるルール数を減らしました。

後は$\Delta$が小さいもの（お徳なルール）から順番に空き瓶と新しいコーラの交換を交換できなくなるまで繰り返します。

しかし、実際に交換を試していると制限時間を超えてしまいます。これをどうした解決できるか思いつくことができませんでした。そこで、解説に助けてもらいました。

まず、お徳なルールで交換します。そうすると、必要な空き瓶の本数よりも手持ちの本数が多い場合は、次の回も同じお徳なルールを適応できるということです。すなわち最もお徳なルールは、必要な空き瓶のを満たさなくなるまでその交換ルールを繰り返し適用できるのです。

その結果、実際に交換を試さなくても交換できる回数が次の計算で求められます。

$$ 交換可能な回数 = \left\lfloor \frac{手持ちの空き瓶数 - 交換に必要な本数}{\Delta} \right\rfloor + 1 $$

$$ 残りの空き瓶数 = 手持ちの空き瓶数 - 交換可能な回数 \times \Delta $$

そして、この最もお徳な交換ルールを適用できなくなったら、次にお徳なルール、それもダメならその次にお徳なルールと順次交換できなくなるまでルールを適用して交換可能回数を積算します。

N, M = map(int, input().split())

# key: delta, value: consumed bottles
rules = {}
for _ in range(M):
    A, B = map(int, input().split())
    delta = A - B
    if delta in rules:
        if rules[delta] > A:
            # update new consumed
            rules[delta] = A
    else:
        rules[delta] = A

rules = list(rules.items())
# sort by お徳順 (減少が少ない)
rules.sort(key=lambda x: x[0])

current_bottles = N
step = 0
for rule in rules:
    delta = rule[0]
    consume = rule[1]
    if current_bottles >= consume:
        # if available, repeat it
        available = (current_bottles - consume) // delta + 1
        step += available
        current_bottles = current_bottles - delta * available
print(step)

参考サイト

D - Get Many Stickers 解説