kmjp's blog

競技プログラミング参加記です

TopCoder SRM 663 Div1 Easy ABBADiv1

問題文見間違えてEasy落とした…。
http://community.topcoder.com/stat?c=problem_statement&pm=13922

問題

文字列Sに対し、以下の処理を繰り返し行える。

  • 末尾に"A"を加える。
  • 末尾に"B"を加えたのち、全体を前後ひっくり返す。

入力文字列initialに対し、上記処理を繰り返して文字列targetを作れるか判定せよ。

解法

initialから生成しようとすると、1手毎に2通りの手段があって状態数が膨れ上がる。
ここは逆にtargetから戻せる文字列を列挙しよう。

targetから戻せる文字列は、targetの部分集合またはそれを反転させたものなので、O(|target|^2)通り程度しかない。

class ABBADiv1 {
	public:
	string canObtain(string initial, string target) {
		set<string> S[51];
		
		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[0]=='B') {
					string a=r.substr(1);
					reverse(a.begin(),a.end());
					S[i-1].insert(a);
				}
			}
		}
		if(S[initial.size()].count(initial)) return "Possible";
		return "Impossible";
		
	}
}

まとめ

何を勘違いしたか、「先頭に"A"を加える」としてしまい本番落とした。
せっかくMediumを解けたのに、おかげでレート減。