SRM 502 div1 easy:TheLotteryBothDivs (Trie木でやってみた)

この記事↓mayokoex.hatenablog.com
で言ったとおりTrie木でもやってみました。

最初に宝くじに当たりがつくところにflagを立てながらTrie木を構成していきます。

その後に,dfsでflagが立てたノードに来たらすぐさま当たる確率を返すことで余計な確率の足し算をすることを防ぎます。図にするとこんな感じですね。

以下ソースコード

struct Trie {
    bool ok;
    Trie* next[10];
    Trie() : ok(false) {for (int i = 0; i < 10; i++) next[i] = (Trie*)0;}
};

double dfs(Trie* now, int depth) {
    if (now->ok) return pow(0.1, depth);
    double ret = 0;
    for (int i = 0; i < 10; i++) {
        if (now->next[i] == NULL) continue;
        ret += dfs(now->next[i], depth+1);
    }
    return ret;
}

class TheLotteryBothDivs {
public:
    double find(vector <string> goodSuffixes) {
        Trie* root = new Trie();
        for (string s : goodSuffixes) {
            reverse(s.begin(), s.end());
            Trie* now = root;
            int n = s.size();
            for (int i = 0; i < n; i++) {
                int a = s[i]-'0';
                if (now->next[a] == NULL) {
                    now->next[a] = new Trie();
                }
                now = now->next[a];
            }
            now->ok = true;
        }
        return dfs(root, 0);
    }
};