TCO 2016 Round 1B Medium. ReplacingDigit

問題概要

数列 A[N] が与えられる。好きな要素 A[i] を持ってきて、ある桁の数字を j に変えるという操作を各 j につき D[j] 回ずつできる。

この操作により A[n] の総和を最大化せよ。

解法

下から i 桁目を 9 増やすよりも下から i+1 桁目を 1 増やした方がいいので上の桁から貪欲に変えていけばいい。たとえば 5 桁目を 9 増やすと 9*10⁴ 増えるが、6 桁目を 1 増やすと 1*10⁵ 増える。

TCO 2016 Round 1B Medium. ReplacingDigit

実装方法に悩んだ。