TopCoder SRM 758 Div1 Easy Div2 Hard SelfDescFind

今回はMediumの早解きに成功して良い順位。
https://community.topcoder.com/stat?c=problem_statement&pm=15458

問題

以下のような整数を自己記述的と定義する。

• 偶数の桁長で、先頭の桁からa[0],b[0],a[1],b[1]...と交互に2つの数列に分けていく。
• 元の整数中、数字b[i]がa[i]回登場する。

数字の集合Sが与えられる。
各桁に登場する数字がSに一致するような自己記述的整数のうち最小値を答えよ。

解法

Sの要素がbに1回ずつ登場しなければならないのは明らか。
そうすると解の桁数は2*|S|となる。
よって、bはS昇順に固定し、aをどう割り当てるかを考えよう。
割り当てが決まったら、a[i],b[i]を小さい順に並べなおせば解の候補となる。

あとはSの要素を|S|個並べて和が2*|S|になるようにするだけなので、枝刈りしつつ全探索すればよい。

class SelfDescFind {
	public:
	vector<int> D;
	int N;
	string S;
	void dfs(int cur,vector<int>& num,int left) {
		if(left<N-cur) return;
		if(cur==N) {
			if(left) return;
			int cnt[10]={};
			int i;
			FOR(i,N) {
				cnt[num[i]]++;
				cnt[D[i]]++;
			}
			set<string> V;
			FOR(i,N) {
				if(cnt[D[i]]!=num[i]) return;
				V.insert(to_string(num[i]*10+D[i]));
			}
			string R;
			FORR(v,V) R+=v;
			S=min(S,R);
			
		}
		else {
			int i;
			FOR(i,N) if(D[i]!=0) {
				num.push_back(D[i]);
				dfs(cur+1,num,left-D[i]);
				num.pop_back();
			}
		}
	}
	
	string construct(vector <int> digits) {
		D=digits;
		N=D.size();
		S="z";
		
		vector<int> num;
		dfs(0,num,2*N);
		if(S=="z") S="";
		return S;
	}
}

まとめ

よくこういう問題設定思いつくな。