SRM diary(Sigmar)

• 250:219.90, 500:150.00(+125), score:494.90, rank:63, rating:2108(+48)
• 500に時間かけすぎた。でも通って良かった。

SRM502 Div1 250 TheLotteryBothDivs

SRM502, Div1 | 22:54 |

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

SRM502, Div1 | 22:54 |

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