Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-05-20SRM543 Div1

SRM543 Div1 500 EllysRivers

| 19:30 | SRM543 Div1 500 EllysRivers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM543 Div1 500 EllysRivers - SRM diary(Sigmar) SRM543 Div1 500 EllysRivers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

明らかに普通のDPは無理だよね


これが船が島のどこからでも(整数の位置でなくても)発着できて、歩くのが一切ないのであれば、単なる光の入射角を決める問題である

高校物理によると光の進む速度によって屈折率が決まり、光が通る道は常にその場所への最短路となるらしい

ということは、光の屈折率を使えば最短路が出せるということである

  • sin(θ1)/sin(θ2)=v1/v2 みたいな感じ

入射角が決まれば、屈折率に従って右端の島のどの位置に着くのかは一意に定まる

そこで、入射角を二分探索することで、目的地に到着するための入射角を決めることができる


walkはどこでやっても同じだから、左端の島だけで歩けばいいんだろう

ということは、どうせwalkの距離に対して到着時間が谷型の関数になるんだろうから、三分探索で出せるんだろう


あとは整数の位置しか港がないから、doubleで計算した港の位置の近くにある適当な港を使って、どれを使えば一番速いか適当に探索すればよさげ


書いてみようとする


・・・


タイムアップ


こんな複雑なの時間内に書けるわけなかった/(^o^)\


チャレンジフェーズ

適当に怪しそうな人にでかいケースをぶつけて+50

たまたま誤差死してくれたみたいで助かった

こんなお茶濁し的なやり方では長くは持たないのでちゃんと問題を解けなければ・・・


後で

Greedyで良かったっていう・・・


どこかで北にlength回進まなければならないので、最初は全ての島で下端にいるとして、1つ北に進むのはどの川 or 歩きを使えば一番速いかっていうのをGreedyにlength回求めるだけだった


DPで計算量が多すぎるときに、部分的にGreedyにしたり、そのために見方を変えるのは常套手段で、今回もそういう意味では典型的なんだけど、全く対応できてない、というか、ちゃんと考えられてない気がする


屈折率による解法でも解けたけど、ちょっと書くのが遅すぎるし、色々いけてなかった。。

まあ高校物理なんて覚えてないんで思い出すのに時間がかかったってのもありますが・・・


ソースコード

せっかくだから屈折率のコードをpracticeに通したので掲載します

港を選ぶ辺りが若干嘘解法っぽいが、lengthの大きさに耐性のある解法だからあながち意味のない考え方でもないかな?

class EllysRivers {
public:
	// 島の長さlengthとしたときの最短となる入射角を求める
	double bestangle(double length, const vector <int> &width, const vector <int> &speed) {
		int n=width.size();
		double hi=M_PI/2, lo=0, mid;
		for(int i=0; i<100; i++) {
			mid=(hi+lo)/2;
			bool ok=true;
			double h=(double)width[0]*tan(mid);
			double theta=mid;
			for(int j=0; j<n-1; j++) {
				double sinn=sin(theta)*(double)speed[j+1]/(double)speed[j];
				if(abs(sinn)>=1) { ok=false; break; } // 全反射
				theta=asin(sinn);
				h+=(double)width[j+1]*tan(theta);
			}
			if(!ok || h>length) hi=mid;
			else lo=mid;
		}
		return lo;
	}

	double getMin(int length, int walk, vector <int> width, vector <int> speed) {
		double res=1e100;
		int n=width.size();
		
		// 歩く距離の最適値を求める(double)
		double hi=length, lo=0, mid[2];
		for(int i=0; i<100; i++) {
			mid[1]=(hi-lo)/3;
			mid[0]=lo+mid[1];
			mid[1]+=mid[0];
			double theta[2];
			theta[0]=bestangle((double)length-mid[0], width, speed);
			theta[1]=bestangle((double)length-mid[1], width, speed);
			double tres[2];
			for(int j=0; j<2; j++) {
				tres[j]=mid[j]/(double)walk;
				tres[j]+=((double)width[0]/cos(theta[j]))/(double)speed[0];
				for(int k=0; k<n-1; k++) {
					theta[j]=asin(sin(theta[j])*speed[k+1]/speed[k]);
					tres[j]+=((double)width[k+1]/cos(theta[j]))/(double)speed[k+1];
				}
			}
			if(tres[0]<tres[1]) hi=mid[1];
			else lo=mid[0];
		}

		// 最適な入射角における各島の到着位置(南北方向)を求める(double)
		double theta=bestangle((double)length-lo, width, speed);
		vector <double> hv;
		double h=lo+(double)width[0]*tan(theta);
		hv.push_back(h);
		for(int j=0; j<n-1; j++) {
			double sinn=sin(theta)*(double)speed[j+1]/(double)speed[j];
			assert(abs(sinn)<1);
			theta=asin(sinn);
			h+=(double)width[j+1]*tan(theta);
			hv.push_back(h);
		}
		
		// 各島の到着位置の前後適当な範囲の港を使って最短路を求める
		const int range=10;
		int curp[range];
		for(int i=0; i<range; i++) curp[i]=(int)lo-(range-1)/2+i;
		double cur[range];
		for(int i=0; i<range; i++) cur[i]=abs((double)curp[i]/walk);
		for(int k=0; k<n; k++) {
			double nxt[range];
			for(int i=0; i<range; i++) nxt[i]=1e100;
			int nxtp[range];
			for(int i=0; i<range; i++) nxtp[i]=(int)hv[k]-(range-1)/2+i;
			for(int i=0; i<range; i++) for(int j=0; j<range; j++) {
				nxt[j]=min(nxt[j], cur[i]+hypot((double)width[k], (double)(nxtp[j]-curp[i]))/(double)speed[k]);
			}
			memcpy(cur, nxt, sizeof(cur));
			memcpy(curp, nxtp, sizeof(curp));
		}
		for(int i=0; i<range; i++) if(curp[i]==length) res=cur[i];
		
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120520