TopCoder SRM 344 Div1 Medium QuantumAlchemy

問題

A〜Zのアルファベットで表される物質がある。
最初initialで表される物質を持っている。

錬金反応を何度か起こして物質Xを作りたい。
錬金反応は最低何回起こさなければならないか、求めよ。

錬金反応は、
原料の物質->目的の物質の形式で与えられる。
原料の物質は必ず二つ以上であり、ある1種類の目的の物質を作る反応は高々一つしかない。

制約条件

initialの大きさは50以下

方針

Xから逆に探索していく。

X<-ABCだったとき、初期状態で持っていない物質があれば、その物質は必ず作らなくてはならない。
そのため、起こさなければならない反応が一意に定まる。
したがって、貪欲に起こすべき反応を探していけばよい。

必要な物質の合計が50個を超えたら、その時点でXを作れないことは確定するので、シミュレーションを打ち切ってよい。

ソースコード

class QuantumAlchemy {
  public:
  int minSteps(string initial, vector <string> reactions) {
		
		vi v(26), init(26);
		v['X' - 'A']++;
		rep(i, initial.size()) init[initial[i] - 'A']++;
		
		vector<vi> reac(26);
		rep(i, reactions.size()){
			int p = reactions[i].find("-");
			string s = reactions[i].substr(0, p);
			string t = reactions[i].substr(p + 2);
			
			vi tmp(26);
			rep(j, s.size()) tmp[s[j] - 'A']++;
			reac[t[0] - 'A'] = tmp;
		}
		
		int ans = 0, sz = 1;
		while(1){
			bool update = 0;
			rep(i, 26) if(v[i] > init[i]){
				if(reac[i].empty()) return -1;
				v[i]--;
				sz--;
				rep(j, 26) v[j] += reac[i][j], sz += reac[i][j];
				update = 1;
				break;
			}
			if(!update) break;
			if(sz > 50) return -1;
			ans++;
		}
		return ans;
  }
};