Codeforces 71 E. Nuclear Fusion

問題

核反応を考える。
反応前のn個の元素のリストおよび、
反応後のm個の元素のリストが与えられる。

反応前の元素から核反応により反応後の元素を過不足なく作れるか判定せよ。
ただし、反応後の元素は直接作られなければならない。（途中で別の元素を経由してはならない）

核反応は、x1+x2+x3…xi->yという形式でのみ起こるものとする。
加えて、両辺で原子番号の和が等しいものとする。

制約条件

n,m≦17
原子番号は100番まで

方針

ビットDP+経路復元.
dp[i][j]を反応後の元素をi個目まで作ったときに反応前の元素がj余っている
ような状態になることが可能であるかとする。
ここからjの部分集合について考えることで漸化式が作れてDPできる。

元素の集合に対する原子番号の和はあらかじめ前処理で計算しておく。

ソースコード

char *elem[]={
 "H", "He", "Li", "Be", "B", "C", "N", "O", "F", "Ne",
 "Na", "Mg", "Al", "Si", "P", "S", "Cl", "Ar", "K", "Ca",
 "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu", "Zn", "Ga",
 "Ge", "As", "Se", "Br", "Kr", "Rb", "Sr", "Y", "Zr", "Nb", "Mo",
 "Tc", "Ru", "Rh", "Pd", "Ag", "Cd", "In", "Sn", "Sb", "Te", "I",
 "Xe", "Cs", "Ba", "La", "Ce", "Pr", "Nd", "Pm", "Sm", "Eu", "Gd",
 "Tb", "Dy", "Ho", "Er", "Tm", "Yb", "Lu", "Hf", "Ta", "W", "Re",
 "Os", "Ir", "Pt", "Au", "Hg", "Tl", "Pb", "Bi", "Po", "At", "Rn",
 "Fr", "Ra", "Ac", "Th", "Pa", "U", "Np", "Pu", "Am", "Cm", "Bk",
 "Cf", "Es", "Fm",
};
int n,m,a[20],b[20];
int prev[18][1<<17];
int sum[1<<17];

void run()
{
	map<string,int> id;
	rep(i,100)id[elem[i]]=i+1;
	memset(prev,-1,sizeof(prev));
	
	cin>>n>>m;
	rep(i,n){
		string s; cin>>s;
		a[i]=id[s];
	}
	memset(sum,0,sizeof(sum));
	rep(i,1<<n)rep(j,n)if(i&1<<j)sum[i]+=a[j];
	
	rep(i,m){
		string s; cin>>s;
		b[i]=id[s];
	}
	prev[0][(1<<n)-1]=0;
	rep(i,m)rep(j,1<<n)if(prev[i][j]>=0){
		for(int k=j;k;k=k-1&j)
			if(sum[k]==b[i])prev[i+1][j^k]=j;
	}
	if(prev[m][0]==-1)cout<<"NO"<<endl;
	else{
		cout<<"YES"<<endl;
		vector<string> ans;
		int bit=0;
		for(int i=m;i>0;i--){
			int diff=bit^prev[i][bit];
			stringstream ss;
			bool first=1;
			rep(j,n)if(diff&1<<j){
				if(!first)ss<<"+";
				else first=0;
				ss<<elem[a[j]-1];
			}
			ss<<"->"<<elem[b[i-1]-1];
			bit=prev[i][bit];
			ans.pb(ss.str());
		}
		for(int i=m-1;i>=0;i--)cout<<ans[i]<<endl;
	}
}