Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-12-29SRM492 Div1

SRM492 Div1 250 TimeTravellingGardener

| 17:18 | SRM492 Div1 250 TimeTravellingGardener - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM492 Div1 250 TimeTravellingGardener - SRM diary(Sigmar) SRM492 Div1 250 TimeTravellingGardener - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

2本の木を選んで直線を引き、直線より低い木がなければOKとして直線より高い木を数えるだけ

と思ったがサンプルを見ると端っこの1本の木の高さを0にしたパターンも必要ぽい

方針はすぐ分かるのだが・・こういうの大嫌い。不等式の計算ややこしい。

案の定全然答え合わずデバッグでものすごく時間がかかる。

→できた。35分もかかった。終わった。。。

→提出


システムテスト

Passed


後で

無理に整数での計算に拘らなくてもEPSを導入すればdoubleでも安全なレベルだからdoubleのほうがややこしくなくて良かったかもしれない

でも怖くて本番ではやはりdoubleにできない・・(といいつつ一部doubleを使っているが)


ソースコード

class TimeTravellingGardener {
public:
	int determineUsage(vector <int> d, vector <int> h) {
		int n=h.size();
		vector <int> x(n);
		x[0]=0;
		for(int i=0; i<n-1; i++) {
			x[i+1]=x[i]+d[i];
		}

		int res=1000000000;
		for(int i=1; i<n; i++) {
			int cnt=0;
			bool ok=true;
			for(int j=0; j<n; j++) {
				if(h[j]*x[i]<h[i]*x[j]) ok=false;
				if(h[j]*x[i]!=h[i]*x[j]) cnt++;
			}
			if(ok) res=min(res, cnt);
		}
		for(int i=0; i<n-1; i++) {
			int cnt=0;
			bool ok=true;
			for(int j=0; j<n; j++) {
				if(h[j]*(x[n-1]-x[i])<h[i]*(x[n-1]-x[j])) ok=false;
				if(h[j]*(x[n-1]-x[i])!=h[i]*(x[n-1]-x[j])) cnt++;
			}
			if(ok) res=min(res, cnt);
		}
		for(int i=0; i<n; i++) {
			for(int j=i+1; j<n; j++) {
				bool ok=true;
				int cnt=0;
				for(int k=0; k<n; k++) {
					if(x[i]!=x[j]) if((h[j]-h[i])*(x[k]-x[i])/(double)(x[j]-x[i])+h[i]<0) ok=false;
					if((h[k]-h[i])*(x[j]-x[i])<(h[j]-h[i])*(x[k]-x[i])) ok=false;
					if((h[k]-h[i])*(x[j]-x[i])!=(h[j]-h[i])*(x[k]-x[i])) cnt++;
				}
				if(ok) res=min(res, cnt);
			}
		}

		return res;
	}
};


SRM492 Div1 550 TimeTravellingTour

| 17:18 | SRM492 Div1 550 TimeTravellingTour - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM492 Div1 550 TimeTravellingTour - SRM diary(Sigmar) SRM492 Div1 550 TimeTravellingTour - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん・・

始点と終点をmemo化して適当に再帰で解けそうな気がするけど

時間ない・・とりあえず書くか

→合わない。なんかループしてるし。ちょっと違う・・

→だめだ・・残り5分。修正できない。終わった


後で

分岐する都市を決めて、その都市まで行き、そこから訪問先を前半と後半に分けて再帰的に訪問することで解けます

整理すればなんということはないが整理する時間が足りない

正直250に時間かけ過ぎると全然無理すぎるしもうちょっと簡単にしてほしい・・

計算量がO(n^5)なんだが・・最大ケース1秒くらいです


ソースコード

const ll INF=100000000000000000LL;
ll memo[52][52][52];

template <class T> vector <T> strspl(string str, char delim) {
	vector <T> res;
	stringstream ss(str);
	string s;
	while(std::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;
}

class TimeTravellingTour {
public:
	int n, m;
	vector <int> city;
	ll cost[52][52];

	//都市curから、beginからendまでの都市を訪問する
	ll rec(int begin, int end, int cur) {
		ll res=INF;
		if(end-begin==1) return cost[cur][city[begin]];
		if(memo[begin][end][cur]>=0) return memo[begin][end][cur];
		for(int fork=0; fork<n; fork++) {
			for(int partition=begin+1; partition<end; partition++) {
				res=min(res, cost[cur][fork]+rec(begin, partition, fork)+rec(partition, end, fork));
			}
		}
		memo[begin][end][cur]=res;
		return res;
	}

	long long determineCost(int N, vector <int> city, vector <string> road) {
		long long res=INF;

		n=N;
		this->city=city;
		m=city.size();
		memset(memo, -1, sizeof(memo));
		for(int i=0; i<n; i++) for(int j=0; j<n; j++) cost[i][j]=INF;
		for(int i=0; i<n; i++) cost[i][i]=0;

		//parse
		string s=accumulate(road.begin(), road.end(), string());
		vector <string> vs=strspl <string>(s, ' ');
		for(int i=0; i<(int)vs.size(); i++) {
			vector <int> vi=strspl <int>(vs[i], ',');
			cost[vi[0]][vi[1]]=cost[vi[1]][vi[0]]=vi[2];
		}

		//warshall-floyd
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);
				}
			}
		}

		res=rec(0, m, 0);
		if(res>=INF) res=-1;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101229