Hatena::Grouptopcoder

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

 | 

2010-11-19

Single Round Match 488 14:13 Single Round Match 488 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 488 - nodchipのTopCoder日記 Single Round Match 488 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 TheBoredomDivOne

  • 47・・・?
  • ああ、あの人か
  • 一問目から期待値
  • これは嫌な予感
  • 案の定、式が分からない
  • orz
  • Opened
  • 以下はPracticeで通したソースコードです
class TheBoredomDivOne {
public:
	double dp[64][64];
	double two(int n) {
		return n * (n - 1) * 0.5;
	}
	double f(int n, int m) {
		if (m <= 0) {
			return 0.0;
		}
		double& r = dp[n][m];
		if (r == -1.0) {
			const double p0 = two(n) / two(n + m);
			const double p1 = m * n / two(n + m);
			const double p2 = two(m) / two(n + m);
			r = (1.0 + p1 * f(n + 1, m - 1) + p2 * f(n + 2, m - 2) ) / (1.0 - p0);
		}
		return r;
	}

	double find(int n, int m) {
		fill_n((double*)dp, sizeof(dp) / sizeof(double), -1.0);
		return f(n, m);
	}
}

Middle 500 TheBoringStoreDivOne

  • ・・・?
  • 問題の意味が分からない・・・orz
  • サンプルも分からないorz
  • Opened

Hard 1000 TheBoringGameDivOne

  • なんだか難しそう
  • パス
  • Opened

Challenge Phase

  • 0完だったのでなんとかpositive scoreにしなければ
  • 今回は青コーダーが多い部屋だから250でメモなし再帰をしている人を狙おう
  • いた!
  • +50
  • さらに見つけた!
  • +50
  • 250は全員見終わった
  • 次は500かなぁ
  • 500もTLEしそうな人を見つけていこう
  • このひとTLEしそう・・・
  • でも計算量が見積もれない・・・
  • O(N^5)なんだけどいろんな所で枝が刈れてるからなぁ
  • ・・・
  • やめておこう

System Test

x x x +100 2052->2003 最小限の被害で済みました。自己を起こさないためには確率と期待値の勉強を一からやり直す必要がありますが、正直気が乗りませんorz

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