WARush

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

SRM625 Div1 Easy "PalindromePermutations"

問題

TopCoder Statistics - Problem Statement

回文は前から読んでも後ろから読んでも同じ並びになる文字列のことをいう。例えば、"a", "abba", "zzz" は回文であり、"ab", "xxxyx" は回文ではない。

文字列Sのアナグラムとは、Sにある文字を任意に並び替えたものである。例えば文字列"haha"でいえば、6つのアナグラム("aahh", "ahah", "ahha", "haah", "haha", "hhaa")がある。

あなたは文字列 wordが与えられる。一様にランダムにアナグラムが1つ選ばれる。選ばれたアナグラムが回文である期待値を返せ。

制約

1 <= wordの長さ <= 50
wordに含まれる文字は'a'-'z'


考えたこと

回文の数 / アナグラムの数が答えとなる。

アナグラムの数は回文の数ともに、wordに含まれる各文字の出現回数を記憶しておいて、場合の数をとれば出せる。ただし、両方とも途方もない大きさ(long longを余裕でオーバーフロー)になってしまう。両方とも場合の数(6C2とか)で出すことになり、掛けたり割ったりするので、そのまま期待値に反映させていくとよい。

ソースコード

class PalindromePermutations {
public:

    double palindromeProbability(string word) {
        int n = word.size();
        int m = n / 2;

        // 各文字の出現回数を取得
        int cnt[26];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) {
            cnt[word[i] - 'a']++;
        }

        // 期待値を算出
        bool find = false;
        double p = 1; // 期待値
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                if (find) {
                    // 出現回数が奇数の文字が2つ以上あれば回文作れない
                    return 0.0; 
                }
                else{
                    find = true;
                }
            }
            else{
                // アナグラムの数を反映
                for (int j = 1; j <= cnt[i]; j++) {
                    p *= j;
                    p /= n;
                    n--;
                }
                // 回文の数を反映
                int t = cnt[i] / 2;
                for (int i = 1; i <= t; i++) {
                    p *= m;
                    p /= i;
                    m--;
                }
            }
        }

        return p;
    }
};