AGC009 A – Multiple Array

はじめに

競プロの精進のために学びがあった問題についてまとめています。
目標は AtCoder 水色！

今のレートは茶色です。

問題

AGC009 A – Multiple Arrayを解きました。

難易度は茶色。

考察

A[i]がB[i]の倍数になるようにボタンを押していく。

もともとA[i]がB[i]の倍数の場合は0、そうでない場合はB[i]から(A[i] % B[i])を引いた値を足していけばよい。

ここで、i番目のボタンを押すとA[0]からA[i]までのすべてが加算されてしまうため、先頭から貪欲的にカウントすると上手くいかない。

そのため、末尾から貪欲法で解くことで、O(N)で解ける。

コード

N = int(input())
A = []
B = []
ans = 0

for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

for i in range(1, N + 1):
    k = N - i
    A[k] += ans
    if A[k] % B[k] != 0:
        ans += B[k] - (A[k] % B[k])

print(ans)

まとめ

初AGCでした。

問題勘違いしてて苦戦。