Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-01Google Code Jam Japan 2011 予選

  • A-small/A-Large/B-small(1WA)/B-Large/C-small/C-Large:Passed, score:54, penalty(time):1:53:00, rank:31
  • 真面目に頑張った割にはBのデバッグで余りにも時間を使ってしまっていまいちな結果だった

Google Code Jam Japan 2011 予選 A カードシャッフル

| 20:14 | 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

解答方針

シミュレーション

正順でやるとLargeで時間に間に合わないため、逆順でシミュレーションする

こういう逆からなら計算量が削減できるというのは慣れていないと分かりにくい気もする

提出時間:Large 14m46s


ソースコード

int solve(int M, int C, int W, vector <int> &A, vector <int> &B) {
	int res=0;
	W--;
	for(int i=0; i<C; i++) {
		A[i]--;
	}
	
	for(int i=C-1; i>=0; i--) {
		if(W<B[i]) {
			W+=A[i];
		} else if(W-B[i]<A[i]) {
			W-=B[i];
		}
	}

	res=W+1;
	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 M, C, W;
		ifs >> M >> C >> W;
		vector <int> A(C), B(C);
		for(int i=0; i<C; i++) {
			ifs >> A[i] >> B[i];
		}
		int res=solve(M, C, W, A, B);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

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

| 20:14 | 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

まだコーヒーの種類が確定していない日の集合をvector <pair <ll, ll> > empで表す

満足度が高いものから順番に、期限ぎりぎりから消費していく

期限ぎりぎりのコーヒーより満足度の低いコーヒーを使っても、満足度の低いほうのコーヒーが余分に減るだけで、何もいいことがない

ということで以上の方針で問題ない

vector <pair <ll, ll> >で表される期間とか、こういうものの管理はとてつもなく面倒くさい。最悪。

案の定バグりまくり。

一通り直してサンプル合った。

Small合わない。

気分転換にCを解くことにする。

・・・

Cを解いて戻ってきた。

とりあえず簡単に全探索のコードが書けるので、それでSmallだけ解いてみる。

解けた。提出。Correct。

先ほどのLarge用の回答と答えが違うところを調べる。

余計なbreak文が一つ入っていたことに気づく。修正。Small合った。

Large提出。

提出時間:Large 1h49m00s


ソースコード

Large用

struct cts {
	ll c;
	ll t;
	int s;
	bool operator<(const cts &o) const {
		if(this->s>o.s) return true;
		if(this->s<o.s) return false;
		if(this->t>o.t) return true;
		if(this->t<o.t) return false;
		if(this->c<o.c) return true;
		return false;
	}
};

ll solve(int N, ll K, vector <ll> &c, vector <ll> &t, vector <int> &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 <pair <ll, ll> > emp;
	emp.push_back(make_pair(0, K));

	for(int i=0; i<N; i++) {
		int last=-1;
		for(int j=0; j<(int)emp.size(); j++) {
			if(emp[j].first<vc[i].t) last=j;
		}
		ll cnt=0;
		vector <pair <ll, ll> > nemp;
		for(int j=last; j>=0; j--) {
			ll rlast=min(emp[j].second, vc[i].t);
			ll ncnt=cnt+(rlast-emp[j].first);
			if(ncnt<vc[i].c) {
				cnt=ncnt;
				if(rlast!=emp[j].second) nemp.push_back(make_pair(rlast, emp[j].second));
			} else {
				for(int k=0; k<j; k++) nemp.push_back(emp[k]);
				if(emp[j].first!=rlast-(vc[i].c-cnt)) nemp.push_back(make_pair(emp[j].first, rlast-(vc[i].c-cnt)));
				if(rlast!=emp[j].second) nemp.push_back(make_pair(rlast, emp[j].second));
				cnt=vc[i].c;
				break;
			}
		}
		res+=vc[i].s*cnt;
		for(int j=last+1; j<(int)emp.size(); j++) nemp.push_back(emp[j]);
		sort(nemp.begin(), nemp.end());
		emp=nemp;
	}
	
	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 N;
		ll K;
		ifs >> N >> K;
		vector <ll> c(N), t(N);
		vector <int> s(N);
		for(int i=0; i<N; i++) {
			ifs >> c[i] >> t[i] >> s[i];
		}
		ll res=solve(N, K, c, t, s);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

Google Code Jam Japan 2011 予選 C ビット数

| 20:14 | 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

解答方針

DP

下の桁から順番に、aとbの1,0を決めていく

状態はdp[2][70]で、添字はそれぞれキャリーの有無、桁数を表す

初期状態でdp[0][0]以外は無効な値であることに注意

Nは2進数で最大59桁であるはずだが、念のため61桁まで計算し、最終的にdp[0][61]を解としている

64桁とか計算するとオーバーフローに注意しないといけないので、適度に打ち切る必要がある


ソースコード

int solve(ll N) {
	int res=0;
	
	int dp[2][70];
	memset(dp, -1, sizeof(dp));
	dp[0][0]=0;
	for(int i=0; i<61; i++) {
		if(N&(1LL<<i)) {
			if(dp[0][i]>=0) dp[0][i+1]=max(dp[0][i+1], dp[0][i]+1);
			if(dp[1][i]>=0) dp[0][i+1]=max(dp[0][i+1], dp[1][i]);
			if(dp[1][i]>=0) dp[1][i+1]=max(dp[1][i+1], dp[1][i]+2);
		} else {
			if(dp[0][i]>=0) dp[0][i+1]=max(dp[0][i+1], dp[0][i]);
			if(dp[0][i]>=0) dp[1][i+1]=max(dp[1][i+1], dp[0][i]+2);
			if(dp[1][i]>=0) dp[1][i+1]=max(dp[1][i+1], dp[1][i]+1);
		}
	}

	res=dp[0][61];
	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 N;
		ifs >> N;
		int res=solve(N);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

ゲスト



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