Codeforces #289 Div2 C. Sums of Digits

CF#289に参加。ただしARC#031を解いた後遅れて参加したので全完間に合わず。
http://codeforces.com/contest/509/problem/C

問題

N個の単調増加な数列A[i]がある。
A[i]自体は不明だが、ヒントとして各項において各桁の合計値B[i]が与えられる。

各桁の合計値がB[i]であるような最小の単調増加数列A[i]を作成せよ。

解法

A[0]=B[0]で良い。
あとはA[i-1]がわかっている状態で、桁の合計がB[i]となるA[i-1]より大きな最小の値を求めればよい。

上の桁から再帰で求めていく。
まず最上位桁xがA[i-1]と同じ値にした場合を考える。
後は残りの桁でA[i-1]以上でかつ桁の合計がB[i]-xとなるものを再帰的に求めていけば良い。
そのようなものが存在するなら、最上位桁をx、解の桁を再帰的に求めた値を連結すればよい。

最上位桁がxで条件を満たせるものがない場合、最上位桁を(x+1)～9にし、残りの桁を下から9を詰めていって合計B[i]に出来るものを探す。

それでもない場合は桁を増やすことを考える。
桁を1つずつ増やしながら最上位桁を1～9にしたとき、下の桁に9を詰めていって合計B[i]に出来るか判定すればよい。
B[i]は300以下なので、桁増加はせいぜい30桁である。

int N;
int B[1010];

string dodo(string c,int d,bool istop=false) {
	int l=c.size();
	int x,i;
	
	if(d<0) return "*";
	if(l==0) return "*";
	
	string s = dodo(c.substr(1),d-(c[0]-'0'));
	if(s!="*") return c.substr(0,1)+s;
	for(x=c[0]-'0'+1;x<=9;x++) {
		if(d-x<0) break;
		if((l-1)*9<d-x) continue;
		s=c;
		s[0]='0'+x;
		d-=x;
		for(i=l-1;i>0;i--) {
			s[i]='0'+min(9,d);
			d-=min(9,d);
		}
		return s;
	}
	if(!istop) return "*";
	while(1) {
		for(x=1;x<=9;x++) {
			if(x<=d && l*9+x>=d) {
				s="0";
				s+=c;
				s[0]+=x;
				d-=x;
				for(i=l;i>0;i--) {
					s[i]='0'+min(9,d);
					d-=min(9,d);
				}
				return s;
			}
		}
		c=c+"0";
		l=c.size();
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	string c="0";
	FOR(i,N) {
		cin>>B[i];
		c=dodo(c,B[i],true);
		cout<<c<<endl;
	}
}

まとめ

Div2Cなのに意外と手こずった。
Div2Dでもいいんじゃ…と思ったけど結構みんな解いてるなぁ。