TopCoder SRM 589, Division 1, Level 1 : GooseTattarrattatDiv1

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12730&rd=15701

概要

文字列 S が与えられる。
S に対して次の操作を繰り返し適用し、回文となるようにしたい。

• アルファベットを一つ選び、その文字を全て任意の一文字に置き換える。

操作には、対象となった文字一つにつき 1 の時間がかかる。

S を回分にするために必要な時間の最小値を求めよ。

解法

S の長さを L とします。
S[ i ] == S[ L - 1 - i ] を満たすとき、文字 S[ i ] と S[ L - 1 - i ] は同じ文字に変形される必要があります。
この条件を満たす文字のペアを同じグループとして併合していきます。
併合が全て終わったあと、グループ毎に一つの文字にするためのコストを計算します。
この計算は単純で、グループ内の文字の内、S に現れる回数が最も多いものに変換することで最小時間を達成できます。
各グループのこの値の和が答えです。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class UnionFind; // 中身は省略
// UnionFind( N )
// find( x )
// same( x, y )
// unite( x, y )

class GooseTattarrattatDiv1
{
public:
	int getmin( string S )
	{
		const int L = S.size();

		UnionFind uf( 26 );
		REP( i, 0, L / 2 )
		{
			uf.unite( S[i] - 'a', S[ L - 1 - i ] - 'a' );
		}
		
		int res = 0;
		REP( i, 0, 26 )
		{
			int max_num = 0, total = 0;
			REP( j, 0, 26 )
			{
				if ( uf.find( j ) == i )
				{
					const int cnt = count( ALL( S ), 'a' + j );
					total += cnt;
					max_num = max( max_num, cnt );
				}
			}

			res += total - max_num;
		}

		return res;
	}
};