SRM502 Div1 Easy TheLotteryBothDivs

2015/06/21 (Sun) SRM 文字列

問題

問題文

000000000 から 999999999 までの $10^9$ 通りの出方があるくじがある． そのうち prefix が $goodSuffixes$ に含まれるものは当たりである．当たる確率を求めなさい．

方針

長さが違って prefix が被っている $2$ つの文字列があったとき，長い方に当たっていれば短い方に当たっている． なら初めから最も短い方だけに注目する．

実装

class TheLotteryBothDivs {
public:
    double find(vector <string> suf) {
        vector<ll> pow10(13);
        pow10[0] = 1;
        rep(i,12) pow10[i+1] = pow10[i]*10;

        int n = suf.size();
        rep(i,n) reverse(all(suf[i]));
        sort(all(suf));
        rep(i,n){
            int j = i+1;
            while(j < n && contains(suf[j],suf[i])){
                suf[j] = "~";
                j++;
            }
        }
        suf.erase(remove(all(suf),"~"), suf.end());
        n = suf.size();
        ll cnt = 0;
        rep(i,n) cnt += pow10[9-suf[i].size()];
        return 1.* cnt / pow10[9];
    }
    bool contains(string s, string t){
        if(s.size() < t.size()) return false;
        return s.substr(0,t.size()) == t;
    }
};