Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-02Google Code Jam Japan 2011 練習問題

  • 練習問題ってGCJ2010の予選問題かと思ったらBだけ違った

Google Code Jam Japan 2011 練習問題 B 数の集合

| 01:46 | Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

区間篩ぽい問題

エラトステネスの篩で素数を作って

区間篩っぽくUnion-Findで結合していくだけ


ソースコード

//Union-Find Tree
class UFT {
public:
	int size;
	vector <int> dad;
	UFT(int size=0) {
		dad.assign(size, -1);
		this->size=size;
	}
	void assign(int size) {
		dad.assign(size, -1);
		this->size=size;
	}
	int ufind(int x, int y, bool dounion) {
		int t, s, i=x, j=y;
		while(dad[i]>=0) i=dad[i];
		while(dad[j]>=0) j=dad[j];
		t=x;
		while(dad[t]>=0) {s=t; t=dad[t]; dad[s]=i;}
		t=y;
		while(dad[t]>=0) {s=t; t=dad[t]; dad[s]=j;}
		if(dounion && (i!=j)) {
			if(dad[j]<dad[i]) {
				dad[j]+=dad[i]; dad[i]=j;
			} else {
				dad[i]+=dad[j]; dad[j]=i;
			}
		}
		return (i!=j);
	}
	int num_of_trees(void) {
		int res=0;
		for(int i=0; i<size; i++) if(dad[i]<0) res++;
		return res;
	}
	vector <int> size_of_trees(void) {
		vector <int> res;
		for(int i=0; i<size; i++) if(dad[i]<0) res.push_back(-dad[i]);
		return res;
	}
	vector <vector <int> > get_groups(void) {
		vector <vector <int> > res;
		vector <int> mp(size);
		int id=0;
		for(int i=0; i<size; i++) if(dad[i]<0) mp[i]=id++;
		res.resize(id);
		for(int i=0; i<size; i++) {
			int j=i; while(dad[j]>=0) j=dad[j];
			res[mp[j]].push_back(i);
		}
		sort(res.begin(), res.end());
		return res;
	}
	UFT operator=(const UFT & _op) {
		dad=_op.dad;
		size=_op.size;
		return *this;
	}
};

//エラトステネスの篩
vector <int> cpn(int n) {
	vector <int> vn(max(2, n+1), 1);

	vn[0]=vn[1]=0;
	for(int i=2; i*i<=n; i++) {
		if(!vn[i]) continue;
		for(int j=i*i; j<=n; j+=i) vn[j]=0;
	}
	
	return vn;
}

int solve(ll A, ll B, ll P) {
	int res=0;

	int d=B-A;
	vector <int> vpn=cpn(d);
	UFT eq(d+1);
	for(ll i=P; i<(ll)vpn.size(); i++) {
		if(!vpn[i]) continue;
		ll start=A/i*i;
		if(start<A) start+=i;
		for(ll j=start+i; j<=B; j+=i) {
			eq.ufind(start-A, j-A, true);
		}
	}
	res=eq.num_of_trees();
	
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		ll A, B, P;
		ifs >> A >> B >> P;
		int res=solve(A, B, P);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

TommyTommy 2013/02/18 19:38 A really good answer, full of raitonatliy!

CharlCharl 2013/02/18 19:38 It's like you're on a misison to save me time and money!

fxtvbyplipfxtvbyplip 2013/02/21 14:42 YzF6wS <a href="http://wazxjswkbbtm.com/">wazxjswkbbtm</a>

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111002