kmjp's blog

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

TopCoderOpen 2020 Round2A : Medium PrimeSubstrings

本番これ出たらいやだな…。
https://community.topcoder.com/stat?c=problem_statement&pm=16251&rd=18068

問題

正整数N,Kが与えられる。
N桁の正整数のうち、どこのK桁を抜き出してもLeading Zeroを含まない素数になっているものを求めよ。

解法

K桁の素数をリピートしたものを総当たりすると、K=7以外は回答できる。
K=7の時7桁の素数で条件を満たすものはないが、8桁の素数まで見ると解がある。

const int prime_max = 10000000;
vector<int> prime;
int NP;
bool divp[prime_max];

void cprime() {
	if(NP) return;
	divp[1]=1;
	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]=1;
	}
}

class PrimeSubstrings {
	public:
	int L;
	int ok(int p,int L) {
		string S=to_string(p),T;
		while(T.size()<S.size()+L) T+=S;
		int i;
		FOR(i,S.size()) {
			if(T[i]=='0') return 0;
			int v=atoi(T.substr(i,L).c_str());
			if(divp[v]) return 0;
		}
		return 1;
	}
	
	int dfs(int p,int d) {
		if(ok(p,L)) return p;
		if(d==8) return 0;
		
		int i,v;
		FOR(i,5) {
			v=dfs(p*10+i*2+1,d+1);
			if(v) return v;
		}
		return 0;
	}
	
	string construct(int N, int L) {
		this->L=L;
		cprime();

		string S=to_string(dfs(0,0)),T;
		int i;
		FOR(i,N) T+=S[i%S.size()];
		return T;
	}
}

まとめ

2Bといい2Aといいしんどい問題。