Codeforces #169 Div2 B "Little Girl and Game"
問題
次のようなゲームがある。
2人でプレイし、交互にターンが回ってくる。
文字列Sが与えられている。
ターンが回ってきたら、Sを好きなように並べ替えて、
回文が作れたら勝ち。
回文が作れなければどれか1文字削除する。
文字列Sが与えられた時に、先行と後攻がどちらが勝つかを出力せよ。
制約
1 <= 文字列Sの長さ <= 1000
考えた事
回文って文字が奇数個のものが1つ以下になった時に作れるな~
とにかく紙にパターン書きまくってなんか法則見つけよう
どうやら奇数個のものが全くないか、奇数個あれば先行が勝つ様である。
ソースコード
int main() { string S; cin >> S; int num[26]; memset( num, 0, sizeof(num) ); for( int i = 0; i < S.length(); i++ ){ int n = S[i] - 'a'; num[n]++; } int oddNum = 0; for( int i = 0; i < 26; i++ ){ if( num[i] % 2 == 1 ) oddNum++; } if( oddNum == 0 || oddNum % 2 == 1 ){ cout << "First" << endl; }else{ cout << "Second" << endl; } return 0; }