Codeforces #169, B : Little Girl and Game

問題文

http://codeforces.com/contest/276/problem/B

概要

文字列 s を使って次のようなターン制のゲームを二人でプレイする。

• プレイヤーは s から一文字を削除する。
• もし削除する前の段階で、s を並び替えて回文にできるならばそのプレイヤーの勝利とする

文字列 s が与えられるので、勝利するのはどちらか求めよ。

解法

文字列 s を回文にできる条件は、「 s に奇数個含まれる文字の数が一個以下」です。
以下、奇数個含まれる文字の数で状態を識別するとします。
先攻が偶数個含まれる文字を消したときに後攻が同じ文字を消し、先攻が奇数個含まれる文字（一個しかなくてもよい）を消したときに後攻も奇数個含まれる文字を消すとした場合、先攻は状態を変えることができません。
このプロセスを続けていくと、最初の段階で奇数個含まれる文字のみが残ります。
結局、各文字が高々一つ含まれる文字列が残ることになって、この文字列でゲームをした場合の勝敗を求めればよいことになります。
全て偶数個だった場合空文となりますが、空文も回文として扱えば、「最初の文字列に於いて奇数個含まれる文字が奇数個であるか 0 個の場合に先攻が勝つ」と言うことができます。

コード

#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define snd second

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	string s;
	cin >> s;

	map<char,int> count;
	FOR( c, s )
	{
		count[c]++;
	}

	int odds = 0;
	FOR( n, count )
	{
		odds += n.snd % 2;
	}

	cout << ( odds == 0 || odds % 2 ? "First" : "Second" ) << endl;

	return 0;
}