SRM627 Div1 Easy "HappyLetterDiv1"
問題
TopCoder Statistics - Problem Statement
訳
"The Happy Letter"というゲームは次のようなルールである。まず始めに数人のキャラクターがフィールドにいる。それぞれのキャラクターは小文字のアルファベットとして表示されている。このゲームはターン制であり、それぞれのターンで、あなたは違う小文字を表された2人のキャラクター選び、選ばれたキャラクターはフィールドから離脱する。
ゲームが終了したときに、もしフィールドにキャラクターが残っていた場合、彼らは同じ文字でなければならない。その文字は"winning letter"と呼ばれる。ゲームが終了したときに、フィールドにキャラクターが残っていなければ、"winning letter"は存在しないこととなる。
あなたはString lettersが与えられる。lettersの文字はゲームが始まったときのそれぞれのキャラクターの文字を表している。"winning letter"となる可能性のある全ての文字を文字列として返せ。その文字列は辞書順でなければならない。
制約
1 <= letters.size() <= 50
考えたこと
例えば' a 'を"winning letter"としたいときに、最善の方法は' a '以外の文字を数が多い順に並べて、上から2つ選んでフィールドから除外していけばよさそう。' a 'は最後まで使わないのがよい。
事後
ゲームのルールがいまいちよく分からん・・
ソースコード
class HappyLetterDiv1 { public: string getHappyLetters(string letters) { int count[30]; memset(count, 0, sizeof(count)); int n = letters.size(); for (int i = 0; i < n; i++) { count[letters[i] - 'a']++; } string res = ""; for (int c = 0; c < 26; c++) { if (count[c] == 0) continue; vector<int> v; for (int i = 0; i < 26; i++) { if (i == c ) continue; v.push_back(count[i]); } while (true) { sort(v.begin(), v.end()); reverse(v.begin(), v.end()); if (v[1] == 0) { if (count[c] > v[0]) { res += (char)('a' + c); } break; } v[0]--; v[1]--; } } return res; } };