Codeforces ECR #188 : E. Sum of Digits (and Again)

ちょっと手間取ったけどまあ普通に解けた。
https://codeforces.com/contest/2204/problem/E

問題

正整数xに対し、S(x)は以下のように構成される。

• xを文字列化する。その後、xが２桁以上なら、xの各桁の総和をD(x)としたとき、S(D)x))を末尾にくっ付ける

今数字で構成される文字列sが与えられる。
S(x)=sとなるxを１つ答えよ。

解法

|s|は10^5以下なので、D(s)の総和は10^6未満である。
あらかじめS(D(s))を列挙しておく。

よって、xはsから高々6桁を除いたものである。そこでD(x)の候補はD(s)-54～D(s)となることが推測される。
そこでD(x)を総当たりし、sからS(D(x))を構成する桁を除いたらxとなるかを確認しよう。

string V[1000000];
int nex[1000000];

int T;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=900000;i++) {
		x=i;
		V[i]=to_string(x);
		if(x>=10) {
			y=0;
			while(x) y+=x%10,x/=10;
			nex[i]=y;
			V[i]+=V[y];
		}
	}
	
	cin>>T;
	while(T--) {
		cin>>S;
		int C[11]={};
		FORR(c,S) {
			C[c-'0']++;
			C[10]+=c-'0';
		}
		for(i=max(C[10]-100,1);i<=C[10];i++) {
			int ts=C[10];
			int ok=1;
			FORR(c,V[i]) {
				C[c-'0']--;
				ts-=c-'0';
				if(C[c-'0']<0) ok=0;
			}
			if(ok&&ts==i) {
				for(j=9;j>=0;j--) {
					FOR(x,C[j]) cout<<j;
				}
				cout<<V[i]<<endl;
				break;
			}
			if(count(C,C+10,0)==10) {
				cout<<V[i]<<endl;
				break;
			}
			FORR(c,V[i]) {
				C[c-'0']++;
			}
		}
		
	}
	
	
}

まとめ

and Againってあるけど、Sum of Digitsが２問目だっけ？と思ったらそうじゃなくて、桁和を何度も取るってことか。