概要
文字列 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; }