TopCoder Open 2013 Round1B Hard EllysReversals

問題

文字列の集合がある。
この中の一つの文字列を取り（これをSとする）
Sの先頭2*i(2*i≦|S|)文字を逆順にする操作を好きなだけ行うことができる。

操作を行った後で、二つの文字列が一致したら、
その文字列を消去することができる。
残る文字列の数の最小値を求めよ。

制約条件

文字列の個数≦50
Sの文字数≦50

方針

2文字単位でなら好きなように並べ替えることができる。
また、2文字単位の中でも、2文字の順序は好きに決めることができる。
他の自由度はない。
したがって、2文字ずつ区切ってソートして、比較すればよい。

2文字単位でなら好きに並べられることの証明は帰納法でやればいい。
2*i文字がOKのとき、2*i+2文字は、
その中で末尾に持っていきたいものをまず先頭にもっていって、
そこから最後まで持っていけばOK。
先頭に来たときに2文字が逆順になっていたら、2文字だけリバースすれば2文字を逆にできる。

ソースコード

class EllysReversals {
	public:
	int getMin(vector <string> words) {
		map<string, int> s;
		rep(i, words.size()){
			vector<string> t;
			for(int j = 0; j < (words[i].size() & ~1); j += 2){
				string a;
				a += words[i][j];
				a += words[i][j + 1];
				sort(all(a));
				t.pb(a);
			}
			sort(all(t));
			string a;
			rep(j, t.size()) a += t[j];
			if(words[i].size() % 2) a += words[i][words[i].size() - 1];
			s[a]++;
		}
		int ans = 0;
		each(i, s) ans += i->second % 2;
		return ans;
	}
};