Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-03SRM534 Div1(Practice)

SRM534 Div1 250 EllysCheckers

| 17:24 | SRM534 Div1 250 EllysCheckers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM534 Div1 250 EllysCheckers - SRM diary(Sigmar) SRM534 Div1 250 EllysCheckers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

普通にビットでメモ化再帰した

DP/メモ化で解ける問題はそのほうが確実性が高いように思うのでもっと効率のいい方法を考えることはしていない

しかし結構実装が大変・・・


ソースコード

int memo[1<<20];

class EllysCheckers {
public:
	int n;

	int rec(int mask) {
		if(memo[mask]>=0) return memo[mask];

		int res=0;
		for(int i=0; i<n-1; i++) {
			if(!(mask&(1<<i))) continue;
			if(!(mask&(1<<(i+1)))) {
				int nmask=(mask^(1<<i));
				if(i+1<n-1) nmask^=(1<<(i+1));
				if(rec(nmask)==0) res=1;
			}
			if(i+3<n && (mask&(1<<(i+1))) && (mask&(1<<(i+2))) && !(mask&(1<<(i+3)))) {
				int nmask=(mask^(1<<i));
				if(i+3<n-1) nmask^=(1<<(i+3));
				if(rec(nmask)==0) res=1;
			}
		}

		memo[mask]=res;
		return res;
	}

	string getWinner(string board) {
		string res;
		n=board.size();

		memset(memo, -1, sizeof(memo));
		int beg=0;
		for(int i=0; i<n-1; i++) {
			if(board[i]=='o') beg|=(1<<i);
		}
		if(rec(beg)) res="YES";
		else res="NO";
		
		return res;
	}
};

SRM534 Div1 500 EllysNumbers

| 17:24 | SRM534 Div1 500 EllysNumbers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM534 Div1 500 EllysNumbers - SRM diary(Sigmar) SRM534 Div1 500 EllysNumbers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

special numberは値が小さいので全部素因数分解する

ここで登場する素因数で、nが割り切れなければそもそも無理なので0

nが割り切れるならば1になるまで割り切って、素因数分解することができる

あとは互いに素ということなので、同じ素因数を含まないように要素を組み合わせる必要がある

ということは、例えばn=2^3*3^2*5とかであれば、2^3や3^2や5をひとまとまりとして考えればいい

このような素因数は、10^18でもせいぜい15個くらいにしか分解できない

なので、2^15くらいでビットDPすればいい


実装は結構ハードだった・・・


ソースコード

ll dp[2][1<<16];

template <class T> vector <T> strspl(string str) {
	vector <T> res;
	istringstream iss(str);
	copy(istream_iterator <T>(iss), istream_iterator <T>(), back_inserter(res));
	return res;
}

vector <pair <ll, int> > factorp(ll n) {
	vector <pair <ll, int> > f;

	for(ll i=2; i*i<=n; i++) {
		int cnt=0;
		while(n%i==0) { n/=i; cnt++; }
		if(cnt>0) f.push_back(make_pair(i, cnt));
	}
	if(n>1) f.push_back(make_pair(n, 1));

	return f;
}

class EllysNumbers {
public:
	long long getSubsets(long long N, vector <string> special) {
		long long res;
		string s=accumulate(special.begin(), special.end(), string());
		vector <int> vi=strspl <int>(s);
		int n=vi.size();
		sort(vi.begin(), vi.end());

		vector <vector <pair <ll, int> > > factv;
		vector <ll> fact;

		for(int i=0; i<n; i++) {
			factv.push_back(factorp(vi[i]));
			for(int j=0; j<(int)factv[i].size(); j++) fact.push_back(factv[i][j].first);
		}
		sort(fact.begin(), fact.end());
		fact.erase(unique(fact.begin(), fact.end()), fact.end());

		vector <pair <ll, int> > nfact;
		for(int i=0; i<(int)fact.size(); i++) {
			int cnt=0;
			while(N%fact[i]==0) {cnt++; N/=fact[i]; }
			if(cnt) nfact.push_back(make_pair(fact[i], cnt));
		}
		if(N!=1) return 0;

		int nfacts=nfact.size();
		vector <int> fmask(n);
		int canapp[510]={0};
		for(int i=0; i<n; i++) {
			canapp[i]=1;
			for(int j=0; j<(int)factv[i].size(); j++) {
				bool ok=false;
				int idx=-1;
				for(int k=0; k<nfacts; k++) {
					if(factv[i][j]==nfact[k]) {ok=true; idx=k; }
				}
				if(!ok) {canapp[i]=0; break; }
				fmask[i]|=(1<<idx);
			}
		}

		memset(dp[0], 0, sizeof(dp[0]));
		dp[0][(1<<nfacts)-1]=1;
		for(int d=0; d<n; d++) {
			memcpy(dp[(d+1)&1], dp[d&1], sizeof(dp[d&1]));
			if(!canapp[d]) continue;
			for(int mask=0; mask<(1<<nfacts); mask++) {
				if((mask&fmask[d])==fmask[d]) dp[(d+1)&1][mask^fmask[d]]+=dp[d&1][mask];
			}
		}

		res=dp[n&1][0];
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120303