WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};