Hatena::Grouptopcoder

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

 | 

2010-12-21

Codeforces Beta Round #47 11:35 Codeforces Beta Round #47 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #47 - nodchipのTopCoder日記 Codeforces Beta Round #47 - nodchipのTopCoder日記 のブックマークコメント

A. Domino piling

  • まさかの探索か・・・?
  • あ、いや、2で割るだけだった。
  • Accepted
int main() {
	int N, M;
	cin >> N >> M;
	cout << N * M / 2 << endl;
}

B. Choosing Symbol Pairs

  • これ、回すだけ・・・
  • ・・・
  • これはTLEと32bit溢れの予感!
  • ということでO(N)書いて、最大ケース生成プログラムを準備しておく
  • Accepted
int main() {
	ll memo[0x100];
	CLEAR(memo);

	string line;
	cin >> line;
	REP(i, line.size()) {
		++memo[line[i]];
	}

	ll answer = 0;
	REP(i, 0x100) {
		answer += memo[i] * memo[i];
	}
	cout << answer << endl;
}

hackテストケース生成ソースコードはコチラ

int main() {

cout << string(100000, '0') << endl;

}

C. Happy Farm 5

  • サンシャイン牧場ですね(違います)
  • 図を眺めてみる
  • ・・・
  • 幾つかのパターンを紙に書いてみる
  • ・・・
  • 凸包的何か?
  • 各店から上下左右の点を作ってあげて凸包してmax(dx,dy)という解法を考えてみた
  • 反例が思いつかない
  • とりあえず書いてみる
  • Accepted
typedef complex<double> P;

namespace std {
	bool operator < (const P& a, const P& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}
double cross(const P& a, const P& b) {
	return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
	return real(conj(a)*b);
}

struct L : public vector<P> {
	L(const P &a, const P &b) {
		push_back(a); push_back(b);
	}
};

int ccw(P a, P b, P c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;       // counter clockwise
	if (cross(b, c) < 0)   return -1;       // clockwise
	if (dot(b, c) < 0)     return +2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;       // a--b--c on line
	return 0;
}

vector<P> convex_hull(vector<P> ps) {
	int n = ps.size(), k = 0;
	sort(ps.begin(), ps.end());
	vector<P> ch(2*n);
	for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
		while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
	for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
		while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
	ch.resize(k-1);
	return ch;
}

int main() {
	int N;
	cin >> N;
	vector<P> ps;
	REP(n, N) {
		int x, y;
		cin >> x >> y;
		static const int dx[] = {0, 0, 1, -1};
		static const int dy[] = {1, -1, 0, 0};
		REP(dir, 4) {
			ps.push_back(P(x + dx[dir], y + dy[dir]));
		}
	}

	ps = convex_hull(ps);

	double sum = 0.0;
	REP(i, ps.size()) {
		const P& a = ps[i];
		const P& b = ps[(i + 1) % ps.size()];
		const P delta = a - b;
		sum += max(abs(delta.real()), abs(delta.imag()));
	}

	const ll answer = (ll)(sum + 0.5);
	cout << answer << endl;
}

D. Bombing

  • ん?二分探索するだけじゃね?
  • N個中K個倒壊する確率はどうすればいいんだろう?
  • ・・・
  • DP的何かで行けそう
  • 書いてみた
  • サンプル合わない
  • eの値を1.0-eにしてみた
  • サンプル合った
  • submit
  • Accepted
typedef complex<double> P;

double calc(const vector<double>& probs, int K) {
	static double dp[128][128];
	CLEAR(dp);
	dp[0][0] = 1.0;
	REP(i, probs.size()) {
		REP(k, probs.size()) {
			dp[i + 1][k] += dp[i][k] * (1.0 - probs[i]);
			dp[i + 1][k + 1] += dp[i][k] * probs[i];
		}
	}
	double answer = 0.0;
	for (int k = K; k <= probs.size(); ++k) {
		answer += dp[probs.size()][k];
	}
	return answer;
}

bool check(const P& center, const vector<P>& ps, int K, double R, double e) {
	vector<double> probs;
	REP(i, ps.size()) {
		const double D = abs(center - ps[i]);
		if (D < R || D < EPS) {
			probs.push_back(1.0);
		} else {
			probs.push_back(exp(1.0 - D * D / (R * R)));
		}
	}

	return calc(probs, K) > e;
}

int main() {
	int N, K;
	double e, x0, y0;
	cin >> N >> K >> e >> x0 >> y0;
	vector<P> ps;
	e /= 1000.0;
	e = 1.0 - e;

	REP(n, N) {
		double x, y;
		cin >> x >> y;
		ps.push_back(P(x, y));
	}

	check(P(x0, y0), ps, K, 13.0, e);

	double lo = 0.0;
	double hi = 1e20;
	REP(loop, 200) {
		const double mid = (lo + hi) * 0.5;
		if (check(P(x0, y0), ps, K, mid, e)) {
			hi = mid;
		} else {
			lo = mid;
		}
	}
	printf("%.20f\n", lo);
}

E. Square Equation Roots

  • 数論わからないorz

Hack

  • Bで32bit溢れをしていそうな人を狙って落としていってみよう。
  • うわぁ・・・一杯いる
  • あ、一個失敗したorz

System Test

#Who=ABCDE
27nodchip4802+7 / -1498 00:01988 00:031386 00:191280 01:30

サーバートラブルによりnoratedとなりました。赤コーダーリーチがかかっていただけに残念です。

Member Single Round Match 491 11:21 Member Single Round Match 491 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Member Single Round Match 491 - nodchipのTopCoder日記 Member Single Round Match 491 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 FoxMakingDice 11:21  Easy 250 FoxMakingDice - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク -  Easy 250 FoxMakingDice - nodchipのTopCoder日記  Easy 250 FoxMakingDice - nodchipのTopCoder日記 のブックマークコメント

  • きつねたん・・・?
  • rng_58先生だろうか?
  • 問題傾向も似ている気がするし
  • でも58が無い・・・
  • とりあえず考える
  • ・・・
  • (問題を読み間違えていることに気づかない)
  • さっぱりわからない
  • orz

Middle 600 PrefixTree

  • 時間がないのでパス

Hard 900 FoxCardGame

  • 焼き鈍しちゃおうかなぁ・・・
  • とりあえずギャグ回答としてsubmit
  • でも見た感じマッチング的何かだよなぁ
  • コストが分からないorz

Challenge Phase

  • だめだ・・・落とし所が分からないorz

System Test

x x x 2103->1940 予想通り一気に落ちてしまいました。ここから右肩下がりかなのでしょうか・・・。

なおDiv1 250/900のwriterはjaplj先生でした。先生お疲れ様でした。

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