TopCoder SRM 531 Div1 Medium MonsterFarm

なんか似た問題をCodeforcesやGCJで見たことある気がする。
http://community.topcoder.com/stat?c=problem_statement&pm=11232

問題

この世界にはN種類のモンスターがいる。
各モンスターは、１日毎に死亡し、その際他の(1体または複数の)モンスターを生成する。

初期状態では1番の種類のモンスター１体がいる。
時間が経過すると、モンスターは最終的に何体になるか。

解法

各モンスターは死亡時に毎晩１体以上のモンスターを生成するため、モンスターの総数は減少しない。
よって大別すると、モンスターは一定時間後：

• 時間経過に伴い無限に増加する
• それ以上増加しなくなる

のいずれかである。
無限に増加する条件は、あるモンスターから数日後そのモンスターが生成される、すなわち生成の関係が循環しており、かつ死亡時に２体以上のモンスターを生成するモンスターがいる場合である。
このモンスターが存在すると、１周生成するたびに追加のモンスターを生成するので、無限に増加する。

無限に増加しない場合、どこかで打ち止めになるのでN^2日程度経過すればいずれ増加が止まる。
よって以下では適当に10000日処理を繰り返してみた。

vector<int> split_int(const string &str, char delim){
	vector<int> res;
	size_t current = 0, found;
	while((found = str.find_first_of(delim, current)) != string::npos){
		string s = string(str, current, found - current);
		res.push_back(atoi(s.c_str()));
		current = found + 1;
	}
	string s = string(str, current, str.size() - current);
	res.push_back(atoi(s.c_str()));
	return res;
}

ll mo=1000000007;

class MonsterFarm {
	public:
	int gen[51][51], mat[51][51], tgen[51];
	int N;
	int vis[51];
	
	int numMonsters(vector <string> transforms) {
		int i,x,y;
		
		N=transforms.size();
		ZERO(gen);
		FOR(x,N) FOR(y,N) mat[x][y]=1;
		
		FOR(i,N) {
			vector<int> V=split_int(transforms[i],' ');
			ITR(it,V) gen[i][*it-1]++, mat[i][*it-1]=0;
			tgen[i]=V.size();
		}
		FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
		
		FOR(x,N) if(mat[x][x]==0 && mat[0][x]==0) {
			FOR(y,N) if(mat[x][y]==0 && mat[y][x]==0 && tgen[y]>1) return -1;
		}
		
		ll dp[51];
		ZERO(dp);
		dp[0]=1;
		FOR(i,10000) {
			FOR(x,N) {
				ll hoge=dp[x];
				dp[x]=0;
				FOR(y,N) dp[y]=(dp[y]+hoge*gen[x][y])%mo;
			}
		}
		ll ret=0;
		FOR(x,N) ret+=dp[x];
		return ret%mo;
	}
};

まとめ

この変な入力形式、やめてほしいな…。