Codeforces ECR #090 : E. Sum of Digits

後半が難しめだった回。
http://codeforces.com/contest/1373/problem/E

問題

非負整数xに対し、f(x)は各桁の数字の和を示す。
整数N,Kが与えられる。
f(x)+f(x+1)+...+f(x+k)=Nとなる最小のxを求めよ。

解法

g(n) := f(x)=nとなる最小のxで、インクリメントしても繰り上がりが生じない(1の位が9でない)もの
h(n) := f(x)=nとなる最小のx
を最初に求めておこう。

xの1の位を総当たりする。
kは9以下なので、(x+i)の10の位以上に現れる数は2通りしかない。
そこでg(n)・h(n)を用いて、上の桁を定めていく。

int T,N,K;


string cand[151],cand2[151];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,151) {
		j=i;
		while(j) {
			x=min(j,9);
			if(cand[i].empty()) x=min(x,8);
			cand[i]+='0'+x;
			j-=x;
		}
		reverse(ALL(cand[i]));
		
		j=i;
		while(j) {
			x=min(j,9);
			cand2[i]+='0'+x;
			j-=x;
		}
		reverse(ALL(cand2[i]));
		
	}
	
	
	cin>>T;
	while(T--) {
		//N=T/10;
		//K=T%10;
		cin>>N>>K;
		K++;
		string S(152,'9');
		int a,b,c;
		FOR(a,10) {
			int t=0;
			int up=0;
			FOR(i,K) {
				t+=(a+i)%10;
				if(a+i>=10) up++;
			}
			FOR(i,151) {
				int num=t+(i+1)*up+i*(K-up);
				
				if(num>N) continue;
				if((N-num)%(9*(K-up))) continue;
				int n9=(N-num)/9/(K-up);
				
				string T;
				if(up==0) T=cand2[i];
				else T=cand[i];
				FOR(x,n9) T+='9';
				T+=(char)('0'+a);
				if(T.size()<S.size() || (T.size()==S.size() && T<S)) S=T;
			}
		}
		if(S.size()==152) S="-1";
		//cout<<N<<" "<<(K-1)<<" ";
		cout<<S<<endl;
		
		
	}
}

まとめ

本番も何とか解けてるな。