SRM502 Div1 Easy(250), Div2 Medium(500) 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; }};