2013 TCO Round 1B Hard(1000) EllysReversals
許されている操作で何ができるかを考える。文字列の長さが奇数ならば最後の1文字を動かすことはできない。先頭から2文字1組に分けたときに、その2文字をバラすことはできない。先頭を経由すると、この組は自由な場所に動かすことはできるし、2文字を交換することもできる。全ての文字列を、このような操作で作れる辞書順最小の文字列にして数えて、個数が奇数のものを足し合わせれば良い。
#include <string> #include <vector> #include <algorithm> #include <map> #include <numeric> using namespace std; string normalize( string w ) { int n = (int)w.length(); vector<string> T; for ( int i=0; i<n/2; i++ ) { string t = w.substr(i*2,2); sort(t.begin(),t.end()); T.push_back(t); } sort(T.begin(),T.end()); return accumulate(T.begin(),T.end(),string()) + w.substr(n/2*2); } class EllysReversals{public: int getMin( vector <string> words ) { int n = (int)words.size(); map<string,int> M; for ( int i=0; i<n; i++ ) M[normalize(words[i])]++; int ans = 0; for ( map<string,int>::iterator it=M.begin(); it!=M.end(); it++ ) ans += it->second%2; return ans; }};