Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-02-09SRM531 Div1(Practice)

SRM531 Div1 300 NoRepeatPlaylist

| 02:27 | SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

EasyにしてはかなりハードなDP。300だけある・・

直前のM曲は全てdistinctであることを利用すると、残り何曲演奏されていないかを記憶するDPが可能

自分は直前のM曲を除いて1回以上演奏された曲が何曲あるか記憶するというよく分からない書き方をしてしまって時間がかなりかかった。


ソースコード

const int MOD=1000000007;

class NoRepeatPlaylist {
public:
	int numPlaylists(int N, int M, int P) {
		ll res=0;
		
		ll dp[102][102];
		memset(dp, 0, sizeof(dp));
		dp[0][0]=1;
		for(int i=0; i<P; i++) {
			for(int j=0; j<=N; j++) {
				if(i<M) dp[i+1][j]=(dp[i+1][j]+(dp[i][j]*(N-i))%MOD)%MOD;
				else {
					dp[i+1][j]=(dp[i+1][j]+(dp[i][j]*j)%MOD)%MOD;
					dp[i+1][j+1]=(dp[i+1][j+1]+(dp[i][j]*(N-M-j))%MOD)%MOD;
				}
			}
		}
		res=dp[P][N-M];
		return res;
	}
};

SRM531 Div1 500 MonsterFarm

| 02:27 | SRM531 Div1 500 MonsterFarm - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM531 Div1 500 MonsterFarm - SRM diary(Sigmar) SRM531 Div1 500 MonsterFarm - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

無限に増えるかどうかの判定がまず必要

普段ならとりあえず適当にループを回して、収束するかどうかを判定するところだが、今回はMODがかかっているので危険そうである

念のため頑張って無限に増えるかどうかを真面目に判定することにする

まずは、全ての2分岐以上に分岐するノードに対し、そのノードから出発して自分に戻ってくることができるかを判定する。

次に、始点からそのノードへ到達可能かを判定する。

これで無限に増えるかどうかが判定できた。何となく計算が冗長な気がしないでもないが、計算量は問題ない。

あとは、無限に増えない場合にシミュレーションを行うだけである。

何ステップで収束するか検討するのが面倒だったので、行列化して10億乗しておいた。さすがに大丈夫だろう・・・

一発で通った。


やっぱりMODは罠だったらしい。ちゃんと計算しておいて良かった。


ソースコード

//MODつきベクトル
class VectorGF {
private:
	vector <int> data;
	int vsize;
	int MOD;
public:
	VectorGF() { vsize=0; MOD=0; }
	VectorGF(int _vsize, int _MOD) { data.assign(_vsize, 0); vsize=_vsize; MOD=_MOD; }
	int size() const { return vsize; }
	void clear() { data.clear(); }
	void resize(int _vsize) { data.resize(_vsize); vsize=_vsize; }
	int mod() const { return MOD; }
	int mod(int _MOD) { MOD=_MOD; return MOD; }
	const int& operator[](const int idx) const { return data[idx]; }
	int& operator[](const int idx) { return data[idx]; }
	VectorGF operator*(const int mul) const {
		VectorGF res(vsize, MOD);
		for(int i=0; i<vsize; i++) res[i]=(ll)data[i]*mul%MOD;
		return res;
	}
};
VectorGF operator*(const int mul, const VectorGF& v) {
	VectorGF res(v.size(), v.mod());
	for(int i=0; i<(int)v.size(); i++) res[i]=(ll)v[i]*mul%v.mod();
	return res;
}

//MODつき行列
class MatrixGF {
private:
	vector <VectorGF> data;
	int rows, cols;
	int MOD;
public:
	MatrixGF() { rows=0; cols=0; MOD=0; }
	MatrixGF(int _rows, int _MOD) {
		data.assign(_rows, VectorGF(_rows, _MOD));
		for(int i=0; i<_rows; i++) data[i][i]=1;
		rows=_rows; cols=_rows; MOD=_MOD;
	}
	MatrixGF(int _rows, int _cols, int _MOD) { data.assign(_rows, VectorGF(_cols, _MOD)); rows=_rows; cols=_cols; MOD=_MOD; }
	int size1() const { return rows; }
	int size2() const { return cols; }
	void clear() { data.clear(); }
	void resize(int _rows, int _cols) {
		data.resize(_rows);
		for(int i=0; i<_rows; i++) data[i].resize(_cols);
		rows=_rows; cols=_cols;
	}
	int mod() const { return MOD; }
	int mod(int _MOD) { MOD=_MOD; return MOD; }
	const VectorGF& operator[](const int idx) const { return data[idx]; }
	VectorGF& operator[](const int idx) { return data[idx]; }
	MatrixGF operator+(const MatrixGF& b) const {
		MatrixGF res(rows, cols, MOD);
		for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) res[i][j]=((ll)data[i][j]+b[i][j])%MOD;
		return res;
	}
	MatrixGF operator-(const MatrixGF& b) const {
		MatrixGF res(rows, cols, MOD);
		for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) res[i][j]=((ll)data[i][j]-b[i][j])%MOD;
		return res;
	}
	MatrixGF operator*(const MatrixGF& b) const {
		if(cols!=(int)b.size1()) return MatrixGF(0, 0, MOD);
		MatrixGF res(rows, b.size2(), MOD);
		for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) {
			ll tmp=0;
			for(int k=0; k<cols; k++) tmp+=(ll)data[i][k]*b[k][j]%MOD;
			res[i][j]=(int)(tmp%MOD);
		}
		return res;
	}
	MatrixGF operator*(const int mul) const {
		MatrixGF res(rows, cols, MOD);
		for(int i=0; i<rows; i++) for(int j=0; j<cols; j++) res[i][j]=((ll)data[i][j]*mul)%MOD;
		return res;
	}
	VectorGF operator*(const VectorGF& v) const {
		if(cols!=(int)v.size()) return VectorGF(0, MOD);
		VectorGF res(rows, MOD);
		for(int i=0; i<rows; i++) {
			ll tmp=0;
			for(int k=0; k<cols; k++) tmp+=(ll)data[i][k]*v[k]%MOD;
			res[i]=(int)(tmp%MOD);
		}
		return res;
	}
	MatrixGF pow(int n) {
		if(rows!=cols) return MatrixGF(0, 0, MOD);
		if(n==0) return MatrixGF(rows, MOD);
		if(n%2==0) {
			MatrixGF tmp=this->pow(n/2);
			return tmp*tmp;
		} else {
			return (*this)*(this->pow(n-1));
		}
	}
	//E+A+A^2+...+A^n
	MatrixGF geometric_progression(int n) {
		if(rows!=cols) return MatrixGF(0, 0, MOD);
		if(n==0) return MatrixGF(rows, MOD);
		if(n%2==1) return (this->pow(n/2+1)+MatrixGF(rows, MOD))*this->geometric_progression(n/2);
		else return this->pow(n)+this->geometric_progression(n-1);
	}
};
MatrixGF operator*(const int mul, const MatrixGF& m) {
	MatrixGF res(m.size1(), m.size2(), m.mod());
	for(int i=0; i<(int)m.size1(); i++) for(int j=0; j<(int)m.size2(); j++) res[i][j]=(ll)m[i][j]*mul%m.mod();
	return res;
}

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;
}

const int MOD=1000000007;

class MonsterFarm {
public:
	bool loop(MatrixGF A) {
		int n=A.size1();
		int goal[52];
		memset(goal, 0, sizeof(goal));
		for(int i=0; i<n; i++) {
			int cnt=0;
			for(int j=0; j<n; j++) cnt+=A[j][i];
			if(cnt<=1) continue;
			int vis[52];
			memset(vis, 0, sizeof(vis));
			vis[i]=1;
			queue <int> q;
			q.push(i);
			bool ok=false;
			while(!q.empty()) {
				int qt=q.front(); q.pop();
				for(int j=0; j<n; j++) {
					if(A[j][qt]==0) continue;
					if(j==i) {
						goal[i]=1; ok=true; break;
					}
					if(vis[j]) continue;
					vis[j]=1;
					q.push(j);
				}
				if(ok) break;
			}
		}

		int vis[52];
		memset(vis, 0, sizeof(vis));
		vis[0]=1;
		queue <int> q;
		q.push(0);
		while(!q.empty()) {
			int qt=q.front(); q.pop();
			if(goal[qt]) return true;
			for(int j=0; j<n; j++) {
				if(A[j][qt]==0) continue;
				if(vis[j]) continue;
				vis[j]=1;
				q.push(j);
			}
		}

		return false;
	}

	int numMonsters(vector <string> trans) {
		int res;

		int n=trans.size();
		MatrixGF A(n, MOD);
		for(int i=0; i<n; i++) for(int j=0; j<n; j++) A[i][j]=0;
		for(int i=0; i<n; i++) {
			vector <int> vi=strspl <int>(trans[i]);
			for(int j=0; j<(int)vi.size(); j++) {
				A[vi[j]-1][i]++;
			}
		}

		if(loop(A)) return -1;

		A=A.pow(1000000000);
		VectorGF V(n, MOD);
		for(int i=0; i<n; i++) V[i]=0;
		V[0]=1;
		V=A*V;
		res=0;
		for(int i=0; i<n; i++) res=(res+V[i])%MOD;
		
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120209