トップ > AtCoder > ABC231E - Minimal payments

ABC231E - Minimal payments

AtCoder AtCoder-Beginner Contest Python DP


【関連】

考え方

まず，$X$を「$\{A_{i}\}_{i}$を使った進数」で表す．つまり，「$X$を最小の硬貨でピッタリ払うときに必要な各硬貨の枚数」を決める．これは，大きい硬貨から使えるだけ使えば良い．これにより，$X$を
\begin{aligned}
X = \sum_{i=1}^{N} \mathrm{cnt\,}[i] \cdot A[i]
\end{aligned}
の形で表す．つまり，$i$ケタ目が$\mathrm{cnt\,}[i]$である．

この進数の一番下のケタから順に考える．各桁の支払いを決めると，そのケタをゼロにした状態で一つ上のケタに移れる．


$i$ケタ目の支払い方は，

  1. ピッタリ払う（$A[i]$の硬化を$\mathrm{cnt\,}[i]$枚払う）
  2. 一桁大きな硬化を払ってお釣りをもらう（$\mathrm{cnt\,}[i+1]$に1を加えて，お釣りを$A[i+1]/A[i] - \mathrm{cnt\,}[i]$枚もらう）．
のいずれかとなる．この両方を最小化しつつ再帰的に計算すれば良い．そこで，上の場合を$\mathrm{dp\,}[i][0]$，下の場合を$\mathrm{dp\,}[i][1]$と表す．つまり，$\mathrm{dp\,}[i][0]$を「$1\sim i$ケタ目まで決めたとき，$i$ケタ目でピッタリ払うときの最小の硬貨枚数」，$\mathrm{dp\,}[i][1]$を「$1\sim i$ケタ目まで決めたとき，$i+1$ケタ目の硬貨を払って，$i$ケタ目ではおつりをもらう場合の最小の硬貨枚数」とする．


$i$ケタまで決めたとき，$i + 1$ケタ目の最小硬貨枚数は

\begin{aligned}
\mathrm{dp\,}[i+1][0]
& = \min(\mathrm{dp\,}[i+1][0], \\
&\qquad\qquad
\mathrm{dp\,}[i][0] + \mathrm{cnt\,}[i+1], \\
&\qquad\qquad
\mathrm{dp\,}[i][1] + \mathrm{cnt\,}[i+1] + 1) \\
\mathrm{dp\,}[i+1][1]
& = \min(\mathrm{dp\,}[i+1][1], \\
&\qquad\qquad
\mathrm{dp\,}[i][0] + A[i+2]/A[i+1] - \mathrm{cnt\,}[i+1] \\
&\qquad\qquad
\mathrm{dp\,}[i][1] + A[i+2]/A[i+1] - \mathrm{cnt\,}[i+1] - 1)
\end{aligned}
となる．実装のときは，$A, \mathrm{cnt\,}$が0-indexedのため，添字が-1されることに注意．


よく考えてみれば，次のような事情があるが，最小値をとるときに，自然に落とされる．
  • $\mathrm{cnt\,}[i] = 0$であれば，「一桁大きな硬化を払ってお釣りをもらう」という選択肢はありえない（必ず損をする）．
  • $\mathrm{cnt\,}[i+1] + 1 \geq A[i+2]/A[i+1]$の場合は，$A[i+1]$の硬貨でピッタリ払うという選択肢はありえない（$A[i+2]$で支払ったほうが得）．

【参考】

回答例

N, X = map(int, input().split())
A = list(map(int, input().split()))

cnt = [0] * N
for i in range(N - 1, -1, -1):
  cnt[i] = X // A[i]
  X %= A[i]
  
dp = [[1 << 60] * 2 for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
  dp[i + 1][0] = min(dp[i + 1][0],
                     dp[i][0] + cnt[i],
                     dp[i][1] + cnt[i] + 1)
  if i + 1 < N:
    dp[i + 1][1] = min(dp[i + 1][1],
                       dp[i][0] + A[i + 1] // A[i] - cnt[i],
                       dp[i][1] + A[i + 1] // A[i] - cnt[i] - 1)
  
print(min(dp[-1]))