TCO Round1B 1000 EllysReversals

2013-03-02

05:12 |

あとで

最大50文字の文字列が最大50個ある。どれかの文字列の先頭の偶数文字を逆順にする作業を 0 回以上行う。
同じ文字列が２つ出てきたらそれらは消される。最後に残る文字列の最小個数を求める問題。

先頭から２文字ずつのグループに分けると、グループ内の順序とグループの順序は任意に動かせる
（任意のグループを先頭に持ってきたり元の位置に戻したりできるので）
ので、ある文字列について何回か作業したときにできる文字列の代表を求める（辞書順最小のものとか）
各文字列の代表の個数が奇数個のものだけ 1 個ずつ残るのでその和が答え。

↓あとで(accepted in practice room)

class EllysReversals {
	public:
	int getMin(vector <string> W) {
		int N=W.size();
		map<string, int> hi;
		REP(i, N) {
			vector<string> ww;
			REP(j, W[i].size()/2*2) {
				string ss;
				ss.PB(W[i][j]);
				ss.PB(W[i][j+1]);
				j++;
				sort(ALL(ss));
				ww.PB(ss);
			}
			sort(ALL(ww));
			string sn;
			FOR(e, ww) sn+=*e;
			if(W[i].size() & 1) sn+=W[i][W[i].size()-1];
			hi[sn]++;
		}
		cout<<hi<<endl;
		int ans = 0;
		FOR(e, hi) if(e->second & 1) ans++;
		return ans;
	}
};