SRM 627 Div1 Easy, HappyLetterDiv1

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13274

[a-z] のみからなる文字列 L (1 <= |L| <= 50) が与えられる. 一度の操作で, 文字列中の任意の異なる文字ペアを消去する (例えば "aabbc" -> "aab"). この操作を繰り返して, 最後に残ったアルファベットを winning letter と呼ぶ. winning letter になりうるアルファベットを全て求めよ.

解法

あるアルファベット c について, c が winning letter になりうる条件は次の通り.
c 以外の文字に対して操作を繰り返して, 「c の個数 > c 以外の文字の個数」にすることができる

c 以外の文字をうまく減らす戦略を考える. c を除いて最も個数が多い 2 文字を消していく戦略が考えられる. これを実装する.
最適性の証明が出来なくて苦しかったけど, AC だった.

解答

class HappyLetterDiv1
{
public:
    string getHappyLetters (string letters)
    {
        int chars[26] = {};
        for (char c : letters) chars[c-'a']++;
        string ans = "";
        loop (26, i) {
            int cs[26] = {};
            loop (26, j) if (j != i) cs[j] = chars[j];

            while (1) {
                sort(cs, cs+26);
                if (cs[24] == 0) {
                    if (cs[25] < chars[i]) ans += i + 'a';
                    break;
                }
                cs[24]--;
                cs[25]--;
            }
        }
        return ans;
    }
};