Qualification Round 2011 B: Magicka
解法
ただのシミュレーション。vectorをstack代わりに使って書いた。
#include <cstdio> #include <vector> #include <string> using namespace std; char table[0x100][0x100]; bool oppos[0x100][0x100]; int main(){ int T; scanf("%d",&T); for(int c=1; c<=T; c++){ //clear tables for(int i='A'; i<='Z'; i++)for(int j='A'; j<='Z'; j++) table[i][j] = '*'; for(int i='A'; i<='Z'; i++)for(int j='A'; j<='Z'; j++) oppos[i][j] = false; //read input int C, D, N; char buf[257]; scanf("%d ",&C); for(int i=0; i<C; i++){ scanf("%s ",buf); char s1 = buf[0], s2 = buf[1], t = buf[2]; table[s1][s2] = table[s2][s1] = t; } scanf("%d ",&D); for(int i=0; i<D; i++){ scanf("%s ",buf); oppos[buf[0]][buf[1]] = oppos[buf[1]][buf[0]] = true; } scanf("%d %s ",&N, buf); //simulation vector<char> st; for(int i=0; i<N; i++){ st.push_back(buf[i]); while((int)st.size() >= 2){ char c1 = st[st.size()-1], c2 = st[st.size()-2]; if(table[c1][c2] != '*'){ char ch = table[c1][c2]; st.pop_back(); st.pop_back(); st.push_back(ch); } else{ break; } } for(int j=0; j<(int)st.size(); j++)for(int k=j+1; k<(int)st.size(); k++){ if(oppos[st[j]][st[k]]){ st.clear(); goto end; } } end:; } //output printf("Case #%d: [",c); string ans = ""; for(int i=0; i<(int)st.size(); i++){ ans += st[i]; ans += ", "; } if(!ans.empty()){ ans = ans.substr(0,(int)ans.length()-2) + "]"; } else{ ans = "]"; } puts(ans.c_str()); } return 0; }