ABC257 E - Addition and Multiplication 2

atcoder.jp

def resolve():

    N = int(input())

    C = list(map(int, input().split()))
    Min = min(C)

    diff = [
        [1, C[0]],
        [2, C[1]],
        [3, C[2]],
        [4, C[3]],
        [5, C[4]],
        [6, C[5]],
        [7, C[6]],
        [8, C[7]],
        [9, C[8]],
    ]

    for i in range(9):
        diff[i][1] -= Min

    diff = sorted(diff, key=lambda x: (x[1], -x[0]))

    keta = N // Min
    Cost = N - Min * keta

    ans = [diff[0][0]] * keta

    diff = sorted(diff, key=lambda x: (-x[0], x[1]))

    for i in range(keta):
        if Cost <= 0:
            break
        for d in diff:
            if d[1] <= Cost:
                ans[i] = d[0]
                Cost -= d[1]
                break

    if keta == 0:
        ans = [0]

    print(*ans, sep="")


resolve()

つっこみどころがあるにはあるが

• 最小コストの数字（かつ最も数字が大きいもの）を連打し、最大桁数の初期解とする
• 最小コストの数字に対して、各数字に変える時の差分コストを列挙する
• あとは差分コストが低い（かつ数字が大きい）順に貪欲に・・・と思いきや、これをやると、NG。数字が大きい（かつ差分コストが低い）順に貪欲にやる必要がある
  • そうでない場合、7777を9777にすべきところ、8877にしてしまうようなケースが発生する

と、ここまではもっと良質な解説があると思うので、この程度に。

---

地味にハマったポイントとして、巨大な数字を各桁ごとのリストで作成した場合に、どう出力しようとするか？でTLEしたので、メモしておく。

最後の結果出力部分を、いったん結果文字列を作ろうとしてこんな感じにすると、TLEする。
文字列の末尾への追加ならタダみたいなもんだと思い込んでいたが、そんなことはないので、↑のように、リストをそのまま出力しましょう。。。

    ansS = ""
    for a in ans:
        ansS += str(a)
 
    print(ansS)