TopCoderOpen 2013 Round1B Hard EllysReversals

さてHard。
自力では解けなかったけど、他人の回答を見て理解したので再度自分でコードを組んでみた。
http://community.topcoder.com/stat?c=problem_statement&pm=12393

問題

与えられた文字列に対し、偶数の長さを選んでその長さ分のprefixの順番を反転する、という処理を任意回数行えるとする。
複数の文字列が与えられたとき、そのうちある文字列を上記手順で変形させて他の文字列に変換できる場合、元の文字列と変換先文字列を削除する。
最終的に残る文字列の数を答える。

解答

各文字列を、上記変形手順でできる辞書順で最も前にくる文字列に変形してしまう。
変形後に同じ文字列のペアがあったらそれを取り除けばよい。

さて、上記手順でできる変形だが、文字を２文字ずつ区切ったとき、その２文字は順番を入れ替えることができるが２文字を切り離すことはできない。
なぜなら、prefixの反転は常に偶数長で行われるためである。
一方、２文字ずつ区切ったペア同士は互いに任意の位置に持って行ける。

一番後ろに持っていきたいペアが真ん中にある場合、まず先頭からそのペアまでを反転してそのペアを先頭に持ってきて、今度は一番後ろまでを反転すれば、そのペアは一番後ろにくる。
後は同様に２番目、３番目…と処理できるためである。

よって、元の文字列を２文字ずつ区切り、その２文字を辞書順で並べ変えたのち、区切った２文字の文字列同士をソートすればよい。

class EllysReversals {
	public:
	vector<string> W;
	
	string conv(string s) {
		int i;
		vector<string> ss;
		char str[100];
		
		strcpy(str,s.c_str());
		
		FOR(i,s.size()/2) {
			if(str[i*2]>str[i*2+1]) swap(str[i*2],str[i*2+1]);
			ss.push_back(string(str,i*2,2));
		}
		sort(ss.begin(),ss.end());
		
		string ret;
		FOR(i,ss.size()) ret +=ss[i];
		if(s.size()%2==1) ret += s[s.size()-1];
		return ret;
		
	}
	
	int getMin(vector <string> words) {
		int vis[100];
		W=words;
		int i,j,num=0;
		
		set<string> s;
		
		FOR(i,W.size()) {
			string ex=conv(W[i]);
			if(s.find(ex)==s.end()) s.insert(ex);
			else s.erase(ex);
		}
		return s.size();
	}
};

まとめ

気づいてしまえば割と簡単。
これもDiv2 Hard位の問題かもな…。