AtCoder ARC #153 : D - Sum of Sum of Digits

これ系似た解法を見た気がするけど、本番詰め切れず。
https://atcoder.jp/contests/arc153/tasks/arc153_d

問題

非負整数nに対し、f(n)を、nの各桁の数字の和とする。
整数列Aが与えられる。
任意の非負整数xを選べるとき、sum(A[i]+x)の最小値を求めよ。

解法

dp(d,n) := xの下からd桁目までを決めたとき、繰り上がりがn個あるときの桁和の最小値
とする。
dp(d,n)を下の桁から決めて以降。それぞれのケースで、d+1桁目を0～9を取った場合を総当たりするとよい。

int N;
ll A[202020];
ll from[202020];
ll to[202020];
ll S[202020];
ll p10[13];

ll dp[13][202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,10) p10[i+1]=p10[i]*10;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	FOR(j,11) FOR(i,N+1) dp[j][i]=1LL<<60;
	dp[0][0]=0;
	FOR(i,10) {
		vector<pair<int,int>> pre;
		int C[11]={};
		FOR(j,N) {
			C[A[j]/p10[i]%10]++;
			pre.push_back({A[j]%p10[i],j});
		}
		sort(ALL(pre));
		reverse(ALL(pre));
		FOR(j,N+1) {
			FOR(x,10) {
				ll cv=dp[i][j];
				int carry=0;
				FOR(y,11) {
					cv+=C[y]*((y+x)%10);
					carry+=C[y]*((y+x)/10);
				}
				chmin(dp[i+1][carry],cv);
			}
			
			if(j<N) {
				x=pre[j].second;
				y=A[x]/p10[i]%10;
				C[y]--;
				C[y+1]++;
			}
		}
	}
	
	
	
	cout<<dp[10][0]<<endl;
}

まとめ

似たようなの見たのはyukicoderだったかな…？