TopCoder SRM 663 Div2 Medium ABBA

さっきのが分かればこちらも簡単。
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を解いていたのか…。