[ABC257E] Addition and Multiplication 2 を Pythonで解く

https://atcoder.jp/contests/abc257/tasks/abc257_e

考え方

DPの問題かと思ったら、貪欲法でした。
考え方のポイントとしては、
(1) 操作を行うと$x$の桁が増えるので、操作回数が多い方が$x$は大きくなる。
(2) 選んだ数字が一の位に入るので、できるだけ大きな数字を選んだ方が良い。

桁が大きい方が数字は大きくなるので、(1)が(2)よりも優先される。$N$を[$C$の最小値]で割ると、その商 $q$ が桁数になる。桁数を決めた後で、余り $r$ の数を上手くやり繰りすると、さらに大きな数字に変化させることができる。

実装メモ

from functools import reduce
N = int(input())
C = list(map(int,input().split()))
rC = list(reversed(C))

MinC = reduce(min,C)
k = 9 - rC.index(MinC)
q = N // MinC
r = N % MinC

$C$ が最小値となるような $i$ を $k$ とすると、とりあえず桁数を最大にするならば、$k$ を $q$ 個並べた数字をつくることは可能となる。余り $r$ を上手く処理すれば、さらに大きな数字に変化させることが出来る可能性がある。

貪欲に $i=9$ から試していく。余り $r$ で $C$[$i-1$]$-k$ (0-indexedなので$-1$)を支払えるなら、数字を大きなものに変更することができる。$i$ が $k$ と同じになってしまった場合には、変更の意味がないので、残りの桁数分 $q$ だけ $k$ をつけて終了とする。

ans = ""
i = 9
while r > 0 and i > k:
    if C[i-1] - MinC <= r:
        r -= C[i-1] - MinC
        ans = ans + str(i)
        q -= 1
    else:
        i -= 1

ans = ans + str(k)*q

print(ans)