SRM 502 div1 easy:TheLotteryBothDivs

SRM 502の練習会に参加しました。結果は全落ちで（◞‸◟）でした。

問題

TopCoder Statistics - Problem Statement

解法

例えば{"74", "4"}というのを考えると,これは"4"の方のみ考えれば良いことがわかる(74と4では1の位が被ってるので)。
よって,goodSuffixesを文字列の長さ順にソートして,一つの文字列を考えるたびに「その文字列の部分文字列がすでに存在しないか」を調べて存在しなければ宝くじに当たる確率として加えていく。

以下ソースコード

bool cmp(const string& lhs, const string& rhs) {
    return lhs.size() < rhs.size();
}

class TheLotteryBothDivs {
public:
    double find(vector <string> goodSuffixes) {
        int n = goodSuffixes.size();
        sort(goodSuffixes.begin(), goodSuffixes.end(), cmp);
        set<string> S;
        double ans = 0;
        for (string s : goodSuffixes) {
            reverse(s.begin(), s.end());
            int p = s.size();
            bool uni = true;
            for (int i = 1; i <= p; i++) {
                if (S.find(s.substr(0, i)) != S.end()) {
                    uni = false;
                    break;
                }
            }
            if (uni) {
                S.insert(s);
                double tmp = 1;
                for (int i = 0; i < p; i++) tmp /= 10;
                ans += tmp;
            }
        }
        return ans;
    }
};

本番では文字列の長さ順にソートするのを忘れてました…
あとTrie木でやっても良さそうなので後でやってみます。