SRM 344 Div1 Medium QuantumAlchemy
問題
'A'から'Z'までの26種類の物質が存在しており、あなたが持っている物質は文字列initialで表されている。また、いくつかの物質を1つずつ組合わせて別の物質を1つ錬金することができ、これらの組合せがreactionsに記述されている。持ち合わせている物質から物質'X'を作るのに必要な錬金の最小回数を求めよ。不可能なら-1を返せ。
注意点
・ある一回の錬金の材料として、同じ物質を2個以上使用することはない
・ある物質を錬金して作る方法は1パターンしかない
・ある物質iを作るための材料として物質iを使用するパターンはない
やりかた
物質'A'-'Z'を1つのノードに見立てると錬金はグラフと見ることができる。そこで錬成パターンからグラフの接続関係がわかる。そこでゴール地点'X'から出発する深さ優先探索を行う。
今訪れたノードが、所有している物質の中にあり、かつその物質の数がまだあるようなら、その物質の所有数をひとつ減らし、そのノードでは探索を打ち切る。そして今訪れたノードを所有していない、もしくは所有していたがすでに使っており数がない場合には、その物質(ノード)を別の物質から生成する必要があるので、生成回数を+1して、そのノードから別のノードに移動できるかを調べる。移動できるようなら探索を継続し、移動できないようならXを生成するのは不可能ということになる。
錬成パターンがループしている場合、場合によっては無限に物質が必要ということになってしまうが、所有している物質が50以下という制約から、それ以上物質を必要とする探索になったら生成不可能として探索を打ち切ればいい。
以下ソース。
class QuantumAlchemy { public: int ans = 0; bool re[26][26]; map<int, int> num; void rec(int cur){ if(num.count(cur) && num[cur] >= 1) {//この物質は手持ちの物質からまかなえる num[cur]--; return; } if(ans > 100){//パターンがループしてて、手持ちの物質では作れない ans = INF; return; } //この物質は錬金で作るしかない ans++; bool found = false; for(int i = 0; i < 26; i++){ if(re[cur][i]){ found = true; rec(i); } } if(!found) ans = INF;//錬金でつくれなかった return; } int minSteps(string initial, vector <string> reactions){ if(count(ALL(initial), 'X')) return 0; memset(re, false, sizeof(re)); num.clear(); int N = reactions.size(); //グラフの接続を調べる for(int i = 0; i < N; i++){ int c = reactions[i][reactions[i].length() - 1] - 'A'; string ing = reactions[i].substr(0, reactions[i].length() - 3); for(int j = 0; j < (int)ing.length(); j++) re[c][ing[j] - 'A'] = true; } for(int i = 0; i < (int)initial.length(); i++) num[initial[i] - 'A']++; ans = 0; rec('X' - 'A'); return ans >= INF / 2 ? -1 : ans; }
後日短く書いたもの
class QuantumAlchemy { public: int cnt[30]; int ans; map<char, string> pat; void rec(char c){ if(ans >= 200) return; ans++; string s = pat[c]; for(int i = 0; i < (int)s.length(); i++){ if(cnt[s[i] - 'A'] > 0) cnt[s[i] - 'A']--; else if(pat.find(s[i]) != pat.end()) rec(s[i]); else ans += 200; } return; } int minSteps(string initial, vector <string> reactions){ fill(cnt, cnt + 30, 0); pat.clear(); int L = initial.length(); for(int i = 0; i < L; i++) cnt[initial[i] - 'A']++; for(int i = 0; i < (int)reactions.size(); i++) pat[reactions[i].back()] = reactions[i].substr(0, reactions[i].find('-')); ans = 0; if(count(ALL(initial), 'X') > 0) return 0; if(pat.find('X') == pat.end()) return -1; rec('X'); return ans >= 200 ? -1 : ans; } };