2013 TCO Round 1B Hard(1000) EllysReversals

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; 
}};