torus711 のアレ

主に競技プログラミングの問題について書きます

2013 TCO Algorithm - Round 1B, Level 3 : EllysReversals

概要

いくつかの文字列が与えられる。
各文字列に対して、先頭から任意の偶数文字を反転させる操作を 0 以上の任意回施すことができる。
操作の結果として、同じ文字列が二つあれば、その対を消去することができる。
最終的に残る文字列の数の最小数を求めよ。

解法

まず、各操作に於ける変化の自由度について考察します。
任意の場所にある文字のペアについて、一度先頭に持ってきてから移動させることで、任意の場所に移動させることができます。
このとき、先頭二文字を反転させる操作を挟むことで、そのペアの順序も任意のものにできます。
また、目的の場所がより後ろのペアから先に操作をすることで、後続の操作で影響を受けないようにできます。
まとめると、各文字のペアについて、任意の場所に任意の順序で格納できる、ということになり、かなり自由度の高い変換ができることがわかります。
なお、文字列長が奇数の場合は、末尾の文字は変化できません。

ところで、ある文字列 S1 に変換できる二つの文字列があったとして、その片方が S2 に変換できるとき、他方も S2 に変換できます。
ということは、各文字列を辞書式順序で最小になるように予め変換しておいて、その結果の個数の奇偶をみればよいことになります。

コード

typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ITER( c ) __typeof( (c).begin() )
#define EACH( it, c ) for ( ITER(c) it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )
#define snd second

struct Odd
{
	bool operator ()( pair<string,int> p )
	{
		return p.snd % 2;
	}
};

class EllysReversals
{
public:
	int getMin( vector <string> words )
	{
		map<string,int> counts;
		EACH( it, words )
		{
			counts[ normalize( *it ) ] ++;
		}
		return count_if( ALL( counts ), Odd() );
	}

	string normalize( string str )
	{
		VS pairs;
		for ( int i = 0; i + 1 < str.size(); i += 2 )
		{
			string tmp( str.substr( i, 2 ) );
			sort( ALL( tmp ) );
			pairs.PB( tmp );
		}
		sort( ALL( pairs ) );
		if ( str.size() % 2 )
		{
			pairs.PB( str.substr( str.size() - 1 ) );
		}
		return accumulate( ALL( pairs ), string() );
	}
};