Hatena::Grouptopcoder

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

 | 

2010-01-14

SingleRoundMatch458@TopCoder 03:13 SingleRoundMatch458@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch458@TopCoder - nodchipのTopCoder日記 SingleRoundMatch458@TopCoder - nodchipのTopCoder日記 のブックマークコメント

SingleRoundMatch458@TopCoderの参加記録です。今回の問題もrng_58先生がwriterを担当されたようです。なおrng_58先生によると全ての問題が1行で書けるようです。

Easy 250 BouncingBalls

数直線上に質量と体積の無視できるボールが置かれている。このボールが一定の速度で数直線方向に動き出す。ただし向きは正負ランダムである。ボール同士がぶつかるとそのまま反射する。T秒以内にぶつかったボールの数の期待値を求めよ。

  • うぎゃぁシミュレーション問題、しかも面倒
  • ・・・本当に面倒なのか?250だぞ
  • まず反射は素通りと等価か・・・。
  • ボールの数は12個だから2^12^2ループ回してぶつかったボールを数えるだけ・・・?
  • できた。submit。

結果 : All Tests Passed

class BouncingBalls {
public:
	double expectedBounces(vector <int> x, int T) {
		const int n = x.size();
		int result = 0;
		//0は左,1は右
		for (int flag = 0; flag < (1 << n); ++flag) {
			for (int left = 0; left < n; ++left) {
				if ((flag & (1 << left)) != 0) {
					continue;
				}
				for (int right = 0; right < n; ++right) {
					if ((flag & (1 << right)) == 0) {
						continue;
					}

					if (x[left] < x[right]) {
						continue;
					}

					if (x[left] - x[right] <= T * 2) {
						++result;
					}
				}
			}
		}

		return result / (double)(1 << n);
	}
};

Middle 450 NewCoins

商品が幾つかあり、それらを硬貨をお釣りの無いように支払って購入した。この国の硬貨の額面はx0, x1, x2, ... xnであり、a<bならxbはxaの整数倍となっている。全ての商品を購入するために必要な最小の硬貨の枚数を求めよ。</ppp>

  • DPか何かか・・・
  • 諦めたい
  • というワケには行かないので手をつけてみる
  • ・・・
  • わからない
  • ・・・
  • 硬貨の額面で探索とか・・・?
  • 残りの硬貨の枚数をキーとしたダイクストラとか・・・?
  • どうみてもTLEだよなぁ
  • ・・・
  • わからない
  • ・・・
  • ボトムアップに探索してみる?
  • 途中でハッシュでメモしてみる?
  • できた
  • サンプル通った!
  • あれ、もう時間過ぎてたorz

以下はPracticeで通ったソースコードです。

class NewCoins {
public:
	map<ll, int> memo;
	ll hash(const vector<int>& v) {
		ll x = -1;
		for (int i = 0; i < v.size(); ++i) {
			x *= 137;
			x += v[i];
		}
		return x;
	}
	int f(const vector<int>& price) {
		const ll h = hash(price);
		if (memo.count(h)) {
			return memo[h];
		}

		int bestValue = INT_MAX;
		const int maxPrice = *max_element(price.begin(), price.end());
		if (maxPrice == 1) {
			bestValue = 0;
			for (int i = 0; i < price.size(); ++i) {
				bestValue += price[i];
			}
			return memo[h] = bestValue;
		}
		for (int div = 2; div <= maxPrice; ++div) {
			int value = 0;
			vector<int> nextPrice = price;
			for (vector<int>::iterator it = nextPrice.begin(); it != nextPrice.end(); ++it) {
				value += *it % div;
				*it /= div;
			}
			bestValue = min(bestValue, value + f(nextPrice));
		}

		return memo[h] = bestValue;
	}
	int minCoins(vector <int> price) {
		memo[hash(vector<int>(price.size()))] = 0;
		return f(price);
	}
}

撃墜フェイズ

  • 450のTLEに狙いをつけて・・・
  • あ、この人TLEしそう
  • とられた
  • ・・・。
  • orz

システムテスト

o x x 197位

総評

450がもう少し速く書ければよかったのに・・・orz

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