概要
いくつかの文字列が与えられる。
各文字列に対して、先頭から任意の偶数文字を反転させる操作を 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() ); } };
