さっきのが分かればこちらも簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=13918
問題
文字列Sに対し、以下の処理を繰り返し行える。
- 末尾に"A"を加える。
- 全体を前後ひっくり返したのち、末尾に"B"を加える。
入力文字列initialに対し、上記処理を繰り返して文字列targetを作れるか判定せよ。
解法
Div1Easyと同じアプローチで対応できる。
TopCoder SRM 663 Div1 Easy ABBADiv1 - kmjp's blog
こちらは文字列長が長いが、Div1と異なり巻き戻し方が末尾の文字で一意に定まるため、登場する文字列数はO(|target|)となり計算量も収まる。
class ABBA { public: string canObtain(string initial, string target) { set<string> S[1010]; S[target.size()].insert(target); for(int i=target.size();i>initial.size();i--) { FORR(r,S[i]) { if(r[i-1]=='A') S[i-1].insert(r.substr(0,i-1)); if(r[i-1]=='B') { string a=r.substr(0,i-1); reverse(a.begin(),a.end()); S[i-1].insert(a); } } } if(S[initial.size()].count(initial)) return "Possible"; return "Impossible"; } }
まとめ
自分は本番Div2Mediumを解いていたのか…。