torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, SRM 627, Division 1, Level 1 : HappyLetterDiv1

問題概要

 英小文字からなる文字列 letters が与えられる。この文字列に対し、異なる二つの文字を選んで取り除く操作を繰り返し適用し、それ以上操作を適用できなくなった時点で終了する。一連の操作終了後、leltters に残っている文字が 1 種類だけならば、その文字を winning letter と呼ぶ。
 与えられた文字列 letters に於いて winning letter となり得る文字を全て求めよ。

解法

 文字列長を L と書きます。
 解の性質より、ある文字 c を仮定したときに、c が winning letter になり得るか否かを判定できる必要があります。つまり、ある文字 c について、c を 1 つ以上残して操作を終了することができるか否かを判定できなければなりません。この判定ができれば、適当に列挙することで答えが得られます。
 では、ある文字 c を 1 つ以上残して操作を終了する方法ついて考えます。やらなければならないことは c 以外の文字を全て消し去ることです。明らかに、c 以外の文字と c は組み合わせて消去することが可能なので、c 以外の文字同士をを組み合わせて c 以外の文字の数を c の個数未満にできれば、c を 1 つ以上残して操作を完了できます。従って、できるだけ c を使わずに消去した方が得になります。更に、最適な消し方をしたときに、個数最大のものの個数が最小化されると考えると(あるいは直感から)、c 以外の文字の内、数の多いもの 2 種類を優先的に組み合わせた方が得となります。c 以外の文字に関して最適な消し方をしたとき、残った文字の数が c の数未満になれば、c は winning letter になり得ます。また、個数最大のものから消す手順は、優先順位付きキューを用いることで比較敵楽にシミュレートできます。

コード

using VI = vector<int>;

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

class HappyLetterDiv1
{
public:
	string getHappyLetters( string letters )
	{
		const int L = letters.size();

		VI counts( 26 );
		FOR( c, letters )
		{
			counts[ c - 'a' ]++;
		}

		string res;
		for ( char c = 'a'; c <= 'z'; c++ )
		{
			const int t = counts[ c - 'a' ];

			counts[ c - 'a' ] = 0;
			priority_queue<int> que( ALL( counts ) );
			counts[ c - 'a' ] = t;


			while ( 2 <= que.size() )
			{
				const int a = que.top();
				que.pop();
				const int b = que.top();
				que.pop();

				if ( b <= 0 )
				{
					que.push( a );
					que.push( b );
					break;
				}

				que.push( a - 1 );
				que.push( b - 1 );
			}

			int rest = 0;
			while ( !que.empty() && 0 <= que.top() )
			{
				rest += que.top();
				que.pop();
			}

			if ( rest < t )
			{
				res += c;
			}

		}

		return res;
	}
};