Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-04-08SRM502 Div1

SRM502 Div1 250 TheLotteryBothDivs

| 22:54 | SRM502 Div1 250 TheLotteryBothDivs - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM502 Div1 250 TheLotteryBothDivs - SRM diary(Sigmar) SRM502 Div1 250 TheLotteryBothDivs - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

一瞬包除原理かと思ったが全然違った

他の要素がsuffixになっている要素を削除するだけだった

少し時間を使い過ぎたが適当に書いて提出


ソースコード

class TheLotteryBothDivs {
public:
	bool suff(string a, string b) {
		if(b.size()>=a.size()) return false;
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		for(int i=0; i<(int)b.size(); i++) {
			if(a[i]!=b[i]) return false;
		}
		return true;
	}

	double find(vector <string> gs) {
		double res=0;
		sort(gs.begin(), gs.end());
		gs.erase(unique(gs.begin(), gs.end()), gs.end());

		int n=gs.size();
		for(int i=0; i<n; i++) {
			double p=1;
			for(int j=0; j<(int)gs[i].size(); j++) p*=.1;
			res+=p;
			for(int j=0; j<n; j++) {
				if(i==j) continue;
				if(suff(gs[i], gs[j])) {
					res-=p;
					break;
				}
			}
		}

		return res;
	}
};

laycrslaycrs2011/04/08 23:51再提出の10%ペナルティは,再提出するたびに,「最高点の10%」だけ点数がマイナスされます.
500点問題なら,再提出するたびに50点減点され,それが最高点の30%の150点を下回ると,150点になります.

jackperseljackpersel2011/04/09 18:11おお、ありがとうございます。今更ながらルールを理解しました・・・
いつ提出しても10%ペナルティは結構きついんですね。。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110408