Codeforces #350 Div2. F. Restore a Number

こういうのコーナーケースを列挙できないとテストも出来ないし苦手。
http://codeforces.com/contest/670/problem/F

問題

巨大な整数Nの後ろに、桁数をくっつけた文字列がある。
入力として、この文字列の並び順をシャッフルしたものSと、元のNに含まれる部分文字列Tが与えられる。
S,Tから考えられるNのうち最小のものを求めよ。

解法

くっつけた桁数は総当たりなりなんなりで求めてしまおう。
以下、S' = Sから桁数に相当する数字とTに含まれる数字を除いたもの、とする。
S'の並び順には意味がないので、(桁数を取り除いた上で)0～9の登場回数だけを数えておく。

例外ケースとしてN=0の場合はleading zeroがありややこしいので先に取り除いておく。
以下、下記のようになんとか頑張って列挙する。

• Tにleading zeroがある場合
  • S'中非0で最小の数字を1つ頭に置き、後ろにS'中の0をすべて並べ、Tを並べたうえで、残りS'中の1～9を小さい順に列挙すればよい。
• Tにleading zeroがない場合
  • S'にleading zeroがない場合
    • S'中でT[0]より小さいものはまず全部前につなげてしまおう。S'中にT[0]と同じ数字がある場合、S'中の数字とTどちらを先に並べるかはその数字を並べたものとTのうち辞書順で小さいものを前にすればよい。両者を並べたのち、S'中のT[0]以降の要素を小さい順に並べる。
  • S'にleading zeroがある場合
    • 先頭にleading zeroが無いようにS'の要素を|T|文字分並べた最小の文字をUとする(|T|個なければ足りなくてよい)。U+T＜T+UならUを先並べたいので、S'の最小非0要素を1文字並べて0を並べきる。そうでない場合Tを並べて0を並べきる。これでS'中の0は並べきるので、残りは上記leading zeroがないケースに従う。

string S,T;
int L;
int num[10];

void out(int x) { while(num[x]-->0) _P("%d",x);}
void outT() { _P("%s",T.c_str()); T="";}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	FORR(r,S) num[r-'0']++;
	FORR(r,T) num[r-'0']--;
	x=S.size();
	y=1;
	for(i=1;i<=7;i++) {
		if(x-i>=y && x-i<y*10) {
			L=x-i;
			break;
		}
		y*=10;
	}
	x=L;
	while(x) num[x%10]--, x/=10;
	
	if(T[0]=='0') {
		for(i=1;i<=9;i++) if(num[i]) {
			num[i]--;
			_P("%d",i);
			break;
		}
		out(0);
		outT();
		for(i=1;i<=9;i++) out(i);
	}
	else {
		if(num[0]) {
			stringstream ss;
			FOR(i,T.size()) {
				FOR(x,10) if((i!=0 || x!=0) && num[x]) {
					num[x]--;
					ss << x;
					break;
				}
			}
			string U;
			U=ss.str();
			FORR(c,U) num[c-'0']++;
			if(T+U<U+T) {
				outT();
			}
			else {
				for(i=1;i<=9;i++) if(num[i] && i<=T[0]-'0') {
					num[i]--;
					_P("%d",i);
					break;
				}
				if(i==10) outT();
			}
			out(0);
		}
		for(i=1;i<=9;i++) if(num[i]) {
			if(T.size() && i==T[0]-'0') {
				for(j=1;j<T.size();j++) {
					if(T[j]<T[0]) break;
					if(T[j]>T[0]) j=T.size();
				}
				if(j<T.size()) outT();
				out(i);
				outT();
			}
			else {
				out(i);
			}
		}
		_P("%s",T.c_str());
	}
	_P("\n");
	
}

まとめ

この問題桁数くっつける設定いらないでしょ…。