SRM502 Div1 Easy - TheLotteryBothDivs
問題
[000000000,999999999]の10^9個の数字のうちどれか1つが書いてある宝くじを1枚適当に買う
与えられるvector
当選する確率を求める
解法
例えば"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; } };