SRM 502 Div2 Medium TheLotteryBothDivs

問題

"000000000"から"999999999"までの1,000,000,000通りの通し番号が付いているくじを一つ引く.通し番号のsuffixがsuffix集合goodSuffixesいずれかに一致するくじの時賞金がもらえるとすると.賞金がもらえる確立を答えよ.

解答

サイズmのsuffix Pに一致するくじを引く確率は1/10^m.2つのsuffix P1 P2が与えられ,一方のsuffixがもう一方のsuffixになっている時,短いsuffixは長いsuffixの通し番号を含むので,当たりを引く確率は1/10^min(|P1|, |P2|).goodSuffixesの内,このような包含関係にある,短いsuffixのものだけ取り出し,それぞれの確立を足しあわせれば良い.

class TheLotteryBothDivs {
public:
  double find(vector <string> goodSuffixes) {
    double res = 0;
    int n = goodSuffixes.size();
    vector<bool> valid(n, true);
    int i,j;
    for(i = 0; i < n; i++)if(valid[i]){
      for(j = 0; j < n; j++) if (i!=j && valid[j]){
          if(goodSuffixes[i].size() <= goodSuffixes[j].size() &&
             goodSuffixes[j].substr(goodSuffixes[j].size()-goodSuffixes[i].size()) == goodSuffixes[i]){
            valid[j] = false;
          }
      }
    }
    for(i = 0; i < n; i++) if (valid[i]){
        // cout << pow(10.0, (double)(goodSuffixes[i].size())) << endl;
      res += 1/pow(10.0, (double)(goodSuffixes[i].size()));
    }
    return res;
  }
};