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

SRM502 Div1 500 TheProgrammingContestDivOne

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

Problem Statement

コーディングフェーズ

何となくだが、問題aとbのどちらを先に解くかの比較としては、

aを先に持ってきた場合の総減点と、bを先に持ってきた場合の総減点を比較すれば良い気がする

何か怪しいがとりあえず書いてみる

サンプル合った

・・・

けどこれは明らかにダメだな

減点が少ないが得点が高く、目一杯時間を使いきらないと解けないような問題が反例になる

解く問題のセットが決まれば、上記の順位付けでとりあえずは書けそうだが・・・

セットを決めようとすると2^50とかになってしまう・・・どうするんだ・・・

・・・

(結構長く悩む)

・・・

よく考えたら、逆に考えれば良いのか

全体の順序を先に決めて、その中でどの要素を使うかを決めても同じ結果になる・・よね・・

ってことは普通に上記順序付けでソートしてDPするだけで良かったりする?

書けた

提出

もう一度見直す

あ、、微妙にDPの更新間違っとる!(泣

どうせ提出時198点とかだし今更再提出しても大して変わらんか・・・

再提出

すぐ出し直したのに150点とか。今更だが再提出の10%ペナルティってどういう意味なんだ


チャレンジフェーズ

これってサンプル相当弱いから、適当なGreedyとかでも通るよなぁ・・

と思いつつ、インターミッションの間にいくつかテストケースを用意する

皆さんの回答見るとちゃんとDPしてるから皆頭いいなーと思った

でもよく見ると最初のソートの仕方が皆けっこう適当だな

maxPointsでソートとか、pointsPerMinuteでソートとか、すぐ反例思いつくような・・不注意だなあ

3つ撃墜(コード読み違えて1回失敗)

ラッキーでした


ソースコード

DPの更新がつぎはぎだらけで汚いです

vector <int> maxp, ppm, rt;
int n;
bool less_p(int a, int b) {
	ll ra=(ll)rt[a]*ppm[a]+(ll)(rt[a]+rt[b])*ppm[b];
	ll rb=(ll)rt[b]*ppm[b]+(ll)(rt[a]+rt[b])*ppm[a];
	return ra<rb;
}

int dp[100010][52];

class TheProgrammingContestDivOne {
public:

	int find(int T, vector <int> maxp_, vector <int> ppm_, vector <int> rt_) {
		int res=0;

		maxp=maxp_; ppm=ppm_; rt=rt_;
		n=maxp.size();
		vector <int> vi(n);
		for(int i=0; i<n; i++) vi[i]=i;

		sort(vi.begin(), vi.end(), less_p);
		memset(dp, 0, sizeof(dp));
		for(int i=0; i<T; i++) {
			for(int j=0; j<n; j++) {
				int nt=i+rt[vi[j]];
				dp[i][j+1]=max(dp[i][j+1], dp[i][j]);
				if(nt>T) continue;
				int inc=0;
				if(maxp[vi[j]]>(ll)nt*ppm[vi[j]]) inc=maxp[vi[j]]-(ll)nt*ppm[vi[j]];
				if(inc>0) dp[nt][j+1]=max(dp[nt][j+1], dp[i][j]+inc);
				res=max(res, dp[nt][j+1]);
			}
		}
		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