SRM502 Div1 Easy - TheLotteryBothDivs

問題

[000000000,999999999]の10^9個の数字のうちどれか1つが書いてある宝くじを1枚適当に買う
与えられるvectorのうち1個以上のstringが買った番号のsuffixになっていれば当選する
当選する確率を求める

解法

例えば"1234" と "34"が与えられたら後者が前者を包含してるから前者は必要ない
こういうのを全部消しちゃえば全部独立に扱えるようになるからあとは10^(-s.size())を足し合わせるだけ

あと最近学んだんだけど○○.size()はunsignedだからキャストせずに引き算したりマイナスをかけるとすぐバグる
最後の-(int)i.size()もキャストしないとヤバイことになるから注意

class TheLotteryBothDivs {
	public:
	double find(vector<string> s) {
		int n = s.size();
		rep(i,n) rep(j,n) if (i!=j && s[i].size()<=s[j].size() && s[j].substr(s[j].size()-s[i].size(),s[i].size())==s[i]) {
			s.erase(s.begin()+j);
			if (j<i) i--;
			j--, n--;
		}
		double res = 0;
		each(i,s) res += pow(10,-(int)i.size());
		return res;
	}
};