Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-16SRM373 (Practice)

SRM 373 RoadCrossing

|  SRM 373 RoadCrossing - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 373 RoadCrossing - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7521

  • こういう問題のコツはギリギリの状況を考えること
    • 車が通れるか通れないかは特定の時間だけ調べればOK
    • 歩行者のペアについて、距離がちょうど車のサイズになった時間を全て列挙する
    • あと念のため、車が到着した時間、各歩行者についても候補に追加する
  • サンプル通った。提出
  • なぜかWA。方針はあってるはずだが・・・
    • 時間を求める計算式が間違っていた・・・
      • こういうのは頭の中で考えずちゃんと紙に書いて定式化すべき
    • 何故サンプルが通ったのか
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class RoadCrossing {

	public double EPS = 0.00000000001;
			
	public class Walker {
		double from;
		double speed;
		int fi, si;

		Walker(int t, int s) {
			from = t;
			speed = s;
			fi = t;
			si = s;
		}
	}

	public double passTime(String[] pedestrians, int roadWidth, int carWidth,
			int carArrival) {
		int len = pedestrians.length;
		Walker[] w = new Walker[len];
		for (int i = 0; i < len; i++) {
			String[] data = pedestrians[i].split(" ");
			w[i] = new Walker(Integer.valueOf(data[0]),
					Integer.valueOf(data[1]));
		}

		List<Double> candidates = new ArrayList<Double>();
		for (int i = 0; i < len; i++) {
			candidates.add(w[i].from);
			candidates.add(w[i].from + (roadWidth - carWidth) / w[i].speed);
			candidates.add(w[i].from + (carWidth) / w[i].speed);
			candidates.add(w[i].from + roadWidth / w[i].speed);
		}

		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (w[i].si == w[j].si) {
				} else {
					double d = w[i].from*w[i].speed - w[j].from*w[j].speed;
					double time1 = (d - carWidth) / (w[i].speed - w[j].speed);
					double time2 = (d + carWidth) / (w[i].speed - w[j].speed);
					candidates.add(time1);
					candidates.add(time2);
				}
			}
		}
		candidates.add(carArrival * 1.0d);

		double ptime = Double.MAX_VALUE;
		for (int i = 0; i < candidates.size(); i++) {
			double time = candidates.get(i);
			if (time < carArrival) {
				continue;
			}
			List<Double> positions = new ArrayList<Double>();
			for (int j = 0; j < len; j++) {
				if (time >= w[j].fi) {
					double pos = w[j].speed * (time - w[j].from);
					if (0 < pos && pos < roadWidth) {
						positions.add(pos);
					}
				}
			}
			Collections.sort(positions);
			if (positions.size() == 0) {
				ptime = Math.min(ptime, time);
			} else {
				positions.add(0.0d);
				positions.add(roadWidth * 1.0d);
				Collections.sort(positions);
				for (int j = 0; j < positions.size() - 1; j++) {
					double d = positions.get(j + 1) - positions.get(j);
					if (d + EPS > carWidth) {
						ptime = Math.min(ptime, time);
						break;
					}
				}
			}
		}
		return ptime;
	}
}