TopCoder SRM 759 Div1 Easy Div2 Medium EllysThreePrimes

今回Easy/Mediumが余り頭使う要素がないなぁ。
https://community.topcoder.com/stat?c=problem_statement&pm=15436

問題

5つの整数が与えられる。
3つの異なる5ケタの素数の組で、各桁の和が入力と等しくなる組があればそれを答えよ。

解法

5桁の素数は8000個程度なので、2つを総当たりしよう。
入力値から残り1つの値が確定するので、それが素数か判定する。

ループ回数が多いので、素数判定はO(1)で済むよう、前処理でエラトステネスの篩を行っておこう。

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) {
		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;
	}
}

class EllysThreePrimes {
	public:
	vector <int> getPrimes(vector <int> sums) {
		cprime();
		vector<int> V;
		int x,y;
		for(int i=10000;i<100000;i++) if(divp[i]==0) V.push_back(i);
		FORR(x,V) FORR(y,V) if(x!=y) {
			int a=sums[4]-(x/10000%10)-(y/10000%10);
			int b=sums[3]-(x/1000%10)-(y/1000%10);
			int c=sums[2]-(x/100%10)-(y/100%10);
			int d=sums[1]-(x/10%10)-(y/10%10);
			int e=sums[0]-(x/1%10)-(y/1%10);
			if(a<=0 || b<0 || c<0 || d<0 || e<0) continue;
			if(a>9 || b>9 || c>9 || d>9 || e>9) continue;
			int z=a*10000+b*1000+c*100+d*10+e;
			if(divp[z]) continue;
			if(x==y || y==z || z==x) continue;
			return {x,y,z};
		}
		return {};
		
	}
}

まとめ

落ちてる人以外に多かったけどひっかけ要素どこだったんだろう。