TopCoder SRM 524 Div2 Hard MultiplesWithLimit

正答まで若干苦戦したけど、解法自体はすんなり思いついた。
http://community.topcoder.com/stat?c=problem_statement&pm=11629

問題

自然数Nと、使用不可の数字群が与えられる。
自然数Nを自然数倍した数値で、各桁に使用不可の数字群を含まない最小の数値を答えよ。

なお、数値が８ケタまでならその数値を解答し、９ケタ以上なら先頭と末尾の３ケタおよび全体の桁数を答えよ。

解法

数値が８ケタ以内になる99999999までは単純にNの倍数を順に見ていって使用不可な数字を含まないものを列挙すればよい。
もちろんそのような数値が見つかればそれで終了。

９ケタ以上に答えがある可能性がある場合、先頭４桁が1000～9999となるようなNの倍数に対し、下３桁と全体の桁数を覚えておき、探索していく。
初期状態として、最初の99999999までの判定の間で、Nが倍数が7桁以上になる場合、上記桁数・下３桁を覚えておく。

後は桁数が最小となる先頭４桁に対し探索をする。先頭４桁にNの倍数を足せば当然Nの倍数で、あとは先頭4桁+N*kが使用不可な数字を含まない場合、先頭4桁に対する最少桁数を更新していけばよい。

int keta[10000];
int btm[10000]; 

class MultiplesWithLimit {
	public:
	int ng[10];
	
	int ok(ll val) {
		while(val) {
			if(ng[val%10]) return 0;
			val /=10;
		}
		return 1;
	}
	
	string minMultiples(int N, vector <int> forbiddenDigits) {
		int i,j,k;
		
		ZERO(ng);
		FOR(i,forbiddenDigits.size()) ng[forbiddenDigits[i]]=1;
		
		FOR(i,10000) keta[i]=1000000,btm[i]=0;
		
		j=1;k=0;
		set<pair<int,pair<int,int> > > S;
		for(int a=N;a<100000000LL;a+=N) {
			if(N<=10 && a>=10000000) break;
			if(ok(a)) {
				char hoge[20];
				sprintf(hoge,"%d",a);
				return string(hoge);
			}
			if(a>=j*10000) j*=10,k++;
			if(j>=1000 && keta[a/j]>k && ok(a%j)) {
				
				if(ng[0]&&(a%j)<j/10) continue;
				keta[a/j]=k;
				btm[a/j]=a%1000;
				S.insert(make_pair(k,make_pair(a/j,btm[a/j])));
			}
		}
		
		if(N==10000) return "IMPOSSIBLE";
		
		while(!S.empty()) {
			k=S.begin()->first;
			int to=S.begin()->second.first;
			int bt=S.begin()->second.second;
			S.erase(S.begin());
			
			if(!ng[to%10] && !ng[to/10%10] && !ng[to/100%10] && !ng[to/1000%10]) {
				char hoge[20];
				sprintf(hoge,"%d%d%d...%d%d%d(%d digits)",
					to/1000%10,to/100%10,to/10%10,
					bt/100%10,bt/10%10,bt%10,k+4);
				return string(hoge);
			}
			FOR(i,10000) {
				int to2=to+N*(1+i);
				int k2=k;
				while(to2>=10000) {
					if(ng[to2%10]) goto out;
					to2/=10;
					k2++;
				}
				if(keta[to2]>k2) {
					keta[to2]=k2;
					btm[to2]=bt;
					S.insert(make_pair(k2,make_pair(to2,bt)));
				}
				out:
				;
			}
		}
		return "IMPOSSIBLE";
	}
};

まとめ

答え方が珍しい問題。