今回は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; } }
まとめ
よくこういう問題設定思いつくな。