SRM502 Div1 Easy - TheLotteryBothDivs

問題

　000000000から999999999までの数字のうち一つが書いてある宝くじを一つ買う。vector<string>が与えられ、その要素のどれか一つでもsuffixになっていれば当選であるとき、当選する確率を求めよ。

解法

　同じだったり被ったりする要素を上手く弾くだけ。

　vector<string>を文字の長さが小さい順に見ていってsetに詰めながら被りを排除していけばいい。制約が緩いので何をやっても通りそう。

反省

　12分ほどでAC。解法を考えるところではあまり詰まらなかったけど実装の方針があまり良くなかったか。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

class TheLotteryBothDivs {
public:
    double find(vector<string> goodSuffixes) {
        sort(goodSuffixes.begin(), goodSuffixes.end(), [&](string lhs, string rhs) {
            return lhs.size() != rhs.size() ? lhs.size() < rhs.size() : lhs < rhs;
        });
        double ans = 0;
        set<string> used;
        for (auto str : goodSuffixes) {
            bool ok = true;
            for (int i = 0; i < str.size(); i++) {
                auto sub = str.substr(str.size() - i - 1);
                if (used.find(sub) != used.end()) {
                    //中にあったら意味ない
                    ok = false;
                    break;
                }
            }

            if (!ok) {
                continue;
            }

            ans += pow(0.1, str.size());
            used.insert(str);
        }

        return ans;
    }
};