SRM502 Div1 Easy(250), Div2 Medium(500) TheLotteryBothDivs

TheLotteryBothDivs

a,b∈goodSuffixesについてaがbの接尾辞ならば、bが無くても当たり籤は変わらない。例えばサンプル3ならば4747は要らない。goodSuffixesから他の要素が接尾辞になっているような要素を除いた集合Sを考える。当たり籤はちょうど1個のSの要素を接尾辞に持つので、それぞれの要素について当たる確率を求めて足し合わせる。

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

bool cmp( string a, string b ) { return a.length()<b.length(); }

class TheLotteryBothDivs{public:
double find( vector <string> goodSuffixes )
{
    vector<string> G = goodSuffixes;
    vector<string> S;

    sort(G.begin(),G.end(),cmp);

    for ( int i=0; i<(int)G.size(); i++ )
    {
        bool f = true;
        for ( int j=0; j<(int)S.size(); j++ )
            if ( G[i].substr(G[i].length()-S[j].length()) == S[j] )
                f = false;
        if ( f )
            S.push_back(G[i]);
    }

    double ans = 0;
    for ( int i=0; i<(int)S.size(); i++ )
        ans += pow(0.1,(int)S[i].size());
    return ans;
}};