TopCoder SRM 589 Div1 Easy GooseTattarrattatDiv1

うーん、久々に0完。チャレンジでちょっと稼いだけど雀の涙みたいな順位。
Easyは本番なかなか回答が思い浮かばず時間切れ、Mediumはあっさり解けたと思ったら方針ミス。
あと１分でEasy出せたのに…。
最近SRMは上がり調子だっただけに痛いな。
http://community.topcoder.com/stat?c=problem_statement&pm=12730

問題

ある文字列Sが与えられる。
S中の文字Xを全部文字Yに置換する処理を行うことができる。
この際、Xの数だけコストがかかる。

Sを回文にするのにかかる最終コストを答えよ。

解法

本番全然解法が浮かばず焦った。
数が少ない順に置き換えてもダメだし…。
同じ文字を何度も置き換えるのはコストが上がるし…。

終盤で気づいたのが、

• 回文になるのでS[i]とS[L-1-i]は同じ文字でなければならない。
• 元々同じ文字だったS[i]とS[j]はずっと同じ文字でなければならない。

よって、上記2条件でUnion&Findすると、同じ文字にならなければいけない箇所の集合がわかる。
そのような集合のうち、一番数が多い文字に合わせていけばよい。

class UF {
	public:
	static const int ufmax=502;
	int ufpar[ufmax],ufrank[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y;
		else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

class GooseTattarrattatDiv1 {
	public:
	int mi;
	int N;
	
	int getmin(string S) {
		N=S.size();
		UF uf;
		int i,j;
		uf.init();
		FOR(i,N) FOR(j,N) if(S[i]==S[j]) uf.unite(i,j);
		FOR(i,N) uf.unite(i,N-1-i);
		
		int vis[51];
		int ret=0;
		ZERO(vis);
		FOR(i,N) {
			if(uf.find(i)!=i) continue;
			int tot=0;
			int num[26];
			ZERO(num);
			FOR(j,N) {
				if(uf.find(j)==i) {
					num[S[j]-'a']++;
					tot++;
				}
			}
			int ma=0;
			FOR(j,26) ma=max(ma,num[j]);
			ret += tot-ma;
		}
		
		return ret;
	}
};

まとめ

赤文字でも結構回答遅れてた人いたし、気づかないと気付かない問題…。