kmjp's blog

競技プログラミング参加記です

TopCoder SRM 813 : Div1 Hard PrettyPrimes

うーむ。
https://community.topcoder.com/stat?c=problem_statement&pm=17160&rd=18868

問題

2桁以下の整数Pが与えられる。
D桁の整数のうち、(Dを文字列としてみなしたときの)Pの登場回数が最多タイになるようなものの総和を求めよ。

解法

素数判定が愚直にO(√N)かかるとすると、あとは候補をいかに絞り込むかという問題になる。

まずは、登場回数のパターンを数え上げよう。
Dの各桁について、Pの各桁と同じかそれと異なるか、3^|D|通りの組み合わせを考え、Pの登場回数を数えよう。
例えばP=12なら、"1""2""?"で構成されるD文字の文字列を考えてみるとよい。

その後、登場回数の多い順に、各パターンに該当する整数のうち素数のものを洗い出す。

const int prime_max = 1000000;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

//素数判定
bool isprime(ll v) {
	cprime();
	int p;
	if(v==1) return 0;
	if(v==2) return 1;
	FORR(p,prime) {
		if(v%p==0) return 0;
		if(1LL*p*p>=v) return 1;
	}
	return 1;
}



const ll mo=1000000007;
class PrettyPrimes {
	public:
	string P;
	vector<string> pat[13];
	
	void dfs(int D,string C) {
		if(C.size()==D) {
			int i;
			int oc=0;
			for(i=0;i+P.size()<=C.size();i++) {
				if(C.substr(i,P.size())==P) oc++;
			}
			pat[oc].push_back(C);
			return;
			
		}
		C+="?";
		dfs(D,C);
		C.back()=P[0];
		dfs(D,C);
		if(P.size()==2&&P[0]!=P[1]) {
			C.back()=P[1];
			dfs(D,C);
		}
		
	}
	
	ll hoge(string& p,int cur,ll v) {
		if(cur==p.size()) {
			if(isprime(v)) {
				return v;
			}
			else return 0;
		}
		if(p[cur]=='?') {
			ll sum=0;
			for(int i=0;i<10;i++) {
				if(cur==0&&i==0) continue;
				if(i==P[0]-'0') continue;
				if(i==P.back()-'0') continue;
				sum+=hoge(p,cur+1,v*10+i);
			}
			return sum%mo;
		}
		else {
			if(cur==0&&p[cur]=='0') return 0;
			return hoge(p,cur+1,v*10+p[cur]-'0');
		}
		
	}
	
	int solve(int pattern, int D) {
		int i,j,x;
		FOR(i,12) pat[i].clear();
		
		P=to_string(pattern);
		dfs(D,"");
		for(i=D;i>=0;i--) {
			ll sum=0;
			ll ok=0;
			FORR(a,pat[i]) {
				ll v=hoge(a,0,0);
				if(v) {
					(sum+=v)%=mo;
					ok=1;
				}
			}
			if(ok) return sum;
		}
		return 0%mo;
		
		
	}
}

まとめ

けれ計算量どうなるんだろ。