SRM 373 500pt: RoadCrossing

TopCoder

問題概要

横断歩道がある。横断歩道の幅はRで、車の幅はCである。人がN(<50)人いる。各人は時刻T[i]に速度V[i]で横断歩道を渡りはじめる。時刻A以降で車が横切ることのできる最小時刻を求める問題。車が横切るのに必要な時間は考えなくてよい。出てくる数字は1000以下。

考えたこと

  • 幾何とかシミュレーションでよくある特徴点全列挙かな？
  • 時刻を固定したら通過できるかどうかはO(N*log N)で判定できる。
  • 後は特徴点がいくつくらいあるか見積もってみよう。
  • まず、Aとか2000(考えられる最大値)を突っ込む( O(1) )。
  • 次に、確認に対して渡りはじめと渡り終わりと座標Cにいる時刻と座標R-Cにいる時刻を突っ込む( O(N) )。
  • 最後に、任意の二人の距離がCになるとき( O(N^2) )。
  • なので、計算量は全体としてO(N^3 * log N)で余裕。
  • doubleの計算になるけど、出てくる値が小さいのでEPSを適当にとれば通るはず。
  • 書いた。サンプル通った。投げた。落ちた。あれ？
  • 場合分けの座標Cと座標R-Cを書いてなかった。だから場合分けではコメントを書けとあれほど…。

practiceで通ったコード

計算量O(N^3 * log N)。

#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;

const double EPS = 1e-9;

struct RoadCrossing {

	double passTime(vector <string> pedestrians, int roadWidth, int carWidth, int carArrival) {

		//候補点を全列挙する
		vector<double> eventline;
		eventline.push_back(carArrival); //最小値
		eventline.push_back(2000); //最大値


		//データ変換
		const int N = pedestrians.size();
		vector< pair<int,int> > walks; //(T, V)
		for(int i=0; i<N; i++){
			int x, y;
			stringstream ss(pedestrians[i]);
			ss >> x >> y;
			walks.push_back( make_pair(x, y) );

			eventline.push_back(x);
			eventline.push_back(x + (double)roadWidth/y);
		}

		//候補点列挙

		//２歩行者の距離がcarWidthになる場合
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++)if(i!=j){
				const double v1 = walks[i].second, v2 = walks[j].second;
				const double T1 = walks[i].first, T2 = walks[j].first;
				if(v1 != v2){
					const double t = ((v1*T1 - v2*T2) + carWidth) / (v1 - v2);
					eventline.push_back(t);
				}
			}
		}

		//歩行者の進行距離、残り距離がcarWidthになる場合
		for(int i=0; i<N; i++){
			const double v = walks[i].second, T = walks[i].first;
			const double t1 = (carWidth + v*T) / v;
			const double t2 = (roadWidth - carWidth + v*T) / v;
			eventline.push_back(t1);
			eventline.push_back(t2);
		}

		//全候補点をチェック
		sort(eventline.begin(), eventline.end());
		for(int i=0; i<(int)eventline.size(); i++){
			const double t = eventline[i];
			if(carArrival<=t && t<=2000.0 && check(t, walks, roadWidth, carWidth)){
				return t;
			}
		}
		return 2000.0;
	}

	//時刻timeに通れるかどうか判定する。O(N*log N)
	bool check(const double time, const vector<pair<int,int> >& walks,
					const int road_width, const int car_width){
		const int N = walks.size();

		//時刻timeにおける特徴点
		vector<double> pos;
		pos.push_back(0);
		pos.push_back(road_width);

		//時刻timeにおける各員の位置
		for(int i=0; i<N; i++){
			double v = walks[i].second, T = walks[i].first;
			double p = v*(time - T);
			if(0<=p && p<=road_width){
				pos.push_back(p);
			}
		}

		//判定
		sort(pos.begin(), pos.end());
		for(int i=0; i<(int)pos.size()-1; i++){
			double dist = pos[i+1] - pos[i];
			if(dist + EPS > car_width){
				return true;
			}
		}

		return false;
	}
};

バグを減らすための工夫

  • 意味の無い場合分けを減らすようにちゃんとかけたと思う。
  • 今回は意識して中間変数を多用した。まあ、悪くは無かった。