Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2010-02-14

SingleRoundMatch461@TopCoder 12:10 SingleRoundMatch461@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch461@TopCoder - nodchipのTopCoder日記 SingleRoundMatch461@TopCoder - nodchipのTopCoder日記 のブックマークコメント

Easy 300 ColoringRectangle

いくつかの赤と青の円盤の直径が与えられる。これらを用いて幅width、高さheightの長方形をカバーしたい。赤と青の円盤は交互に長方形に乗せていく、次に置く円盤の中心は前に使った円盤の中心より右にくるように置く、同じ色の円盤が重なってはならない、の条件を満たしたとき、最低何枚でカバーできるか求めよ。

  • 英語が難しい・・・
  • 配置の順番を探索するとTLEしそう
  • きっと貪欲に配置すれば良いに違いない
  • となると大きい方から右詰で配置かなぁ・・・
  • 一番左が赤と青のどちらになるか分からないから両方試して良い方を出力しよう
  • サンプルが通らない・・・
  • うわぁぁぁん・・・直径と半径間違えたorz
  • submit

結果:Passed System Tests

class ColoringRectangle {
public:
	int f(int width, int height, const vector<int>& even, const vector<int>& odd) {
		vector<int> rs;
		for (int i = 0; ; ++i) {
			if (i < even.size() && even[i] >= height) {
				rs.push_back(even[i]);
			} else {
				break;
			}

			if (i < odd.size() && odd[i] >= height) {
				rs.push_back(odd[i]);
			} else {
				break;
			}
		}

		double x = 0.0;
		for (int index = 0; index < rs.size(); ++index) {
			const int r = rs[index];

			x += 2 * sqrt(r * (double)r * 0.25 - height * (double)height * 0.25);

			if (width < x + EPS) {
				return index + 1;
			}
		}

		return INT_MAX;
	}

	int chooseDisks(int width, int height, vector <int> red, vector <int> blue) {
		sort(red.begin(), red.end(), greater<int>());
		sort(blue.begin(), blue.end(), greater<int>());
		int result = INT_MAX;
		result = min(result, f(width, height, red, blue));
		result = min(result, f(width, height, blue, red));
		if (result == INT_MAX) {
			result = -1;
		}
		return result;
	}
}

Middle 500 BuildingCities

二次元座標上のN個の街の座標が与えられる。旅人はmaxDirect以下の街の間しか移動できない。また旅人は最大でmaxTravel以下の距離しか移動できない。新たに幾つかの街を建設するとき、旅人が0番目の街からN-1番目の街に移動できるようにするために必要な最小の新たな街の個数を求めよ。

  • ダイクストラ・・・っぽけど違うような
  • とりあえず紙に書き出してみよう
  • ふむふむこんな感じかぁ
  • 何個街を建設すればある街まで行けるかなんだから
  • 新たに建設する街の個数の次元を加えた拡張ダイクストラだ
  • 2次元目の最大値幾つくらいだろう・・・
  • マップの端から端まで2000√2だから、8000位あれば余裕だな
  • 書いた
  • submit

結果 : Challenge Succeeded 枝刈りに使った変数を間違えました

以下は修正後のソースです

class BuildingCities {
public:
	int findMinimumCities(int maxDirect, int maxTravel, vector <int> cityX, vector <int> cityY) {
		const int N = cityX.size();
		static const int kMaxBuild = 8 * 1024;
		static double dp[64][kMaxBuild];
		fill_n((double*)dp, sizeof(dp) / sizeof(double), INT_MAX);

		dp[0][0] = 0;
		priority_queue<pair<double, pair<int, int> > > q;
		q.push(make_pair(0, make_pair(0, 0)));
		int bestBuild = kMaxBuild;
		while (!q.empty()) {
			const double currentCost = -q.top().first;
			const int currentCity = q.top().second.first;
			const int currentBuild = q.top().second.second;
			q.pop();

			if (abs(dp[currentCity][currentBuild] - currentCost) > EPS) {
				continue;
			}

			for (int nextCity = 0; nextCity < N; ++nextCity) {
				const int dx = cityX[currentCity] - cityX[nextCity];
				const int dy = cityY[currentCity] - cityY[nextCity];
				const double r = sqrt(dx * (double)dx + dy * (double)dy);
				const int build = (int)(r / maxDirect - EPS);
				const int nextBuild = currentBuild + build;
				if (nextBuild >= bestBuild) {
					continue;
				}

				const double nextCost = currentCost + r;
				
				if (nextCost > maxTravel + EPS) {
					continue;
				}

				if (dp[nextCity][nextBuild] > nextCost + EPS) {
					dp[nextCity][nextBuild] = currentCost + r;
					q.push(make_pair(-dp[nextCity][nextBuild], make_pair(nextCity, nextBuild)));

					if (nextCity == N - 1 && dp[nextCity][nextBuild] < maxTravel + EPS) {
						bestBuild = min(bestBuild, nextBuild);
					}
				}
			}
		}

		int result = INT_MAX;

		for (int build = 0; build < kMaxBuild; ++build) {
			if (dp[N - 1][build] < maxTravel + EPS) {
				if (result > build) {
					result = build;
				}
			}
		}

		if (result == INT_MAX) {
			result = -1;
		}
		return result;
	}
}

Hard 950 FencingGarden

直線状の壁がある。この壁に3辺を足して囲みを作りたい。N本のフェンスの長さが与えられる。フェンスは1本だけ切っても良い。面積が最大になるように配置した時の壁に平行な辺の長さを求めよ。

  • 探索・・・?
  • 分かりません

Challenge Phase

  • 自分のやつ落とされた・・・orz
  • 他の人の500を見てみる
  • この貪欲解法怪しすぎる・・・
  • 落とされた・・・orz
  • 250を見てみる
  • この貪欲解法あやしすぎる・・・
  • 時間切れ・・・orz

System Test

o x x 1929->1958 上がってしまいました・・・

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100214
 |