SRM 502 250pt: TheLotteryBothDivs

問題概要

"%09d"で表示されるくじが無作為に1枚選ばれる。長さ9以下の文字列が複数与えられ、どれか一つでも末尾が一致していたら賞金がもらえる。賞金がもらえる確率を求める問題。

解法

与えられた文字列のうち、他の文字列を接尾語に持つものは削除すれば良い。同じ文字列があったとき丁度ひとつだけ残す処理に注意(sortしてuniqueするだけだが)。

感想

あれ、JohnとBrusって飛行機で世界中を飛び回る人気アーティストじゃなかったっけ。Johnは職業変わってるしBrusに至っては人間をやめてる。でもこのクラス名(The...DivOne)とメソッド名(find)はいつもの人なのに、とか思いながら読んでた。実はwriterはりんごさんだったらしい。
接尾語と接頭語を勘違いして、最後のサンプルが合わないことにずっと悩んでいた。何故か同じ間違いをした人が結構居たらしい。
あと、撃墜時にC++で、

for(int i=xs.size()-1; i>=0; --i){
    ...
    xs.erase(x);
}

的なことをしている人が居て、範囲外アクセスでは落ちないだろうけど中の処理でミスるだろうと思って投げたらdefendされた(system testも通ってた)。

class TheLotteryBothDivs {
public:
double find(vector <string> goodSuffixes) {
	set<string> rem;
	vector<string> ws;

	sort(goodSuffixes.begin(), goodSuffixes.end());
	goodSuffixes.erase(unique(goodSuffixes.begin(), goodSuffixes.end()), goodSuffixes.end());
	int N = goodSuffixes.size();

	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++)if(i!=j && goodSuffixes[i].length() >= goodSuffixes[j].length()){
			if(goodSuffixes[i].substr((int)goodSuffixes[i].length() - (int)goodSuffixes[j].length()) == goodSuffixes[j]){
				rem.insert(goodSuffixes[i]);
			}
		}
	}

	for(typeof(rem.begin()) itr = rem.begin(); itr != rem.end(); itr++){
		cout << "--- " << *itr << endl;
	}

	for(int i=0; i<N; i++)if(rem.find(goodSuffixes[i]) == rem.end()){
		ws.push_back(goodSuffixes[i]);
	}
	N = ws.size();
	for(int i=0; i<N; i++)cout << ws[i] << endl;

	int all = 1000000000;
	int cnt = 0;
	for(int i=0; i<N; i++){
		int l = 9 - (int)ws[i].length();
		int t = 1;
		for(int j=0; j<l; j++){
			t *= 10;
		}
		cnt += t;
	}

	return (double)cnt/all;
}