Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-05Google Code Jam 2011 Round 2

  • A-small/A-Large/B-small(1WA)/B-Large:Passed, score:38, penalty(time):1:48:41, rank:739
  • B, Cでハマって敗北・・・何をやってるんだ・・・

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