blue_jamのTopCoder日記

SRM502 Div1 Easy

SRM, Practice | 01:05

思い出したかのように鍛錬

概要

9桁の宝くじの当選番号が与えられるので，1枚の宝くじが当選する確率を求める．

解法

早解きゲー

1. 与えられた当選番号のうち，完全に一致する文字列を削除（C++ならsort->unique)
2. 与えられた当選番号に他の当選番号が含まれていないか確かめる．
   • 含まれる当選番号が存在しないなら，答えに0.1^xを加える．(xは当選番号の長さ）
   • そうでなければ何も加えない．

ソース

class TheLotteryBothDivs {
public:
    double find(vector <string> goodSuffixes) {
        double res;
		res = 0.0;

		sort(goodSuffixes.begin(), goodSuffixes.end());
		vector<string>::iterator it = unique(goodSuffixes.begin(), goodSuffixes.end());
		goodSuffixes.erase(it, goodSuffixes.end());
		int n = goodSuffixes.size();

		for(int i=0;i<n;++i){
			bool contains = false;
			for(int j=0;j<n;++j){
				int li, lj;
				li = goodSuffixes[i].size();
				lj = goodSuffixes[j].size();
				if(i!=j && li >= lj){
					int k;
					for(k=0;k<lj;++k){
						if(goodSuffixes[i][li-k-1] != goodSuffixes[j][lj-k-1]){
							break;
						}
					}
					if(k == lj){
						contains = true;
					}
				}
			}
			if(!contains){
				res = res + pow(0.1, (double)goodSuffixes[i].size());
			}
		}
        return res;
    }

};

最近プログラミングやってなさ過ぎてやばい．