Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-05-06Google Code Jam 2012 Round 1A

Google Code Jam 2012 Round 1A A Password Problem

| 20:30 | Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

最初のi個が連続して正しい確率を求めて、何個バックスペースを使うと最も期待値が小さいか調べて、その最小値を返すだけ

なんだけど、色々こまごました式で混乱してしまって20分くらい使ってしまった

終わっとる・・・


ソースコード

入力のパースは省略

double solve(int A, int B, vector <double> &p) {
	double res=0;
	
	vector <double> pn;
	double cp=1;
	for(int i=0; i<A; i++) {
		cp*=p[i];
		pn.push_back(cp);
	}

	res=B+2;
	for(int i=A; i>0; i--) {
		double curk=(A-i)+(B-i+1)+(1-pn[i-1])*(B+1);
		res=min(res, curk);
	}

	return res;
}

Google Code Jam 2012 Round 1A B Kingdom Rush

| 20:30 | Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) Google Code Jam 2012 Round 1A B Kingdom Rush - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

なぜか1-starクリアの数で二分探索なんじゃないかと思ってしまった

いやいや、そもそも上限1000で二分探索なんか普通いらんし・・・

というか何で二分探索なんだ。どの面を1-starに選ぶか決められないとそんな手法取れないし

逆にそれが決められるなら二分探索いらない気がする


もう一度落ち着いて考える

ある状態で2-starに行ける面があるなら、常に取ってしまっていい

ある状態で1-starしか行けないとき、どの面を選ぶかが問題になる

1-starの必要star数を満たしていないものは当然除外する

1-starの必要star数を満たすものの中で、2-starの必要star数が小さいものを残しておいたほうが、総合的に1-starクリア数を減らせるんじゃないか

これで行けば、Greedyでいいことになる


問題文中のサンプルの進め方と異なるが、本当に正しいか。

(1-starの必要star数,2-starの必要star数)という表現で具体的な例を考える

(0,1)と(0,3)があったとする

  • (0,1)からクリアすると、(0,1),(0,1),(0,3),(0,3)の順で合計4回クリアする必要がある
  • (0,3)からクリアすると、(0,3),(0,1),(0,3)の順で合計3回クリアでいける

どちらの1-starを取っても、2-starの必要star数は変わらないし、もらえるstar数も変わらない

だったら、なるべく早い時点で2-starが取れる可能性のある方を残しておいたほうが得に決まっている

やはり正しそうだな

サンプルはたまたまどちらから進めても同じ結果になる例なだけっぽい


とりあえずできたが無駄に時間がかかった。最悪・・・


ソースコード

入力のパースは省略

Too BadのときはN*2+1を返します

int solve(int N, vector <int> &a, vector <int> &b) {
	int res;
	
	int star=0;
	vector <int> done1(N), done2(N);
	for(int one=0; one<=N; one++) {
		bool cont=true;
		while(cont) {
			cont=false;
			for(int i=0; i<N; i++) {
				if(done2[i]) continue;
				if(star<b[i]) continue;
				done2[i]=1;
				if(done1[i]) star++;
				else star+=2;
				cont=true;
			}
		}
		int maxb=-1, maxbi=-1;
		for(int i=0; i<N; i++) {
			if(done1[i] || done2[i]) continue;
			if(a[i]<=star && b[i]>maxb) {
				maxbi=i;
				maxb=b[i];
			}
		}
		if(maxb==-1) break;
		done1[maxbi]=1;
		star++;
	}

	res=N;
	for(int i=0; i<N; i++) {
		if(!done2[i]) return N*2+1;
		res+=done1[i];
	}

	return res;
}

Google Code Jam 2012 Round 1A C Cruise Control

| 20:30 | Google Code Jam 2012 Round 1A C Cruise Control - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2012 Round 1A C Cruise Control - SRM diary(Sigmar) Google Code Jam 2012 Round 1A C Cruise Control - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

全然解答方針が思い浮かばない、かつBまでで通過した気がしたのでイマイチやる気が出なかった・・・


といいつつ、1時間後くらいに何か二部グラフかどうかの判定をすればいいんじゃないかという気がしたので色々考えてみる

左右のレーンを二部グラフに見立てる

前後5m以内にいる2台を、連結しているノードとみなす

そうすると、このグラフは当然二部グラフでなければならないはずだ

追いつきや抜き去りの発生する全ての時刻で、このような判定をする


何かそれが全てのような気がしてきた

書いた

サンプルの最後が通らない

レーンが固定されているはずの人が、入れ替わったりすることが可能になってしまっている

レーンが固定されているか、入れ替え可能かを判定しつつ二部グラフの判定を行う必要があった


書きなおす

サンプル通った

提出

Wrong Answer


時間切れ

終了


後で

グラフの連結解除をするタイミングが誤っていた

単に抜き去りきっただけで連結を解除してはいけない

その時点で他の人と並走していると、レーンを動かせないので、連結状態が続くとみなさないと状態が崩れる

誰とも並走しなくなった時点で、全ての連結を解除するのが正しい


追いつくタイミングと抜き去るタイミングが混ざっていた

ある時刻tで追いつきと抜き去りの両方が発生する場合、まずは抜き去りだけが完了したとみなして連結の判定をしなければならなかった

追いつきも同時に発生させてしまうと、本来レーン変更が可能なはずなのにできなくなってしまう


他にも細かい間違いがいっぱい

全然だめでした

難しい・・・


ちなみにこの解法は、本質的にはanalysisと同じことをやっています

上位2名の解答を見ましたが、やはり本質的には同様の解法でした

しかし書き方が上手で、うまいこと問題が起きないようにコードが書かれています。短時間ですごい・・・


ソースコード

修正してpractice(Large)に通るバージョン

入力のパースは省略

本体はsolve()です

Possibleのときは1e100を返します

tor <vector <
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120506

2011-10-10Google Code Jam Japan 2011 決勝(復習)

Google Code Jam Japan 2011 決勝 C ワイルドカード

| 13:41 | Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

smallを解いているときに思いついたDPでLargeを解いてみたら普通に解けた

大まかには以下のような感じ


aのai文字目まで、bのbi文字目までそれぞれマッチする文字列表現をdp[ai][bi]とする

ただし、最後に*があると何文字目までマッチというのが分からないので最後に*がないものを扱う

次に、aのai+1文字目以降で適当に部分文字列を取り出す(nab~nae文字目まで取り出したとする)

その文字列をbのbi+1文字目以降で検索し、最初に見つかったものをnbb~nbe文字目までとする

dp[nae][nbe]をdp[ai][bi]+"*"+a.substr(nab, nae-nab)で更新する

bのbi+1文字目以降でその文字列が見つからなかった場合、(必要に応じて)末尾に"*"を追加して解の候補とする

解の候補の数があまり多くならないので現実的な時間で解ける


最初と末尾の"*"ありなし辺りで多少コーナーケースのケアが難しくなるがそれ以外には特に難しい点はない

こんなんで通るんならもっと解かれてても良さそうなもんだが・・・


ソースコード

void updatebest(string &best, int &bestast, string cand, int candast, string &a, int ab, int ae, int asz, bool last) {
	if(ab>0) {cand.push_back('*'); candast++; }
	cand+=a.substr(ab, ae-ab);
	if(last && ae<asz) {cand.push_back('*'); candast++; }
	if(bestast==-1 || best.size()>cand.size() || best.size()==cand.size() && bestast>candast || best.size()==cand.size() && bestast==candast && best>cand) {
		best=cand;
		bestast=candast;
	}
}

string solve(string a, string b) {
	string best=a;
	int bestast=0;
	int asz=a.size(), bsz=b.size();

	string dp[52][52];
	int dpast[52][52];
	memset(dpast, -1, sizeof(dpast));
	dpast[0][0]=0;
	for(int ai=0; ai<asz; ai++) {
		for(int bi=0; bi<=bsz; bi++) {
			if(dpast[ai][bi]==-1) continue;
			for(int nab=ai; nab<asz; nab++) {
				for(int nae=nab+1; nae<=asz; nae++) {
					int nsz=nae-nab;
					if(bi+nsz>bsz) {updatebest(best, bestast, dp[ai][bi], dpast[ai][bi], a, nab, nae, asz, true); continue; }
					int nbi=bi, nei=bsz;
					if(nab==0) nei=nsz;
					if(nae==asz) nbi=max(0, bsz-nsz);
					int nbb;
					for(nbb=nbi; nbb+nsz<=nei; nbb++) if(a.substr(nab, nsz)==b.substr(nbb, nsz)) break;
					if(nbb+nsz>nei) {updatebest(best, bestast, dp[ai][bi], dpast[ai][bi], a, nab, nae, asz, true); continue; }
					int nbe=nbb+nsz;
					updatebest(dp[nae][nbe], dpast[nae][nbe], dp[ai][bi], dpast[ai][bi], a, nab, nae, asz, false);
				}
			}
		}
	}

	return best;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		string a, b;
		ifs >> a >> b;
		string res=solve(a, b);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

Google Code Jam Japan 2011 決勝 D クローゼットルーム

| 23:02 | Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 D クローゼットルーム - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Smallのみ後で解いた

せいぜい8箇所くらいしか置けないし、あまりパターン数がないのでDFSで全探索するだけ


ソースコード

int rec(int d, vector <string> room, int str, int stc) {
	int h=room.size(), w=room[0].size();
	int clr[4][3]={{0,0,1},{0,0,-1},{0,1,0},{0,1,1}}, clc[4][3]={{0,1,0},{0,1,1},{0,0,-1},{0,0,1}};

	int res=0;
	if(d==h*w) {
		int dr[4]={0,0,1,-1}, dc[4]={1,-1,0,0};
		queue <pair <int, int> > q;
		int val[52][52];
		memset(val, -1, sizeof(val));
		q.push(make_pair(str, stc));
		val[str][stc]=0;
		while(!q.empty()) {
			int cr=q.front().first, cc=q.front().second; q.pop();
			res+=room[cr][cc]-'0';
			for(int i=0; i<4; i++) {
				int nr=cr+dr[i], nc=cc+dc[i];
				if(nr<0 || nr>=h || nc<0 || nc>=w) continue;
				if(room[nr][nc]=='X') continue;
				if(val[nr][nc]>=0) continue;
				q.push(make_pair(nr, nc));
				val[nr][nc]=val[cr][cc]+1;
			}
		}
		return res;
	}

	int cr=d/w, cc=d%w;
	for(int i=0; i<4; i++) {
		bool ok=true;
		for(int j=0; j<3; j++) {
			int nr=cr+clr[i][j], nc=cc+clc[i][j];
			if(nr<0 || nr>=h || nc<0 || nc>=w) ok=false;
			else if(room[nr][nc]=='X') ok=false;
			else if(j<2 && nr==str && nc==stc) ok=false;
		}
		if(!ok) continue;
		char save[2];
		for(int j=0; j<2; j++) {
			int nr=cr+clr[i][j], nc=cc+clc[i][j];
			save[j]=room[nr][nc];
			room[nr][nc]='X';
		}
		room[cr+clr[i][2]][cc+clc[i][2]]++;
		res=max(res, rec(d+1, room, str, stc));
		for(int j=0; j<2; j++) {
			int nr=cr+clr[i][j], nc=cc+clc[i][j];
			room[nr][nc]=save[j];
		}
		room[cr+clr[i][2]][cc+clc[i][2]]--;
	}
	res=max(res, rec(d+1, room, str, stc));

	return res;
}

int solve(vector <string> room) {
	int res=0;
	int h=room.size(), w=room[0].size();

	for(int i=0; i<h; i++) replace(room[i].begin(), room[i].end(), '.', '0');
	int str, stc;
	for(int i=0; i<h; i++) for(int j=0; j<w; j++) if(room[i][j]=='D') {
		str=i;
		stc=j;
		room[i][j]='0';
	}

	res=rec(0, room, str, stc);
	
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int H, W;
		ifs >> H >> W;
		vector <string> room(H);
		for(int i=0; i<H; i++) ifs >> room[i];
		int res=solve(room);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111010

2011-10-08Google Code Jam Japan 2011 決勝

Google Code Jam Japan 2011 決勝 B バクテリアの増殖

| 20:56 | Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 B バクテリアの増殖 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

A^A mod Cって普通にbinary methodで計算するだけでは?

全然違った。指数のほうはmod Cではダメらしい。

Aの2乗、3乗、4乗、、、と順番にmod Cで計算してみて、同じものが出てくるまでやってみる

Cが素数のときはC-1回で循環するはずである。Cが素数でないときでも鳩の巣原理でC-1回を超えることはない。

X回で循環したとすると、指数をX減らしても同じ結果になるということだから、指数はmod Xで計算すれば良いのか?

サンプルの最後が合わない。

指数の計算がA^A mod Xとかでやってたけどこれがだめっぽい気がする。指数の計算用の指数も考える必要が・・・?

・・・

1時間半も経った。無邪気にやりすぎた。

Aに浮気。

解いて戻ってきた。


smallなら解けるだろうか?A乗1回するだけなら本当にbinary methodするだけでは?

1WA。違った。A乗を最大2回だった。結局smallの何がLargeより簡単なんだろう。よく分からない。


再びLargeを考える。

指数の計算方法も同じである気がする。Aの2乗、3乗、、、と順番にmod Xで計算すると、どこかで循環する

循環の長さは当然Xより小さいはずだから、これを繰り返していけばいつかXが1になるはずだ

mod 1なら常にAは0になるので、ここで収束する

実装してみる

サンプル合った

WA。原因は想像がついている。

A mod Xを何乗かしたとき、必ずしもAに戻ってくるわけではない。例えばA^5=A^2だがA^4!=A^1みたいなのがあると、指数が2~5の間で循環するわけだから、必ずしも常にmodを取っていいわけではない。

うーーーーーん

時間切れ


以下終了後

実は2~5で循環する場合でも、2以上のXの場合は((X-2)%3+2)乗すれば良いわけだから、結局mod 3で見ればX%3と合同であることは変わらない

ってことは、最大でも1000乗すれば循環が始まっていると見て間違いないのだから、単に1000以上になる場合だけ、modで合同の1000以上の最小値を保持しておけば良いはずだ

書いてみた

small/largeともにPass

コンテスト終了後1時間以上も経っていた

もっと頭の回転早くないと無理だな


ソースコード

ll powgf(ll a, ll e, ll MOD) {
	if(a==0) return a;
	ll res=1;
	ll bias=999/MOD*MOD+MOD;
	for(; e; e>>=1) {
		if(e&1) res*=a;
		if(res>=bias) res=(res-bias)%MOD+bias;
		a=a*a;
		if(a>=bias) a=(a-bias)%MOD+bias;
	}

	return res;
}

int solve(int A, int B, int C) {
	int res=0;

	int cyc[1010];
	int i=C;
	while(i) {
		int x=A%i;
		int memo[1010];
		memset(memo, -1, sizeof(memo));
		memo[x]=0;
		while(memo[x*A%i]<0) {
			memo[x*A%i]=memo[x]+1;
			x=x*A%i;
		}
		cyc[i]=memo[x]+1-memo[x*A%i];
		if(i==cyc[i]) break;
		i=cyc[i];
	}

	int a[1010];
	for(int i=1; i<=C; i++) a[i]=A;
	for(int i=0; i<B; i++) {
		int j=C;
		while(j) {
			a[j]=powgf(a[j], a[cyc[j]]?a[cyc[j]]:cyc[j], j);
			if(j==cyc[j]) break;
			j=cyc[j];
		}
	}
	res=a[C]%C;
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int A, B, C;
		ifs >> A >> B >> C;
		int res=solve(A, B, C);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

Google Code Jam Japan 2011 決勝 A アンテナ修復

| 20:56 | Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Bから浮気してきた

よく分からんけど大きいやつ同士をくっつけたほうが面積大きくなるだろ

Greedyに大きいのをくっつけるコードを書いた。

small通った。

largeも通った。

何かBと比べてえらい簡単だな・・・


ソースコード

double solve(int K, vector <int> &E) {
	double res=0;
	
	sort(E.begin(), E.end(), greater <int>());
	res=(double)E[0]*E[1];
	double e0=E[0], e1=E[1];
	for(int i=2; i<K; i++) {
		res+=e0*E[i];
		e0=e1; e1=E[i];
	}
	res+=e0*e1;
	res*=sin(2*M_PI/K)/2;
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int K;
		ifs >> K;
		vector <int> E(K);
		for(int i=0; i<K; i++) ifs >> E[i];
		double res=solve(K, E);
		ofs << "Case #" << fixed << setprecision(15) << testnum << ": ";
		ofs << res << endl;
	}
}

Google Code Jam Japan 2011 決勝 C ワイルドカード

| 20:56 | Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 C ワイルドカード - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

終了後にsmallだけ解いた。

というか基本的に全探索するだけ。こっちのほうがB-smallより簡単な気がする。


ソースコード

string solve(string a, string b) {
	int n=a.size();
	
	string best=a;
	int bestast=0;
	for(int mask=1; mask<(1<<n)-1; mask++) {
		string aa;
		int aaast=0;
		for(int i=0; i<n; i++) {
			if(mask&(1<<i)) {
				if(i==0 || aa[aa.size()-1]!=' ') {
					aaast++;
					aa.push_back(' ');
				}
			} else aa.push_back(a[i]);
		}
		vector <string> vs;
		istringstream iss(aa);
		copy(istream_iterator <string>(iss), istream_iterator <string>(), back_inserter(vs));
		for(int i=0; i<(int)aa.size(); i++) if(aa[i]==' ') aa[i]='*';

		bool ok=false;
		if(aa[0]!='*') {
			if(vs[0].size()>b.size() || vs[0]!=b.substr(0, vs[0].size())) ok=true;
		}
		if(aa[aa.size()-1]!='*') {
			if(vs[vs.size()-1].size()>b.size() || vs[vs.size()-1]!=b.substr(b.size()-vs[vs.size()-1].size(), vs[vs.size()-1].size())) ok=true;
		}

		int idx=0;
		for(int i=0; i<(int)b.size() && idx<(int)vs.size(); i++) {
			if(vs[idx].size()>b.size()-i) break;
			if(vs[idx]==b.substr(i, vs[idx].size())) {
				i=i+vs[idx].size()-1;
				idx++;
			}
		}
		if(idx<vs.size() || ok) {
			if(best.size()>aa.size() || best.size()==aa.size() && bestast>aaast || best.size()==aa.size() && bestast==aaast && best>aa) {
				best=aa;
				bestast=aaast;
			}
		}
	}

	return best;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		string a, b;
		ifs >> a >> b;
		string res=solve(a, b);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

NiiqiitoNiiqiito2013/02/17 11:57I hate my life but at least this makes it braeable.

xkhqsmsgifxkhqsmsgif2013/02/19 15:16E9CxwG <a href="http://cdmchajbiebt.com/">cdmchajbiebt</a>

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

2011-10-03Google Code Jam Japan 2011 予選(復習)

Google Code Jam Japan 2011 予選 B 最高のコーヒー

| 00:43 | Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Greedy

K日目から1日目に向かって遡っていく

その時点で最も満足度の高いコーヒーを飲むようにする

これで前のやり方(満足度の高いものから消費する日を決める)より全然楽にコードが書ける


ソースコード

main関数は省略

//コーヒーの各パラメータを構造体にする
//比較関数は期限にしている
struct cts {
	ll c, t, s;
	bool operator<(const cts &o) const {
		if(this->t>o.t) return true;
		return false;
	}
};

//priority_queue用に満足度をキーにする比較関数を作成
struct less2 {
	bool operator()(const cts &a, const cts &b) {
		if(a.s<b.s) return true;
		return false;
	}
};

ll solve(int N, ll K, vector <ll> &c, vector <ll> &t, vector <ll> &s) {
	ll res=0;
	
	vector <cts> vc(N);
	for(int i=0; i<N; i++) {
		vc[i].c=c[i];
		vc[i].t=t[i];
		vc[i].s=s[i];
	}
	sort(vc.begin(), vc.end());

	//各コーヒーの期限をリスト化
	vector <ll> tlist;
	tlist.push_back(0);
	for(int i=0; i<N; i++) tlist.push_back(t[i]);
	sort(tlist.begin(), tlist.end(), greater <ll>());

	//期限の来たものから、priority_queueに突っ込んでいる
	//今使えるコーヒーのうち、満足度の最高のものを使うようにしている
	priority_queue <cts, vector <cts>, less2> pq;
	for(int i=0; i<N; i++) {
		pq.push(vc[i]);
		ll interval=tlist[i]-tlist[i+1];
		while(!pq.empty()) {
			cts qt=pq.top(); pq.pop();
			if(qt.c>interval) {
				res+=qt.s*interval;
				qt.c-=interval;
				pq.push(qt);
				break;
			} else {
				res+=qt.s*qt.c;
				interval-=qt.c;
			}
		}
	}
	
	return res;
}

(10/5追記)

満足度順で取っていく手法でも効率的な方法があるとのことでコメントいただきました。こんなに多くの解き方があるとは、とても実装の練習に良い題材ですね。

tozangezanさんのブログ

tozangezantozangezan2011/10/04 16:12満足度順にとっていくのでも区間を持たないとこれより楽に実装できると思うのですが

SigmarSigmar2011/10/05 20:42コメントありがとうございます。
勝手ながら検索してtozangezanさんのコードを読ませていただきました。
区間を持たないというのは、飲んだ日の分、日数を圧縮するようなイメージで、その区間より後ろにある期限を単純に日数分前に持ってくるという手法ですね。これは思いつきませんでした。紹介の意味でリンクさせていただきます。

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

2011-10-02Google Code Jam Japan 2011 練習問題

Google Code Jam Japan 2011 練習問題 B 数の集合

| 01:46 | Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) Google Code Jam Japan 2011 練習問題 B 数の集合 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

区間篩ぽい問題

エラトステネスの篩で素数を作って

区間篩っぽくUnion-Findで結合していくだけ


ソースコード

//Union-Find Tree
class UFT {
public:
	int size;
	vector <int> dad;
	UFT(int size=0) {
		dad.assign(size, -1);
		this->size=size;
	}
	void assign(int size) {
		dad.assign(size, -1);
		this->size=size;
	}
	int ufind(int x, int y, bool dounion) {
		int t, s, i=x, j=y;
		while(dad[i]>=0) i=dad[i];
		while(dad[j]>=0) j=dad[j];
		t=x;
		while(dad[t]>=0) {s=t; t=dad[t]; dad[s]=i;}
		t=y;
		while(dad[t]>=0) {s=t; t=dad[t]; dad[s]=j;}
		if(dounion && (i!=j)) {
			if(dad[j]<dad[i]) {
				dad[j]+=dad[i]; dad[i]=j;
			} else {
				dad[i]+=dad[j]; dad[j]=i;
			}
		}
		return (i!=j);
	}
	int num_of_trees(void) {
		int res=0;
		for(int i=0; i<size; i++) if(dad[i]<0) res++;
		return res;
	}
	vector <int> size_of_trees(void) {
		vector <int> res;
		for(int i=0; i<size; i++) if(dad[i]<0) res.push_back(-dad[i]);
		return res;
	}
	vector <vector <int> > get_groups(void) {
		vector <vector <int> > res;
		vector <int> mp(size);
		int id=0;
		for(int i=0; i<size; i++) if(dad[i]<0) mp[i]=id++;
		res.resize(id);
		for(int i=0; i<size; i++) {
			int j=i; while(dad[j]>=0) j=dad[j];
			res[mp[j]].push_back(i);
		}
		sort(res.begin(), res.end());
		return res;
	}
	UFT operator=(const UFT & _op) {
		dad=_op.dad;
		size=_op.size;
		return *this;
	}
};

//エラトステネスの篩
vector <int> cpn(int n) {
	vector <int> vn(max(2, n+1), 1);

	vn[0]=vn[1]=0;
	for(int i=2; i*i<=n; i++) {
		if(!vn[i]) continue;
		for(int j=i*i; j<=n; j+=i) vn[j]=0;
	}
	
	return vn;
}

int solve(ll A, ll B, ll P) {
	int res=0;

	int d=B-A;
	vector <int> vpn=cpn(d);
	UFT eq(d+1);
	for(ll i=P; i<(ll)vpn.size(); i++) {
		if(!vpn[i]) continue;
		ll start=A/i*i;
		if(start<A) start+=i;
		for(ll j=start+i; j<=B; j+=i) {
			eq.ufind(start-A, j-A, true);
		}
	}
	res=eq.num_of_trees();
	
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		ll A, B, P;
		ifs >> A >> B >> P;
		int res=solve(A, B, P);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

TommyTommy2013/02/18 19:38A really good answer, full of raitonatliy!

CharlCharl2013/02/18 19:38It's like you're on a misison to save me time and money!

fxtvbyplipfxtvbyplip2013/02/21 14:42YzF6wS <a href="http://wazxjswkbbtm.com/">wazxjswkbbtm</a>

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