Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-05Google Code Jam 2011 Round 2

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