KUPC2014 : C - 占い

問題のストーリーが無駄にややこしいかも。
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_c

問題

N,M,Qが与えられる。

N要素の数列A[i]とM要素の数列B[i]があるとする。
この時以下の条件を満たす最大のxを答えよ。

• (C[i],D[i])のペアがQ個与えられる。A[C[i]]==B[D[i]]である。
• i=1～x-1においてA[(i-1)%N]==B[(i-1)%M]で、i=xでA[(i-1)%N]!=B[(i-1)%M]となる。

解法

後者の条件より、x<=lcm(N,M)なのは明らかである。
G=gcd(N,M)として、

よって、AををM/G回、BをN/G回繰り返していずれもlcd(N,M)要素にした場合を考える。
この時、初期状態として、以下の値が同値であることをUnion-findで管理しよう。

• AはN要素を繰り返したものなので、A[i]とA[i+N*k]は同値。
• BはM要素を繰り返したものなので、B[i]とA[i+B*k]は同値。
• (C[i],D[i])のペアに対して、A[C[i]]とB[D[i]]は同値。

後は、A[x-1]!=B[x-1]となる最大のxを求めればよい。
i=0～N*M/G-1までの範囲で、A[i]!=B[i]ならiをxの候補としたうえでA[i]とB[i]をuniteし、処理を継続していく。

class UF {
	public:
	static const int ufmax=100002;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[x];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N,M,Q,G;
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>Q;
	G=N*M/__gcd(N,M);
	UF uf;
	FOR(i,Q) {
		cin>>x>>y;
		uf.unite(x-1,50000+y-1);
	}
	FOR(i,N) FOR(j,G/N) uf.unite(i,i+N*j);
	FOR(i,M) FOR(j,G/M) uf.unite(50000+i,50000+i+M*j);
	int ret=0;
	FOR(i,G) {
		if(uf[i] != uf[50000+i]) ret=i+1, uf.unite(i,50000+i);
	}
	cout << ret << endl;
	
}

まとめ

Union-findに気が付くと簡単。