torus711 のアレ

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

TopCoder, SRM 627, Division 2, Level 2 : HappyLetterDiv2

問題概要

 英小文字からなる文字列 letters が与えられる。この文字列に対し、異なる二つの文字を選んで取り除く操作を繰り返し適用し、それ以上操作を適用できなくなった時点で終了する。一連の操作の完了後、letters に残っている文字が 1 種類だけならば、その文字を winning letter と呼ぶ。ある letters に対し、どのような順序で操作を適用しても winning letter が 1 通りに定まるとき、その winning letter を happy letter と呼ぶ。
 与えられた文字列 letters に於ける happy letter を求めよ。存在しない場合は '.' で示せ。

解法

 文字列長を L と書きます。
 ある文字 c を仮定したときに c が happy letter か否かを求めることができれば、c を全通り試すことで答えを得られます。文字 c が happy letter か否かを判定するために、文字列中に文字が出現する回数に着目します。c の出現回数が、その他の文字の出現回数の総和以下のとき、c を全て消し去ることができるので c は happy letter ではありません。そうでないとき、どのような順序で操作しても c が 1 つ以上残るので、c は happy letter であると言えます。従って、c の出現回数を f_c とすれば、c が happy letter である必要十分条件\frac{L}{2} < f_c と書けます。なお、複数の文字が同時にこの条件を満たすことはありません。従って、c と置く文字を全通り試して、条件を満たすものを発見したらそのときの c を return することで happy letter を調べられます。そのような文字が存在しない場合は '.' を return します。

コード

#define ALL( c ) (c).begin(), (c).end()

class HappyLetterDiv2
{
public:
	char getHappyLetter( string letters )
	{
		const int L = letters.size();
		for ( char c = 'a'; c <= 'z'; c++ )
		{
			if ( L / 2 < count( ALL( letters ), c ) )
			{
				return c;
			}
		}
		return '.';
	}
};