TopCoder 2019 Humblefool Cup Prelims : Div1 Hard PrimeAlters

ええ…。
https://community.topcoder.com/stat?c=problem_statement&pm=15337

問題

素数Sが与えられる。下記処理を繰り返し素数Tに遷移できるか判定せよ。

• 1つの桁を選択し、その値を任意の値に差し替える。ただしLeading Zeroが生じてはならないし、差し替えた後の値も素数でなければならない。

解法

本番解いた人はほぼ埋め込みだった。

UnionFindで愚直に遷移可能な素数同士をマージしてみよう。
登場する数の最大値が10^8近いので、手元で行う。
すると以下のことがわかる。

• 89391959と89591959は互いに遷移可能で、それ以外の素数には遷移できない。
• 6桁以上の素数では、他に遷移先が全くないものが400個ほど存在する
• それ以外に孤立する素数はなく、同じ桁同士なら互いに遷移可能

あとは埋め込む。
以下コメント内は埋め込みのために使用したコードである。

/*
template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

const int prime_max = 100000000;
vector<int> prime;
int NP,divp[prime_max+5];

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

UF<101010000> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	for(i=2;i<prime_max;i++) if(divp[i]==0) {
		for(int d=0,p=1;p<=i;d++,p*=10) {
			x=i-(i/p%10)*p;
			FOR(y,10) {
				if(p*10>i&&y==0) continue;
				r=x+p*y;
				if(divp[r]==0) uf(i,r);
			}
		}
	}
	for(i=2;i<prime_max;i++) if(divp[i]==0 && (uf[i]==i||uf.count(i)<=2)) cout<<i<<" "<<uf.count(i)<<endl;
	
}
*/

set<int> X={89391959,89591959};
set<int> Y={
294001,505447,584141,604171,929573,971767,1062599,1282529,1524181,2017963,2474431,
2690201,3070663,3085553,3326489,4393139,5152507,5285767,5564453,5575259,5974249,6173731,
6191371,6236179,6463267,6712591,7204777,7469789,7469797,7810223,7858771,7982543,8090057,
8353427,8532761,8639089,9016079,9262697,9537371,9608189,9663683,9700429,9931447,10506191,
10532453,10564877,11124403,11593019,12325739,12968519,14075273,14090887,14151757,15973733,16497121,
17412427,17412599,17424721,18561293,18953677,19106729,19158221,19579907,19851991,20212327,20414561,
21044557,21089489,21281479,21496661,21668839,21717601,21825337,22138349,22431391,22480351,23196157,
23228479,23274191,23462969,24328567,25081361,25151927,25475617,25556941,25768091,25872199,25948847,
26024267,26521721,27242179,27245539,27425521,27465103,27469241,28046353,28070047,28978889,29136091,
29348797,29617897,29638519,30791767,30915637,30964013,31181461,31240481,31746383,31839427,32524313,
33051769,34302127,34349969,34586371,35009671,35319367,35355923,35673679,35954509,36221597,36438379,
36745811,37074487,37095427,37448137,37763641,38178211,38530123,38585039,38774851,38888137,39397009,
39600559,39689597,39724417,40085977,40432489,40638727,40812781,41745331,41980441,42120581,42145837,
42758917,43414669,43432409,43924399,43988459,44617561,44750351,45412331,45420457,45743483,46031123,
46301219,46448719,46591507,47263001,47457367,47500217,47632271,47744239,48024359,48143047,48341959,
48384977,48441331,49259803,49353841,49453847,50030077,50170513,50413439,50456519,50471857,50592911,
50729603,51340909,52127189,53355689,53420963,53454589,53751119,53753587,53977403,54048263,54127231,
54292081,54559123,54868459,55204889,55959643,56242891,56485057,56660599,56690071,56743469,57013823,
57177889,57375139,57980963,58020581,58091653,58107953,58366619,58572593,59088739,59160317,59704529,
59816347,60114073,60496231,60949807,61089089,61363157,61552901,61575539,61589579,61974541,62155259,
62324861,62444033,62552489,62725253,63359161,64085921,64087411,64353493,64843237,65029997,65040751,
65314439,65366051,65420917,65702393,65947213,66117679,66640253,66854549,67149403,67296517,67489091,
67715653,67959743,68030449,68428379,68495347,68970457,69315427,69374167,69375203,69505109,69912431,
70006253,70078549,70498907,70514141,70717291,70850641,71364053,71370853,71756029,71760109,72168857,
72418187,72422393,72504457,72519631,72534029,72673213,72760297,73022273,73115993,73179193,73440439,
73644101,74143801,74190419,74543663,74711779,75374149,75448801,75460849,75957857,76297087,76424609,
76456141,76720291,76828823,77250497,77438461,77444701,77511487,77540017,77675639,77844287,78050209,
78440119,78562307,78712681,78958211,79477127,79522043,79556513,79833133,80054363,80286407,80468587,
81397777,81434501,81536501,81594283,81608981,81738799,81811589,82087813,82319411,82542419,82742243,
82761961,82764371,82817039,82892633,82905047,83127119,83407327,83610599,83880829,84083011,84159917,
84255251,84487439,84733919,85415249,85468223,85478369,85637089,86504879,86688269,87055763,87077527,
87281011,87303817,87517271,87615019,87737701,88551439,88826693,88903379,88948439,89006641,89146619,
89473777,89602771,89819413,90997241,91384849,92027977,92305589,92519951,92707619,92782441,93117217,
93573091,93831383,94113781,94874159,94912583,95401417,95517517,95532289,95640361,95663761,95708237,
95992103,96282569,96711581,97069493,97163797,97165001,97283321,97312819,97353379,97518247,97551143,
97792117,97864961,97994641,98188099,98240249,98285017,98372203,98451193,98482651,98643439,98701003,
98750609,98954621,98977741,99041179,99157987,99196763,99425279,99595919,99778351,99954053,
};

class PrimeAlters {
	public:
	int can(int A,int B) {
		if(A==B) return 1;
		if(X.count(A) && X.count(B)) return 1;
		if(X.count(A) || X.count(B)) return 0;
		if(Y.count(A) || Y.count(B)) return 0;
		return 1;
	}
	
	string isReachable(vector <int> source, vector <int> target) {
		string S;
		int i;
		FOR(i,source.size()) {
			if(can(source[i],target[i])) S+="1";
			else S+="0";
		}
		return S;
	}
}

まとめ

Mediumは入力のサイズ間違えてSEGVしてたし、こっちは自力で埋め込み思いつかなかったので、本番出てたら大怪我してた。