Hatena::Grouptopcoder

blue_jamのTopCoder日記

 | 

2011-08-29

SRM502 Div1 Easy

| 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;
    }

};

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

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/blue_jam/20110829
 |