Hatena::Grouptopcoder

kuuso1の日記

2014-07-09

KUPC C-占い

| 05:26 | KUPC C-占い  - kuuso1の日記 を含むブックマーク はてなブックマーク - KUPC C-占い  - kuuso1の日記

http://kupc2014.contest.atcoder.jp/tasks/kupc2014_c

  • int N,M,QとQ個の条件 {(C_i,D_i)} i=1 to Q が与えられる
  • 京子さんと結衣さんがそれぞれ数列{A_i},i=1 to N と数列{B_j},j=1 to M を思い描く。
  • その際、「AのC_i番目とBのD_i番目の数は等しい」という条件(Q個)を満たす。
  • 京子さんと結衣さんは同時にホワイトボードに数列の数字を1から順に書き出していく。なくなったらまた1から巡回する。
  • 二人が書いた数字が異なる時に終了し、それまでに書いた数字の個数をスコアとして、スコアが最大となるようにする。ただし10^10を超えた場合は0とみなす。

(制約)1≦N,M,Q≦200, 条件 {(C_i,D_i)} に重複はない。

LCM(N,M)回後には京子さんも結衣さんも1に戻るので、そこで一致してしまうと無限ループとなりスコアは0になる。

従って、LCM(M,N)より小さいところで終わらなければならない。

A_iとB_jが場にある時に2つの値を同じにしていけばスコアを伸ばしていけるが、過去の手続きによってすでにA_iとB_jが同じになる場合には、ここで終わることができない。

言い換えれば、A_iとB_jが場にある時に2者の値が同じになっていなければそこで打ち切ることができるため、LCM(N,M)までの手続きのなかで打ち切ることができる最大の点を探せばよい。

場に並んだ2つの数A_iとB_jを同じグループにしながらUnionFindを更新・管理すればよい。

class Sol{
	public void Solve(){
		var d=ria();
		int q;
		N=d[0];M=d[1];q=d[2];
		UnionFind UF=new UnionFind(N+M);
		
		for(int i=0;i<q;i++){
			d=ria();
			UF.Union(d[0]-1,N+d[1]-1);
		}
		
		int LoopMax=N*M/gcd(N,M);//ループの最終単位はlcm(M,N)
		//int LoopMax=N*M;
		bool[] canBreak=new bool[LoopMax];
		for(int i=0;i<LoopMax;i++){
			int A=i%N;
			int B=i%M;
			canBreak[i]=!UF.areSameGp(A,N+B);
			UF.Union(A,N+B);
		}

		int ans=0;
		for(int i=0;i<LoopMax;i++){
			if(canBreak[i])ans=i+1;//ans++;
		}
		
		Console.WriteLine("{0}",ans);
	}

	int N;
	int M;
	public Sol(){
	}
	int gcd(int a,int b){
		if(a==0)return b;
		return gcd(b%a,a);
	}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
}

class UnionFind{
	int[] parent;
	int N;
	public UnionFind(int n_){
		Initialize(n_);
	}
	public void Initialize(int n_){
		N=n_;
		parent=new int[N];
		for(int i=0;i<N;i++)parent[i]=i;
	}
	public int Parent(int a){
		if(parent[a]==a)return a;
		return parent[a]=Parent(parent[a]);
	}
	public bool areSameGp(int a,int b){
		return Parent(a)==Parent(b);
	}
	public void Union(int a,int b){
		a=Parent(a);b=Parent(b);//Parent()を呼ぶことでa以上のノードは全てparentがrootになる
		if(a==b)return;
		parent[a]=b;
	}
	public void Dump(){
		for(int i=0;i<parent.Length;i++){
			Console.Write(i==0?"{0}":" {0}",parent[i]);
		}
		Console.WriteLine("");
	}
}

本番中はUnionFindっぽいと思いながら停止条件をちゃんと考えられなかったので、復習でAC

実はUnionFind初めて書いたがこれはいいものですね。