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;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101229