TopCoderOpen 2017 Round3A Easy CoprimeMatrix

0完でHighest更新…。
https://community.topcoder.com/stat?c=problem_statement&pm=14645

問題

N要素の数列A[i]があるとする。A[i]は正整数で構成され、A[i+1]=A[i]+1を満たす。
ここでN*Nの行列C[i][j]が与えられる。
C[i][j] := A[i]とA[j]が互いに素かどうかを示す真偽値(Y/N)
とするとき、条件を満たすAが存在するか判定せよ。

解法

先にコーナーケースを処理する。

対角成分C[0][0]=Yとなるのは、A[0]=1のときだけである。
よってC[0][0]=YのケースはAがすべてわかるので互いに素か判定するだけである。
そうでない場合、対角成分はNであり、かつ対象行列であることを確認しておこう。

Cから得られる情報を用いて、Cと同等の行列C'を再構築し、両者が一致するかを判定する。
N以下の素数pに対し以下を行おう。
A[i]とA[i+p]が互いに素でないのは、A[i]がもともとpの倍数の場合だけである(両者のGCDを取れば明らか)。
ここでC[i][i+p]=Yとなるiが1つあったとする。するとA[i]はpの倍数なのでA[i+kp]はいずれもpの倍数である。
この情報から、C'に対してC'[i][i+kp]はYでなければならず、i+kpの形を取らないjに対しC'[j][j+kp]はNでなければならないという条件が得られる。

あとは上記処理を繰り返して得られるCとC'が一致するなら条件を満たす。

class CoprimeMatrix {
	public:

	string isPossible(vector <string> coprime) {
		string YES="Possible";
		string NO="Impossible";
		
		int N=coprime.size();
		int i,j,x,y;
		FOR(x,N) FOR(y,N) coprime[x][y]=coprime[x][y]=='Y';
		
		if(coprime[0][0]) {
			FOR(x,N) FOR(y,N) if(coprime[x][y] != (__gcd(x+1,y+1)==1)) return NO;
			return YES;
		}
		
		FOR(x,N) FOR(y,N) {
			if(x==y && coprime[x][x]) return NO;
			if(coprime[x][y]!=coprime[y][x]) return NO;
		}
		
		auto A=coprime;
		FOR(x,N) FOR(y,N) A[y][x]=x!=y;
		
		for(i=2;i<=N;i++) {
			for(j=2;j<i;j++) if(i%j==0) break;
			if(j!=i) continue;
			x = -1;
			for(j=0;j<i && j+i<N; j++) {
				if(coprime[j][j+i]==0) {
					x = j;
					break;
				}
			}
			if(j==i) return NO;
			
			if(x>=0) {
				for(;x<N;x+=i) for(y=x+i;y<N;y+=i) A[x][y]=A[y][x]=0;
			}
		}
		
		return (A==coprime)?YES:NO;
	}
}

まとめ

さすがに普段のDiv1 Easyより難しめ。