yukicoder : No.30 たこやき工場

お、問題番号２とは。
http://yukicoder.me/problems/2

問題

1～(N-1)番の材料を用いてN番の製品を作りたい。
自社で作れるものとして、M個のリストが与えられる。
各リストはP[i]の番号の材料Q[i]個でR[i]の材料/製品が１個作れることを示す。

なお、各材料/製品を作るのに自分自身を必要とすることはない。

自社で作れる材料は自社で作り、自社で作れないものは外部から調達する。
N番の製品を1個作るのに外部から調達しなければいけない各材料の数を求めよ。

解法

i番の材料/製品を１個作るのに必要なj番の材料数をF(i,j)とし、これをメモ化再帰で埋めていく。
最終的にF(N-1,j)をそれぞれ出力すればよい。

• i番が自製できない場合、F(i,i)=1, F(i,j)=0 (i!=j)となる。
• i番が自製できる場合、R[x]=iとなるxに対しF(i,j) += Q[x] * F(P[x],j)となる。

int N,M;
vector<pair<int,int> > V[101];
ll memo[101][101];
ll tot[101];

void dfs(int cur) {
	if(memo[cur][0]>=0) return;
	ZERO(memo[cur]);
	if(V[cur].empty()) {
		memo[cur][cur]=1;
		return;
	}
	
	int i,j;
	FOR(i,V[cur].size()) {
		dfs(V[cur][i].first);
		FOR(j,N) memo[cur][j] += V[cur][i].second*memo[V[cur][i].first][j];
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>j>>k>>l;
		V[l-1].push_back(make_pair(j-1,k));
	}
	MINUS(memo);
	dfs(N-1);
	FOR(i,N-1) cout<<memo[N-1][i]<<endl;
}

まとめ

なぜたこ焼きなんだろう。