😽

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

2022/06/28に公開約900字

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 が最小値となるような ik とすると、とりあえず桁数を最大にするならば、kq 個並べた数字をつくることは可能となる。余り r を上手く処理すれば、さらに大きな数字に変化させることが出来る可能性がある。

貪欲に i=9 から試していく。余り rC[i-1]-k (0-indexedなので-1)を支払えるなら、数字を大きなものに変更することができる。ik と同じになってしまった場合には、変更の意味がないので、残りの桁数分 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)

Discussion

ログインするとコメントできます