Hatena::Grouptopcoder

SRM diary(Sigmar)

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

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

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

2011-06-05Google Code Jam 2011 Round 2

Google Code Jam 2011 Round 2 A Airport Walkways

| 21:25 | Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

歩く速さと走る速さの差は一定なので、歩道が遅いときに走るほど効果が高い

例:歩く速さ2、走る速さ4、歩道Aの速さ2、歩道Bの速さ4とすると、Aで走ると歩きの1.5倍の速さ、Bで走ると歩きの1.333倍の速さになるので、Aで走ったほうが得

ということで、歩道の速さでソートして遅い歩道からGreedyに走るようにすればOK

すぐ解けた

提出時間:Large 18m28s


ソースコード

入出力は省略。

tはdoubleに変換してある。

double solve(int X, int S, int R, double t, int N, vector <int> B, vector <int> E, vector <int> w) {
	double res=0;

	vector <pair <int, int> > wl;
	int nw=X;
	for(int i=0; i<N; i++) {
		wl.push_back(make_pair(w[i], E[i]-B[i]));
		nw-=E[i]-B[i];
	}

	wl.push_back(make_pair(0, nw));
	sort(wl.begin(), wl.end());

	for(int i=0; i<(int)wl.size(); i++) {
		double tt=(double)wl[i].second/(R+wl[i].first);
		if(tt>t) {
			double len=(R+wl[i].first)*t;
			tt=t+(double)(wl[i].second-len)/(S+wl[i].first);
			t=0;
		} else t-=tt;
		res+=tt;
	}
	
	return res;
}

Google Code Jam 2011 Round 2 B Spinning Blade

| 21:25 | Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

よくある普通のDPに見えるのだが何かうまく計算できなくてとりあえずsmallを全探索しようとし始める

サンプル合ったのでsmall提出。WA。おいおい・・・

(Kが偶数のときと奇数のときで重心位置が0.5刻みになるのに1刻みみたいに書いていたのが原因)

・・・

・・・

(すでにコンテスト開始から1時間経過)

よくわからないので再度Largeを真面目に考え始める

やはりDP

モーメントの計算方法Σ(p-c)*mass(p)を変形すると、Σp*mass(p)-c*Σmass(p)

従ってある正方形のp*mass(p)とmass(p)の和を記憶しておけば定数時間でモーメントを計算できる(⇔重心が中心にあるか判定できる)

ある長方形のΣmass(p)を求めるDPは、左上隅(0,0)~右下隅(r-1,c-1)までの長方形の重さをsum[r][c]、位置(r,c)の重さをmass[r][c]とすると、sum[r][c]=sum[r-1][c]+sum[r][c-1]-sum[r-1][c-1]+mass[r-1][c-1]で計算できる

このDPを使って、左上隅(r,c)~右下隅(r+k-1,c+k-1)の正方形の重さを求めるには、sum[r+k][c+k]-sum[r][c+k]-sum[r+k][c]+sum[r][c]を求めれば良い

あとは4隅の重さを引けば求めたいものが求められる

Σp*mass(p)はr成分とc成分に分けるとやはり同様に計算できる

DP部分の計算はO(R*C)

あとは正方形の位置と大きさを定めれば定数時間でモーメントが計算できるので、計算量はO(R*C*min(R,C))≒500^3程度


というDPを書くのにバグりまくってとんでもないことになった

mass[r][c]を事前計算せず混乱してしまったのが大きな過ちだった

提出時間:Large 1h44m41s


ソースコード

変数対応表

Σp*mass(p)→(msumr, msumc)

p*mass(p)→(mwr, mwc)

Σmass(p)→sum

入出力は省略。IMPOSSIBLEのときは-1を返す。

int solve(int R, int C, int D, vector <string> bl) {
	int res=-1;

	ll msumr[510][510];
	ll msumc[510][510];
	ll sum[510][510];
	ll mwr[510][510];
	ll mwc[510][510];
	memset(msumr, 0, sizeof(msumr));
	memset(msumc, 0, sizeof(msumc));
	memset(sum, 0, sizeof(sum));
	memset(mwr, 0, sizeof(mwr));
	memset(mwc, 0, sizeof(mwc));

	for(int r=0; r<R; r++) {
		for(int c=0; c<C; c++) {
			mwr[r][c]=r*(D+bl[r][c]-'0');
			mwc[r][c]=c*(D+bl[r][c]-'0');
		}
	}

	for(int r=1; r<=R; r++) {
		for(int c=1; c<=C; c++) {
			sum[r][c]=sum[r][c-1]+sum[r-1][c]-sum[r-1][c-1]+D+bl[r-1][c-1]-'0';
			msumr[r][c]=msumr[r][c-1]+msumr[r-1][c]-msumr[r-1][c-1]+mwr[r-1][c-1];
			msumc[r][c]=msumc[r][c-1]+msumc[r-1][c]-msumc[r-1][c-1]+mwc[r-1][c-1];
		}
	}

	for(int r=0; r<R; r++) {
		for(int c=0; c<C; c++) {
			for(int k=3; k<=min(R, C); k++) {
				if(r+k>R || c+k>C) break;
				ll sumr=0, sumc=0;
				sumr=msumr[r+k][c+k]-msumr[r+k][c]-msumr[r][c+k]+msumr[r][c]-mwr[r][c]-mwr[r+k-1][c]-mwr[r][c+k-1]-mwr[r+k-1][c+k-1];
				sumr*=2;
				sumr-=(sum[r+k][c+k]-sum[r+k][c]-sum[r][c+k]+sum[r][c]-(D+bl[r][c]-'0')-(D+bl[r+k-1][c]-'0')-(D+bl[r][c+k-1]-'0')-(D+bl[r+k-1][c+k-1]-'0'))*(r*2+k-1);
				sumc=msumc[r+k][c+k]-msumc[r+k][c]-msumc[r][c+k]+msumc[r][c]-mwc[r][c]-mwc[r+k-1][c]-mwc[r][c+k-1]-mwc[r+k-1][c+k-1];
				sumc*=2;
				sumc-=(sum[r+k][c+k]-sum[r+k][c]-sum[r][c+k]+sum[r][c]-(D+bl[r][c]-'0')-(D+bl[r+k-1][c]-'0')-(D+bl[r][c+k-1]-'0')-(D+bl[r+k-1][c+k-1]-'0'))*(c*2+k-1);
				if(sumr==0 && sumc==0) res=max(res, k);
			}
		}
	}

	return res;
}

Google Code Jam 2011 Round 2 C Expensive Dinner

| 21:25 | Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

取り掛かった時点で残り45分

とりあえずウェイターを呼んだ回数=客が注文した回数かと思い20分ほど考えたが全然分からない

よくよくExplanationを読んだところ、全然注文した回数とcallした回数が一致してない

再度問題をよく読むと、客が入ってきた時点で新しいウェイターが呼ばれ、全員満足するまでその人が注文を受け付けるらしい

ということは一人のウェイターが最大何回注文を受け付けるのか、の最小と最大を求めるのか

でも合わない

さらに20分くらい経って、ようやくウェイターが呼ばれるのが客が入ってきたときだけだということに気づいた

この時点で残り5分

とりあえずNから1の順と1からNの順でlcmを取って差分を求めてみた

そもそもlcmがオーバーフローして話にならない

だめだ

終了


後で

そもそも読み違えすぎ。(問題自体も分かりにくいと思うのだが・・)

「新しい客が入店時ウェイターを呼ぶことになる回数を求める」とか書いてほしかった


Aさんが入店したときに、それまでのlcmをLとしてlcm(A, L)!=Lのとき、ウェイターが呼ばれることになる

別の言い方をすると、Aを素因数分解して、Lの素因数分解に含まれないものがあった場合ウェイターが呼ばれる

最終的には、lcm(1~N)がトータルコストになるので、これを素因数分解することが重要

lcm(1~N)を素因数分解して、指数が1のものはその素数をもつ人が入店したときにウェイターが呼ばれ、それ以降呼ばれない

指数が2以上のものは、それまでに指数がnだったとすると、nより大きい指数をもつ人が入店したときにウェイターが呼ばれる

従って指数が1->2->3->...->nの順に呼ぶと最大でn回ウェイターが呼ばれ、逆順だと最小で1回しか呼ばれない

指数が2以上のものを対象に計算するので、√Nまでの素数を全て求め、N以下の最大指数を求めれば、(指数-1の和)+1が答えとなる

(最後の+1は、最初に1の人が入店すると+1されるため)

N==1のときだけ例外で、解は0となる


ソースコード

class GCJ {
	vector <int> vn;
public:
	void cpn(int n) {
		vn.assign(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;
		}
	}

	ll solve(ll N) {
		ll res=0;
		if(N==1) return 0;

		for(ll i=2; i*i<=N; i++) {
			if(!vn[i]) continue;
			ll mul=i*i;
			ll cnt=0;
			while(mul<=N) {
				mul*=i;
				cnt++;
			}
			res+=cnt;
		}
		res++;
		return res;
	}
};

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

	GCJ gcj;
	gcj.cpn(1000010);
	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		ll N;
		ifs >> N;
		ll res=gcj.solve(N);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}

Google Code Jam 2011 Round 2 D A.I. War

| 21:25 | Google Code Jam 2011 Round 2 D A.I. War - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 D A.I. War - SRM diary(Sigmar) Google Code Jam 2011 Round 2 D A.I. War - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

基本的にはBFSで最短路を求める問題

threatenされた星は次の星かその次の星までに再度threatenの対象として現れうるが、それ以降現れることはない

(なぜなら、3つ以上先に同じthreaten対象の星が現れた場合、threaten対象の星を通ったほうが最短路になってしまうから)

従ってとりあえず2つ前の星までのthreaten対象を覚えながらBFSすればそんなに状態は爆発しない


公式の解説では、2つ前の星までのthreaten+conquer数を覚えるDPが載っていた。

確かにconquer数は後で引けばいいので、そのほうが書きやすそう。

DPの方が簡単に書けて効率もよさそうですね。


普通のcore duoノートPCでLargeが2:30くらいです

template <class T> vector <T> strspl(string str, char delim) {
	vector <T> res;
	stringstream ss(str);
	string s;
	while(getline(ss, s, delim)) {
		if(ss.fail()) continue;
		stringstream sst(s);
		T tmp; sst >> tmp;
		if(sst.fail()) continue;
		res.push_back(tmp);
	}
	return res;
}

struct elem {
	int node;
	int dad;
	vector <set <int> > thr;
	int thrnum;
	bool operator <(const elem &o) const {
		if(this->node<o.node) return true;</pp>
		if(this->node>o.node) return false;
		if(this->dad<o.dad) return true;</pp>
		if(this->dad>o.dad) return false;
		if(this->thr<o.thr) return true;</pp>
		if(this->thr>o.thr) return false;
		if(this->thrnum<o.thrnum) return true;</pp>
		return false;
	}
};

pair <int, int> solve(int P, vector <vector <int> > e) {
	int minpla=1000000000, maxthr=0;
	int start=0, goal=1;

	queue <elem> q;
	elem qt, qe;
	qe.node=start; qe.dad=-1; qe.thr.resize(2); qe.thrnum=0;
	q.push(qe);
	int val[420];
	memset(val, -1, sizeof(val));
	val[start]=0;
	set <elem> vis;
	while(!q.empty()) {
		qt=q.front(); q.pop();
		int cur=qt.node;
		set <int> nthr;
		for(int i=0; i<(int)e[cur].size(); i++) {
			int next=e[cur][i];
			if(next!=qt.dad && !qt.thr[0].count(next) && !qt.thr[1].count(next)) nthr.insert(next);
		}
		if(nthr.count(goal)) {
			int tmaxthr=qt.thrnum+qt.thr[0].size()+qt.thr[1].size()+nthr.size();
			if(minpla<val[cur] || minpla==val[cur] && maxthr>=tmaxthr) continue;
			minpla=val[cur];
			maxthr=tmaxthr;
			continue;
		}
		for(int i=0; i<(int)e[cur].size(); i++) {
			int next=e[cur][i];
			if(val[next]>=0 && val[next]<val[cur]+1) continue;</pp>
			qe.node=next;
			qe.dad=cur;
			qe.thr[0]=qt.thr[1];
			qe.thr[1]=nthr;
			qe.thr[1].erase(next);
			qe.thrnum=qt.thrnum+qt.thr[0].size();
			if(vis.count(qe)) continue;
			vis.insert(qe);
			q.push(qe);
			val[next]=val[cur]+1;
		}
	}
	
	return make_pair(minpla, maxthr);
}

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

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int P, W;
		ifs >> P >> W;
		vector <vector <int> > e(P);
		for(int i=0; i<W; i++) {</pp>
			string s;
			ifs >> s;
			vector <int> vi=strspl <int>(s, ',');
			e[vi[0.push_back(vi[1]);
			e[vi[1.push_back(vi[0]);
		}
		pair <int, int> res=solve(P, e);
		ofs << "Case #" << testnum << ": ";
		ofs << res.first << " " << res.second << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110605

2011-05-22Google Code Jam 2011 Round 1A

Google Code Jam 2011 Round 1A A FreeCell Statistics

| 23:13 | Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

サンプルが親切。

PGが0か100のときに、PD!=PGだと矛盾するのでBroken

それ以外の場合は、PGはGの上限がないので任意の値で実現可能

(典型的にはGを100の倍数とすると、G*(PG/100)が必ず整数になるので、G*(PG/100)がN以上となるようにGを適当な100の倍数とすれば必ず実現できることが分かる)

ということで後はN以下のDでD*(PD/100)が整数となるものがあればPossibleということになる

式を変形するとD*(PD/100)=x⇔PD/100=x/D

すなわちPD/100を約分すると最小のDはその分母となる

ユークリッドの互除法を使用して最小のDを求め、N以下となるかどうかを確認すればOK

small通った

Largeダウンロード、一瞬で回答出た

中身を確認すると全てBrokenになっている・・・

問題文の上限を見直すと、10^15と書いてある。オーバーフローしている。不注意だった。

intをlong longに直す。

再度run。今度はPossibleがたくさん出てきたので良さそう

提出

ここまで15分くらい


ソースコード

main関数は省略

solve関数がfalseのときBrokenを出力、trueのときPossibleを出力します

ll gcd(ll a, ll b) {
	while(b) {
		a=a%b;
		swap(a, b);
	}
	return a;
}

bool solve(ll N, ll Pd, ll Pg) {
	if(Pd<100 && Pg==100) return false;
	if(Pd>0 && Pg==0) return false;
	if(Pd==0 || Pd==100) return true;
	ll m=100;
	ll g=gcd(m, Pd);
	if(m/g>N) return false;
	else return true;
}

Google Code Jam 2011 Round 1A B The Killer Word

| 23:13 | Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Seanの戦略が分かりにくい。exampleなかったらかなり理解が大変だったろうな・・

さて方針が思いつかない。

普通にシミュレーションするとLargeでTLEするよなあ

色々考えたが、Seanの戦略はシミュレーションしないとやはり最大失点を求めることが難しいように感じる

よく考えれば、シミュレーションを適当に効率化すればLargeでも間に合いそうな気がする

方針は、、、

  • 同じ長さのwordをグループ化して、各グループ毎にポイントを求める
  • 同じグループの中でも、1文字guessする毎に、開いた文字の位置が全く同じものをグループ化する
  • グループが1つになった時点でそのグループのシミュレーションを終了する

ぐらいのことをやれば良いのでは。

書いた→サンプル合った→提出→WA

なぜだ・・・

分からないので適当に細かいところを直してみるが合計3WA

再度問題文を読みなおす

ポイントが同じ場合はDictionaryで早く現れる順と書いてある

てっきり辞書順かと思っていたが、lexicographically smaller(earlier)とは書いていない

Dictionaryって、引数の名前かよ・・・

直した

通った

年のためsmallの時間を計測

0.08秒くらい。Largeは1000倍くらいのスケールなので大丈夫そう

Largeダウンロード

1分くらいで計算終了

提出

ここまで2時間くらい

最後のWAのデバッグで30分くらい無駄にした。問題文は本当によく読まないと・・・・・・

(問題文があまり良くないような気もするが)


ソースコード

提出時から多少整形しました

//oD:元のD, D:長さで分類したD, Di:長さで分類したDの各要素に対するoDのindex
vector <string> solve(int N, int M, vector <string> oD, vector <string> D[11], vector <int> Di[11], vector <string> L) {
	vector <string> res;

	//Dictionaryの各wordの各文字に対してbitmaskで位置を記憶
	int mask[10010][26];
	memset(mask, 0, sizeof(mask));
	for(int i=0; i<N; i++) {
		for(int j=0; j<(int)oD[i].size(); j++) {
			mask[i][oD[i][j]-'a']|=(1<<j);
		}
	}

	//Lの要素ごとに探索
	for(int li=0; li<M; li++) {
		vector <int> points(N);
		//wordの長さごとにポイントを計上
		for(int i=1; i<=10; i++) {
			if(D[i].empty()) continue;
			if(D[i].size()==1) continue;
			//判別がつかないものを同じgroupの要素(vector)に入れていく
			set <vector <int> > group[2];
			vector <int> vi;
			for(int j=0; j<(int)D[i].size(); j++) vi.push_back(Di[i][j]);
			group[0].insert(vi);
			//Lの1文字毎にgroupを分類する
			for(int j=0; j<(int)L[li].size(); j++) {
				set <vector <int> > &curgroup=group[j%2], &nextgroup=group[(j+1)%2];
				nextgroup.clear();
				if(curgroup.empty()) break;
				//これまでに判別がついてない集合毎に更に現在見ている文字で分類
				for(set <vector <int> >::iterator sti=curgroup.begin(); sti!=curgroup.end(); sti++) {
					vector <int> &curset=*sti;
					if(curset.size()==1) continue;
					map <int, vector <int> > tset;
					bool pointsplus=false;
					//mapとmaskを使って分類をする
					for(int k=0; k<(int)curset.size(); k++) {
						tset[mask[curset[k]][L[li][j]-'a']].push_back(curset[k]);
						if(mask[curset[k]][L[li][j]-'a']==0) points[curset[k]]++;
						else pointsplus=true;
					}
					for(map <int, vector <int> >::iterator mpi=tset.begin(); mpi!=tset.end(); mpi++) {
						if(mpi->second.size()>1) nextgroup.insert(mpi->second);
					}
					//集合の全ての要素が現在見ている文字を含まない場合、ポイントの追加を取り消す
					if(!pointsplus) {
						for(int k=0; k<(int)curset.size(); k++) {
							points[curset[k]]--;
						}
					}
				}
			}
		}
		//最もポイントの大きいものを解とする
		int maxpoints=0, maxi=0;
		for(int i=0; i<N; i++) {
			if(maxpoints<points[i]) {
				maxpoints=points[i];
				maxi=i;
			}
		}
		res.push_back(oD[maxi]);
	}
	
	return res;
}

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

	ifs >> testcase; ifs.ignore();
	for(int i=1; i<=testcase; i++) {
		int N, M;
		ifs >> N >> M;
		ifs.ignore();
		vector <string> oD;
		vector <string> D[11];
		vector <int> Di[11];
		for(int j=0; j<N; j++) {
			string s;
			getline(ifs, s);
			oD.push_back(s);
			D[s.size()].push_back(s);
			Di[s.size()].push_back(j);
		}
		vector <string> L(M);
		for(int j=0; j<M; j++) {
			getline(ifs, L[j]);
		}
		vector <string> w;
		w=solve(N, M, oD, D, Di, L);
		ofs << "Case #" << i << ":";
		for(int j=0; j<M; j++) {
			ofs << " " << w[j];
		}
		ofs << endl;
	}
}

Google Code Jam 2011 Round 1A C Pseudominion

| 23:13 | Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

残り30分弱では解けませんでした

以下は終了後の検討内容


まず、turnボーナスは手に入ったと同時に全部使ってしまったほうが良いのは明らか

turnボーナスが0のものはどう考えれば良いかという問題になるが、ここではcardボーナスの最大値が小さいのが重要なポイント

smallはcardボーナスが最大1なので、smallから考える


cardボーナスが1のものをc1、0のものをc0というグループに分ける

ここでc1及びc0を使用枚数を固定すると、各グループの中ではどんな順番で使ってもscore以外の状態が変わらない

従って、各グループの中ではscoreボーナスが大きい順に使ったほうが良いのだろうということになる

また、c1とc0についてはc1を先に使ったほうが選択肢が広がるため、まずc1をスコアが大きい順に使用し、次にc0をスコアが大きい順に使うという順序になる

あとはc1の使用枚数を全探索すれば、答えが出る。


ということで、Largeも同様にできそうであるが、実はこの考え方だとc2が登場するだけで劇的に難しくなる

ストレートフォワードに考えれば、選択肢を広げるため、c2をスコアが大きい順に使用し、c1を使用し、c0を使用し・・・という順番で良さそうに見えるが、これではWAとなる

以下のようなのが反例

(ここでは前からN枚が手札、後ろのM枚がデッキとする)

N=3, M=3

c={0,1,2,2,0,0}

s={0,6,1,5,0,0}

t={2,0,0,0,0,0}

上記の例で最適なパスは以下の通り

  1. card0使用, card:1,2, score:0, turn:2
  2. card1使用, card:2,3, score:6, turn:1
  3. card3使用, card:2,4,5, score:11, turn:0

c1のcard1より先にc2のcard2を使用すると、スコアは7にしかならない。

これは、c1でゲットしたカード内に手札のc2よりスコアの高いc2が入っていたからである。

なので無条件にc2から進めてもダメである。

ということで、c1とc2の使用タイミングを探索しようとすると、計算量が爆発する

そこで、以下のような条件を利用してDPする

  • c1とc2の使用した枚数が同じであれば、結果的にゲットしたカード(使用したものを含む)は常に同じになる
  • c1とc2の使用した枚数が同じであれば、よりスコアボーナスの大きいものを使用したほうが望ましい

ということでc1とc2の使用枚数を状態とすると、そのときのスコアが高いものだけを使用するDPが利用できる

ただし、例外があるので注意が必要である。

以下のような反例を考える。(これは上記の例のcard4のturnボーナスのみを変更したものである)

N=3, M=3

c={0,1,2,2,0,0}

s={0,6,1,5,0,0}

t={2,0,0,0,2,0}

上記の例で最適なパスは以下の通り

  1. card0使用, card:1,2, score:0, turn:2
  2. card2使用, card:1,3,4, score:1, turn:1
  3. card4使用, card:1,3, score:1, turn:2
  4. card1使用, card:3,5, score:7, turn:1
  5. card3使用, card:5, score:12, turn:0

card0,2,4,1の順で使っても、card0,1,3の順で使っても、c1とc2の使用枚数は同じであるが、0,1,3の順で使用すると残りのturn数が0となってしまい0,2,4,1の順より損である

これは、turnボーナスのカードがturn0のときに使えないという制約のためである。

従って、turnが0となる場合は、そうでない場合と区別して扱う必要がある。

これを踏まえてコーディングすると一応通る。

計算量はn=N+Mとすると、O(n^3log n)くらい?

なお公式の解説にはもっとコーナーケースを考えなくてよさそうなO(n^5)のDPが載ってました


ソースコード

Small専用。比較的簡単。

class GCJ {
public:
	int N, M;
	vector <int> c, s, t;

	//turnボーナスを全て使用する
	int get_turn_bonus(int begin, int end, int &score, int &turn) {
		if(turn<=0) return end;
		int nend=end;
		while(begin<end) {
			for(int card=begin; card<end; card++) {
				if(t[card]>0) {
					turn+=t[card]-1;
					score+=s[card];
					nend+=c[card];
				}
			}
			if(nend>N+M) nend=N+M;
			begin=end;
			end=nend;
		}
		return end;
	}

	//指定した範囲のカードをcardボーナスの値に応じてpriority_queueに振り分ける
	void classify_card(int begin, int end, priority_queue <int> &c0, priority_queue <int> &c1) {
		for(int card=begin; card<end; card++) {
			if(t[card]==0) {
				if(c[card]==0) c0.push(s[card]);
				else if(c[card]==1) c1.push(s[card]);
				else exit(1);
			}
		}
	}

	//残りの手札内でcardボーナス0のものを全て使用した場合のscoreを計算する
	int calc_score(priority_queue <int> c0, int turn) {
		int res=0;
		while(turn>0 && !c0.empty()) {
			res+=c0.top(); c0.pop();
			turn--;
		}
		return res;
	}

	//本体
	int solve(int N, int M, vector <int> c, vector <int> s, vector <int> t) {
		int res=0;
		
		this->N=N; this->M=M;
		this->c=c; this->s=s; this->t=t;
		priority_queue <int> c0, c1;
		int scard=N, sscore=0, sturn=1;
		scard=get_turn_bonus(0, scard, sscore, sturn);
		classify_card(0, scard, c0, c1);

		res=sscore+calc_score(c0, sturn);
		while(!c1.empty() && sturn>0) {
			int score=c1.top(); c1.pop();
			sscore+=score;
			sturn--;
			int nscard=min(scard+1, N+M);
			nscard=get_turn_bonus(scard, nscard, sscore, sturn);
			classify_card(scard, nscard, c0, c1);
			scard=nscard;
			res=max(res, sscore+calc_score(c0, sturn));
		}

		return res;
	}
};

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

	ifs >> testcase; ifs.ignore();
	for(int test=1; test<=testcase; test++) {
		int N;
		ifs >> N;
		vector <int> c(N), s(N), t(N);
		for(int i=0; i<N; i++) {
			ifs >> c[i] >> s[i] >> t[i];
		}
		int M;
		ifs >> M;
		c.resize(N+M); s.resize(N+M); t.resize(N+M);
		for(int i=N; i<N+M; i++) {
			ifs >> c[i] >> s[i] >> t[i];
		}
		ofs << "Case #" << test << ": " << gcj.solve(N, M, c, s, t) << endl;
	}
}

Large用。もちろんSmallも通る。

DP部分は幅優先探索で書いている。

main関数はsmallと一緒なので省略

class GCJ {
public:
	int N, M;
	vector <int> c, s, t;

	//turnボーナスを全て使用する
	int get_turn_bonus(int begin, int end, int &score, int &turn) {
		if(turn<=0) return end;
		int nend=end;
		while(begin<end) {
			for(int card=begin; card<end; card++) {
				if(t[card]>0) {
					turn+=t[card]-1;
					score+=s[card];
					nend+=c[card];
				}
			}
			if(nend>N+M) nend=N+M;
			begin=end;
			end=nend;
		}
		return end;
	}

	//指定した範囲のカードをcardボーナスの値に応じてpriority_queueに振り分ける
	void classify_card(int begin, int end, priority_queue <int> &c0, priority_queue <int> &c1, priority_queue <int> &c2) {
		for(int card=begin; card<end; card++) {
			if(t[card]==0) {
				if(c[card]==0) c0.push(s[card]);
				else if(c[card]==1) c1.push(s[card]);
				else if(c[card]==2) c2.push(s[card]);
				else exit(1);
			}
		}
	}

	//残りの手札内でcardボーナス0のものを全て使用した場合のscoreを計算する
	int calc_score(priority_queue <int> c0, int turn) {
		int res=0;
		while(turn>0 && !c0.empty()) {
			res+=c0.top(); c0.pop();
			turn--;
		}
		return res;
	}

	int solve(int N, int M, vector <int> c, vector <int> s, vector <int> t) {
		int res=0;
		
		this->N=N; this->M=M;
		this->c=c; this->s=s; this->t=t;
		priority_queue <int> c0, c1, c2;
		int scard=N, sscore=0, sturn=1;
		scard=get_turn_bonus(0, scard, sscore, sturn);
		classify_card(0, scard, c0, c1, c2);
		res=sscore+calc_score(c0, sturn);

		//幅優先探索(DP)
		queue <pair <int, int> > cbonus_cands;
		pair <int, int> cur_cbonus=make_pair(0, 0);
		cbonus_cands.push(cur_cbonus);
		int cards[82][82];
		memset(cards, -1, sizeof(cards));
		cards[0][0]=scard;
		int scores[82][82];
		memset(scores, -1, sizeof(scores));
		scores[0][0]=sscore;
		int turns[82][82];
		memset(turns, -1, sizeof(turns));
		turns[0][0]=sturn;
		priority_queue <int> rem_sbonus[82][82][3];
		rem_sbonus[0][0][0]=c0; rem_sbonus[0][0][1]=c1; rem_sbonus[0][0][2]=c2;
		while(!cbonus_cands.empty()) {
			cur_cbonus=cbonus_cands.front(); cbonus_cands.pop();
			int c1used=cur_cbonus.first, c2used=cur_cbonus.second;
			priority_queue <int> *rem=rem_sbonus[c1used][c2used];
			if(rem[1].size()>0) {
				int ncard=cards[c1used][c2used];
				int nscore=scores[c1used][c2used]+rem[1].top();
				int nturn=turns[c1used][c2used]-1;
				priority_queue <int> nrem[3];
				nrem[0]=rem[0]; nrem[1]=rem[1]; nrem[2]=rem[2];
				nrem[1].pop();
				int nncard=min(N+M, ncard+1);
				nncard=get_turn_bonus(ncard, nncard, nscore, nturn);
				classify_card(ncard, nncard, nrem[0], nrem[1], nrem[2]);
				res=max(res, nscore+calc_score(nrem[0], nturn));
				//nturn==0のものはqueueにpushしないようにする
				if(scores[c1used+1][c2used]==-1 && nturn>0) {
					cur_cbonus=make_pair(c1used+1, c2used);
					cbonus_cands.push(cur_cbonus);
				}
				if(nscore>scores[c1used+1][c2used] && nturn>0) {
					cards[c1used+1][c2used]=nncard;
					scores[c1used+1][c2used]=nscore;
					turns[c1used+1][c2used]=nturn;
					rem_sbonus[c1used+1][c2used][0]=nrem[0];
					rem_sbonus[c1used+1][c2used][1]=nrem[1];
					rem_sbonus[c1used+1][c2used][2]=nrem[2];
				}
			}
			if(rem[2].size()>0) {
				int ncard=cards[c1used][c2used];
				int nscore=scores[c1used][c2used]+rem[2].top();
				int nturn=turns[c1used][c2used]-1;
				priority_queue <int> nrem[3];
				nrem[0]=rem[0]; nrem[1]=rem[1]; nrem[2]=rem[2];
				nrem[2].pop();
				int nncard=min(N+M, ncard+2);
				nncard=get_turn_bonus(ncard, nncard, nscore, nturn);
				classify_card(ncard, nncard, nrem[0], nrem[1], nrem[2]);
				res=max(res, nscore+calc_score(nrem[0], nturn));
				//nturn==0のものはqueueにpushしないようにする
				if(scores[c1used][c2used+1]==-1 && nturn>0) {
					cur_cbonus=make_pair(c1used, c2used+1);
					cbonus_cands.push(cur_cbonus);
				}
				if(nscore>scores[c1used][c2used+1] && nturn>0) {
					cards[c1used][c2used+1]=nncard;
					scores[c1used][c2used+1]=nscore;
					turns[c1used][c2used+1]=nturn;
					rem_sbonus[c1used][c2used+1][0]=nrem[0];
					rem_sbonus[c1used][c2used+1][1]=nrem[1];
					rem_sbonus[c1used][c2used+1][2]=nrem[2];
				}
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110522

2011-05-08Google Code Jam 2011 Qual Round

Google Code Jam 2011 Qual Round A Bot Trust

| 13:13 | Google Code Jam 2011 Qual Round A Bot Trust - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round A Bot Trust - SRM diary(Sigmar) Google Code Jam 2011 Qual Round A Bot Trust - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

シミュレーションするだけ

どうもこういうの書くのが遅くて良くない

ソースコード

入出力処理は省略

Rは色、Pはボタン位置を示す

int solve(int N, string R, vector <int> P) {
	int res=0;
	
	int o=1, b=1;
	vector <int> O, B;
	for(int i=0; i<N; i++) {
		if(R[i]=='O') O.push_back(P[i]);
		else B.push_back(P[i]);
	}

	int oi=0, bi=0, i=0;
	while(i<N) {
		res++;
		bool odone=true, bdone=true;
		if(oi<(int)O.size()) {
			if(O[oi]>o) o++;
			else if(O[oi]<o) o--;
			else odone=false;
		}
		if(bi<(int)B.size()) {
			if(B[bi]>b) b++;
			else if(B[bi]<b) b--;
			else bdone=false;
		}
		if(!odone && R[i]=='O' && O[oi]==o) {
			i++; oi++;
		} else if(!bdone && R[i]=='B' && B[bi]==b) {
			i++; bi++;
		}
	}

	return res;
}

Google Code Jam 2011 Qual Round B Magicka

| 13:13 | Google Code Jam 2011 Qual Round B Magicka - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round B Magicka - SRM diary(Sigmar) Google Code Jam 2011 Qual Round B Magicka - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

シミュレーションするだけ

どうもこういうの書くのが遅くて良くない

ソースコード

入出力処理は省略

combはcombine、oposはopposed(oppoにすれば良かった?)、invoはinvokeをそれぞれ示す

string solve(int C, int D, int N, vector <string> comb, vector <string> opos, string invo) {
	string res;
	
	int appear[256];
	memset(appear, 0, sizeof(appear));
	char prev=127;

	for(int i=0; i<N; i++) {
		res.push_back(invo[i]);
		appear[invo[i]]++;
		for(int j=0; j<C; j++) {
			if(prev==comb[j][0] && invo[i]==comb[j][1] || prev==comb[j][1] && invo[i]==comb[j][0]) {
				res.erase(res.size()-2, 2);
				res.push_back(comb[j][2]);
				appear[prev]--;
				appear[invo[i]]--;
				appear[comb[j][2]]++;
				prev=comb[j][2];
				break;
			}
		}
		for(int j=0; j<D; j++) {
			if(appear[opos[j][0]] && appear[opos[j][1]]) {
				res.clear();
				memset(appear, 0, sizeof(appear));
				prev=127;
				break;
			}
		}
		if(res.empty()) prev=127;
		else prev=res[res.size()-1];
	}

	return res;
}

Google Code Jam 2011 Qual Round C Candy Splitting

| 13:14 | Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

パトリックの計算方法はxorに等しい

ある2つの集合に分けたとき、各集合のxorがx1、x2となるとすると、xorの性質よりx1=x2のときx1^x2=0

従ってNOとなる条件は、全てのキャンディをxorして0にならないこと

また、NOとならない場合x1^x2=0となることから、どのような分け方をしてもx1=x2となる

なのでパトリックには一番価値の低いキャンディを1つあげれば良い


ソースコード

入出力処理は省略

NOの場合は-1を返す

int solve(int N, vector <int> C) {
	int res=0;
	
	int cur=0;
	for(int i=0; i<N; i++) cur^=C[i];
	if(cur!=0) return -1;

	sort(C.begin(), C.end(), greater <int>());
	res=accumulate(C.begin(), C.end()-1, 0);
	return res;
}

Google Code Jam 2011 Qual Round D GoroSort

| 13:14 | Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

サンプルを見ると、1,2と3,4でそれぞれ入れ替わっていてグループ化できる

何となく位置が入れ替わっているものをグループ化してそれぞれ入れ替えてやれば良さそうである

その場合、各要素が正しい位置に行く可能性はそれぞれ要素数分の1であるため、大体一回のシャッフルで1個の位置が合うものと想定できる

従って、グループ化したときの要素数がおそらくシャッフル回数の期待値である(ただし要素数1のときを除く)

以上から、グループ化して要素数1個以外の要素数を全て足しあわせたものが解となる


と考えて解答したがAnalysisを見たところ、グループ化しなくても良く、正しい位置にない要素の数が解となるとのこと。

確かに自分の解答と答えは同じになるが、グループ化してシャッフルしなくても良いというのは少し直感的ではなかったのでなかなか面白い。


ソースコード

入出力処理は省略

以下はグループ化した書き方になっています

(Pの要素は元々1baseになっていたので0baseとなるよう全て-1してある)

double solve(int N, vector <int> P) {
	double res=0;
	
	vector <int> used(N);
	for(int i=0; i<N; i++) {
		if(used[i]) continue;
		int cur=P[i];
		int cnt=0;
		while(!used[cur]) {
			used[cur]=1;
			cur=P[cur];
			cnt++;
		}
		if(cnt>1) res+=cnt;
	}
	return res;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110508

2010-06-06Google Code Jam 2010 Round 2

Google Code Jam 2010 Round 2 C Bacteria

| 00:16 | Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) のブックマークコメント

バクテリアの増殖と死滅の過程をシミュレーションします。

上と左の両方にバクテリアがいないと増殖しないので、初期状態の右端バクテリアより右側及び下端バクテリアより下側にバクテリアが増殖することはありません。

ということで、Smallでは100*100の範囲内でバクテリアの増殖・死滅をシミュレーションすればよいです。

15分くらいでしこしこと書きましたが、あまりにもミスが多く、デバッグでさらに15分くらい消耗・・・

ダメすぎたので、間違えたところを書き留めておくことにします。

  • 増殖の条件が、左か上のどちらかにバクテリアがいるだけで増えるようになっていた
  • gridの次の状態をgrid2として記録していたが、繰り返し時にgrid2をgridにコピーし忘れていた
  • 最初のバクテリアの個体数を計算する際に、重複しているところを2重に数えていた(問題文に注意としてわざわざ書いてあるのに・・・)

3個目のミスについては、シミュレーションの終了条件を個体数管理によって実現しようとしましたが、そもそもシミュレーションの過程で必ずグリッド全体をスキャンするので、個体数管理は必要なかった・・・

当たり前の確認をきちんとしていないからこうなるんですかね。。

  • if文はよく内容を確認する
  • 問題文の注意点は実行前に再確認する
  • 不必要に複雑なことをしようとしていないか確認する

提出したソースは以下のとおりです。

typedef long long ll;

class GCJ {
public:
	ll solve(int R, vector <int> X1, vector <int> X2, vector <int> Y1, vector <int> Y2) {
		ll res=0, cnt=0;
		vector <vector <int> > grid(102, vector <int>(102, 0)), grid2;

		for(int i=0; i<R; i++) {
			for(int p=X1[i]; p<=X2[i]; p++) {
				for(int q=Y1[i]; q<=Y2[i]; q++) {
					if(grid[q][p]==0) {
						grid[q][p]=1;
						cnt++;
					}
				}
			}
		}

		while(cnt>0) {
			grid2=grid;
			for(int i=1; i<=100; i++) {
				for(int j=1; j<=100; j++) {
					if(grid[i][j]==1) {
						if(grid[i-1][j]==0 && grid[i][j-1]==0) {
							grid2[i][j]=0;
							cnt--;
						}
					} else {
						if(grid[i-1][j]==1 && grid[i][j-1]==1) {
							grid2[i][j]=1;
							cnt++;
						}
					}
				}
			}
			res++;
			grid=grid2;
		}

		return res;
	}
};

Google Code Jam 2010 Round 2 B World Cup 2010

| 00:16 | Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) のブックマークコメント

みなさんの提出状況を見ると、BのS/Lの提出率が高かったため、Cの終了後Bに取り掛かりました。

この問題については、以下のような仮定をした上で進めます。

  • 各々のチームが勝ち進むかどうか分からないので、すべてのチームが決勝まで進むと仮定する必要があります。
  • 見逃していい数というのは分かりにくいので、決勝までのうち、見なければいけない試合数に変換します。

Smallについては、Greedyな戦略で解けそうでした。

チーム0から順に、決勝から順に見なければいけない試合数分チケットを購入します。

チーム0の必要分を購入したら、チーム1でまた決勝から必要分購入していきます。(もちろん、既に購入してある分は除きます)

これだけで最小費用でチケットを購入できると思います。(試してませんが)


すぐに書けそうでしたが、Largeの提出率が高いので、こちらもやり方を考えてみました。

LargeはDPになりそうです。

チーム0から始めて、必要な試合数分(P-M[i])だけチケットを購入します。

C(n,k)をnからk個選ぶ組み合わせ数とすると、C(P,(P-M[i]))通りの購入方法があります。

次に、チーム1では、チーム0で購入したチケットに加えて、さらに必要なチケットだけを購入します。(これも、チーム0での購入状況に従って何通りか購入方法ができます)

というのをdfsでチーム2^P-1まで続けていき、コストが最小になるものを解とします。


現在のチケットの購入状況のうち、次のチームに対して意味のあるチケットかどうかを判断して状態を更新していくところが少しややこしく、実装に不安がありましたが、恐らくLargeを解かねば通過は難しいと考え、SmallはスルーしてLargeに挑むことにしました。

実際に書いてみると、思ったよりも状態の更新は難しくなく、むしろ計算量を減らす部分で苦労しました。

n個のうちk個を選ぶ組み合わせについて、

  • for文で1<<n通り回して、</li>
  • ビット数がkになる場合以外continue

という方針で書いたのですが・・・

  • 前回の購入時に既にk個を超えたチケットを購入している

という場合に、うまく動きませんでした。(これも、最初正しい答えが出ず原因解明に苦労しました)

とりあえず、

  • ビット数k未満のときcontinue

と変更してみましたが、特定の入力ケースにおいて計算量が爆発的に増え、TLEしてしまいました。

よく考えると既にk個以上のチケットが購入されている場合、これ以上チケットを買う必要はないので、

  • 前回の購入時に既にk個以上チケットを購入している場合、これ以上チケットを購入しないという例外処理をする

で問題なく動きました。

このあたりでビット演算でかなりごちゃごちゃして混乱してしまい、時間を浪費してしまい、結局1時間半近くかかってしまいました。

なんとか、うまくビットDPを混乱せずに書けるようになりたいですが・・・

練習するしかないでしょうか。


あとで、解説や他の人の解答を見ると、決勝のチケットからdfsで購入/非購入を試していけば良かったようです。

このほうがコードも簡単だし、計算量も少なくなりそうです。

一度解けそうな方法が見つかると、他の方法を探そうという意志がかなり弱くなってしまうため、解法が妙に複雑そうな場合は気をつけて別解を考えてみるようにしたいです・・・

以下、提出したソースです。solve関数が本体です。

typedef long long ll;

int popcount(unsigned int x) {
	int result=0;
	for(int i=0; i<sizeof(x)*8; i++) if(x&(1U<<i)) result++;
	return result;
}

class GCJ {
public:
	ll memo[1050][1050];
	int P;
	vector <int> M;
	vector <vector <int> > price;

	ll rec(int d, int pb) {
		ll res=2000000000000, tmp;
		int buy[11];
		int nb, pcnt, ppcnt;

		if(d==(1<<P)) return 0;
		if(memo[d][pb]>=0) return memo[d][pb];

		ppcnt=popcount(pb);
		for(int i=0; i<(1<<P); i++) {
			if(ppcnt>=P-M[d]) {
				if(i>pb) break;
				else i=pb;
			}
			pcnt=popcount(i);
			if((ppcnt<=P-M[d] && pcnt!=P-M[d]) || (ppcnt>P-M[d] && pcnt!=ppcnt)) continue;
			if(popcount(pb|i)!=pcnt) continue;
			memset(buy, 0, sizeof(buy));
			tmp=0;
			for(int j=0; j<P; j++) {
				if(i&(1<<j)) {
					buy[j]=1;
					if(!(pb&(1<<j))) tmp+=price[j][d/(1<<(j+1))];
				}
			}
			nb=0;
			for(int j=0; j<P; j++) {
				if(buy[j]) {
					if((d+1)%(1<<(j+1))>0) nb|=(1<<j);
				}
			}
			tmp+=rec(d+1, nb);
			res=min(res, tmp);
		}

		memo[d][pb]=res;
		return res;
	}

	ll solve(int _P, vector <int> _M, vector <vector <int> > _price) {
		ll res=0;
		
		P=_P; M=_M; price=_price;
		memset(memo, -1, sizeof(memo));
		res=rec(0, 0);
		return res;
	}
};

Google Code Jam 2010 Round 2 A Elegant Diamond

| 00:16 | Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) のブックマークコメント

残り30分となってしまいましたが、この時点で550位くらいで、おそらくもう一問解かないと通過できないだろうという状態でした。

問題Aについては実装が難しそうでしたが、既に問題の内容は把握済みでしたので、これをやるしかないと思い、進めました。


やり方として、せっかく綺麗なダイアの形で与えられた入力をわざわざvector <int>に直してしまい、非常に処理が煩雑になってしまいました。。。

stringのまま読み込めば良かった・・・不必要にメモリ効率を良くしようとする悪いくせが出てしまいました。

30分では全く間に合わず、残念ながら私のGoogle Code Jam 2010はここで終わってしまいました。

他にも色々アルゴリズム的に判定処理を間違えたりしていたので、どちらにしてもダメでした。

今の私の実力ではこれでベストを尽くしたという感じです。

これ以上進むためには、妙なミスを減らすこと、コーディングを早くすること、そのためにさらに訓練を積み重ねることがまず必要なようです。

以下、コンテスト終了後に書いたコードです。solve関数が本体です。stringでの読み込みに直してあります。

check関数の中で同じチェックを2度するなど冗長な部分がありますが、このほうが早く書けると思うのでそのままにしてあります。


class GCJ {
public:
	int k;
	vector <string> dia;

	bool check(int r, int c, int s) {
		int top, rig, bot, lef;
		for(int i=1; i<s; i++) {
			for(int l=0; l<=i; l++) {
				top=r-i+l; rig=c+l; bot=r+i-l; lef=c-l;
				if(abs(top-(k-1))+abs(rig-(k-1))<k && abs(top-(k-1))+abs(lef-(k-1))<k && dia[top][rig]!=dia[top][lef]) return false;
				if(abs(top-(k-1))+abs(rig-(k-1))<k && abs(bot-(k-1))+abs(rig-(k-1))<k && dia[top][rig]!=dia[bot][rig]) return false;
				if(abs(bot-(k-1))+abs(lef-(k-1))<k && abs(bot-(k-1))+abs(rig-(k-1))<k && dia[bot][lef]!=dia[bot][rig]) return false;
				if(abs(bot-(k-1))+abs(lef-(k-1))<k && abs(top-(k-1))+abs(lef-(k-1))<k && dia[bot][lef]!=dia[top][lef]) return false;
			}
		}
		return true;
	}

	int solve(int _k, vector <string> _dia) {
		int r, c;
		int dri[4]={-1,0,1,0}, dci[4]={0,1,0,-1}, dr[4]={1,1,-1,-1}, dc[4]={1,-1,-1,1};

		k=_k; dia=_dia;
		r=k-1; c=k-1;
		if(check(r, c, k)) return 0;
		for(int i=1; i<2*k; i++) {
			for(int j=0; j<4; j++) {
				r=k-1+dri[j]*i; c=k-1+dci[j]*i;
				for(int l=0; l<i; l++) {
					if(check(r, c, k+i)) return (k+i)*(k+i)-k*k;
					r+=dr[j]; c+=dc[j];
				}
			}
		}

		return 0;
	}
};

Google Code Jam 2010 Round 2 D Grazing Google Goats

| 00:17 | Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) のブックマークコメント

コンテスト中は読むこともできませんでしたが、後で読んでみるとSmallは2円の重なる面積を求めるだけのようなので、簡単そうでした。

ということで解いてみましたが、意外と扇形の面積の求め方で場合分けなどが必要になってきて、時間がかかってしまいました。(40分くらい)

もっと簡単に書けるみたいなので、幾何に関する勉強が必要です。

以下、ソースです。solve関数が本体です。


typedef complex <double> pt;

double triangle_area_u(pt a, pt b, pt c) {
	return fabs(imag(conj(b-a)*(c-a))*0.5);
}

vector <pt> cross_c_c(pt c, double r, pt d, double s) {
	vector <pt> res;
	double di=abs(c-d);

	if (di<=r+s && di>=abs(r-s) && !(c==d)) {
		double l=((r*r-s*s)/di+di)/2.0;
		double n=sqrt(r*r-l*l);
		pt e=c+(d-c)*l/di;
		pt p=(d-c)*n/di*pt(0,-1);
		res.push_back(e+p);
		res.push_back(e-p);
	}
	return res;
}

vector <double> cross_l_l(pt a, pt u, pt b, pt v) {
	vector <double> res;
	double det=imag(conj(u)*v);

	if (abs(det)>1e-7) {
		res.push_back(-imag(conj(v)*(b-a))/det);
		res.push_back(-imag(conj(u)*(b-a))/det);
	}
	return res;
}

class GCJ {
public:
	vector <double> solve(int N, int M, vector <int> Px, vector <int> Py, vector <int> Qx, vector <int> Qy) {
		vector <double> res;
		vector <pt> c;
		pt a, b, q;
		double da, db, dab, area, areaa, areab;
		
		a.real(Px[0]); a.imag(Py[0]);
		b.real(Px[1]); b.imag(Py[1]);
		for(int i=0; i<M; i++) {
			q.real(Qx[i]); q.imag(Qy[i]);
			da=abs(q-a); db=abs(q-b); dab=abs(a-b);
			//a円とb円の交点を求める
			c=cross_c_c(a, da, b, db);
			//扇形の面積を求める(1/2 θr^2)
			areaa=abs(arg((c[0]-a)/(c[1]-a))*da*da/2);
			areab=abs(arg((c[0]-b)/(c[1]-b))*db*db/2);
			//扇形から三角形の面積を引く
			areaa-=triangle_area_u(a, c[0], c[1]);
			areab-=triangle_area_u(b, c[0], c[1]);
			//c[0]c[1]直線とab直線の交点を求める
			//ab方向に負ならa円の面積から引く
			if(cross_l_l(a, b-a, c[0], c[1]-c[0])[0]<0) {
				areaa=M_PI*da*da-areaa;
			}
			//bも同様
			if(cross_l_l(b, a-b, c[0], c[1]-c[0])[0]<0) {
				areab=M_PI*db*db-areab;
			}
			area=areaa+areab;
			res.push_back(area);
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100606