Hatena::Grouptopcoder

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

 | 

2010-10-21

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

Easy 250 AfraidOfEven

  • なんか面倒そう
  • とりあえず考えてみる
  • 数列って言うくらいだから奇数番目か偶数番目は奇数なんじゃね?<-間違い
  • じゃあ奇数番目か偶数番目で場合分けして初項と公差求めればいいか
  • submit
    • Passed System Test
  • (全て偶数の場合いには自動的に奇数に変化するので上記のコードでも通ってしまう。怖い・・・。)
class AfraidOfEven {
public:
	vector <int> restoreProgression(vector <int> seq) {
		vector <int> result;

		const int N = seq.size();
		REP (offset, 2) {
			const int diff2 = seq[offset + 2] - seq[offset];
			bool ok = true;
			for (int i = offset + 2; ok && i < N; i += 2) {
				ok = (seq[i] - seq[i - 2] == diff2);
			}
			if (!ok) {
				continue;
			}

			const int diff = diff2 / 2;
			const int start = seq[offset] - diff * offset;
			vector<int> answer;
			REP(i, N) {
				answer.push_back(start + diff * i);
			}

			ok = true;
			REP(i, N) {
				int number = answer[i];
				while (number && number % 2 == 0) {
					number /= 2;
				}
				if (seq[i] != number) {
					ok = false;
				}
			}
			if (!ok) {
				continue;
			}

			if (result.empty() || answer < result) {
				result = answer;
			}
		}

		return result;
	}
}
追記 2010/10/21 23:24
  • rng_58さんの指摘により{3, 7, 1, 9}でTLEすることが分かりました。ソースコードを修正いたしました。

Middle 500 RectangleAvoidingColoring

  • いつも通りDP臭はする・・・
  • でも2^50が掛かるDPしか思いつかないorz
  • Opened

Hard 1000 Deposit

  • ☆幾☆何☆
  • (゜ρ゜)ジュルリ
  • DPなんてエイリアンたちのための高尚な遊びだよね?日本人ならやっぱり幾何だよね?
  • ということで実装開始
  • まずは各辺を最も遠い点で分割
    • 辺ABについて、最も遠い点がAと同じ部分の終点を二分探索で求める
    • 前の終点から次の終点を順に求める
  • 続いて分割した各線分について、最も遠い点からdepositの各頂点に引いた半直線との交点で分割
  • 交点と交点の中点から最も遠い点までの線分とdepositが交差していたら、その部分の距離を加えていく
  • (実装中)
  • (実装中)
  • (実装中)
  • デバッグ開始
  • なんか比の扱い間違ってる・・・
  • さらにデバッグ
  • 距離を加算する位置を間違えた
  • さらにデバッグ
  • なんか答えが全然合わない・・・orz
  • Opened
  • 初期化忘れでしたorz
namespace std {
	bool operator < (const P& lh, const P& rh) {
		return lh.real() != rh.real() ? lh.real() < rh.real() : lh.imag() < rh.imag();
	}
}

// 線分の交差判定
bool cross(const P& p1, const P& p2, const P& p3){
	P a = p2 - p1;
	P b = p3 - p1;
	if (abs(a.real() * b.imag() - a.imag() * b.real()) > EPS){
		return false;
	}
	if (a.real() * b.real() + a.imag() * b.imag() < 0){
		return false;
	}
	P c = p1 - p2;
	P d = p3 - p2;
	if (c.real() * d.real() + c.imag() * d.imag() < 0){
		return false;
	}
	return true;
}
bool cross(const P& p1, const P& p2, const P& p3, const P& p4, P& out) {
	const double x1 = p1.real();
	const double y1 = p1.imag();
	const double x2 = p2.real();
	const double y2 = p2.imag();
	const double x3 = p3.real();
	const double y3 = p3.imag();
	const double x4 = p4.real();
	const double y4 = p4.imag();
	double d = (x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3);
	if (abs(d) < EPS) {
		return false;
	}
	double s = (x4 - x3) * (y3 - y1) - (x3 - x1) * (y4 - y3);
	double t = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	if (d < 0){
		d *= -1;
		s *= -1;
		t *= -1;
	}
	bool result = (0 <= s && s <= d && 0 <= t && t <= d);
	if (result) {
		s /= d;
		out = p1 * (1.0 - s) + p2 * s;
	}
	return result;
}

class Deposit {
public:
	vector<P> site;
	vector<P> deposit;
	int findFarPoint(const P& p) {
		int bestIndex = -1;
		double bestDistance = -1.0;
		REP(n, site.size()) {
			const double distance = abs(p - site[n]);
			if (bestDistance < distance) {
				bestDistance = distance;
				bestIndex = n;
			}
		}
		return bestIndex;
	}
	void divideEdge(const P& a, const P& b, double begin, vector<pair<double, int> >& divided) {
		if (abs(begin - 1.0) < EPS) {
			return;
		}
		const int first = findFarPoint(a * (1.0 - (begin + EPS)) + b * (begin + EPS));
		double l = begin + EPS;
		double r = 1.0;
		REP(loop, 200) {
			const double m = (l + r) * 0.5;
			if (findFarPoint(a * (1.0 - m) + b * m) == first) {
				l = m;
			} else {
				r = m;
			}
		}
		divided.push_back(make_pair((l + r) * 0.5, first));
		divideEdge(a, b, (l + r) * 0.5, divided);
	}
	double processSegment(const P& a, const P& b, int farPoint) {
		vector<P> points;
		points.push_back(a);
		points.push_back(b);

		const P& c = site[farPoint];
		REP(depositIndex, deposit.size()) {
			P p = deposit[depositIndex];
			p = c + (p - c) / abs(p - c) * 1e4;
			P crossPoint;
			if (cross(a, b, c, p, crossPoint)) {
				points.push_back(crossPoint);
			}
		}
		sort(ALL(points));
		points.erase(unique(ALL(points)), points.end());

		double sum = 0.0;
		for (int i = 0; i < points.size() - 1; ++i) {
			P p = (points[i] + points[i + 1]) * 0.5;
			p = c + (p - c) / abs(p - c) * 1e5;
			bool isCross = false;
			REP(depositIndex, deposit.size()) {
				P crossPoint;
				if (cross(c, p, deposit[depositIndex], deposit[(depositIndex + 1) % deposit.size()], crossPoint)) {
					isCross = true;
					break;
				}
			}

			if (isCross) {
				sum += abs(points[i] - points[i + 1]);
			}
		}
		return sum;
	}
	double processEdge(const P& a, const P& b) {
		vector<pair<double, int> > divided;
		divided.push_back(make_pair(0, -1));
		divideEdge(a, b, 0.0, divided);

		double result = 0.0;
		for (int i = 0; i < divided.size() - 1; ++i) {
			const double r0 = divided[i].first;
			const double r1 = divided[i + 1].first;
			const int farPoint = divided[i + 1].second;
			result += processSegment(a * (1.0 - r0) + b * r0, a * (1.0 - r1) + b * r1, farPoint);
		}
		return result;
	}

	double successProbability(vector <int> siteX, vector <int> siteY, vector <int> depositX, vector <int> depositY) {
		site.clear();
		deposit.clear();
		REP(n, siteX.size()) {
			site.push_back(P(siteX[n], siteY[n]));
		}
		REP(n, depositX.size()) {
			deposit.push_back(P(depositX[n], depositY[n]));
		}

		double ok = 0.0;
		double sum = 0.0;
		REP(n, site.size()) {
			sum += abs(site[n] - site[(n + 1) % site.size()]);
			ok += processEdge(site[n], site[(n + 1) % site.size()]);
		}

		return ok / sum;
	}
}

Challenge Phase

  • 今回は撃墜ポイントが分からない
  • とりあえず250を準備見ていこう
  • ・・・
  • やっぱりわからない
  • そうこうしているうちに500が落とされていく
  • 乗り遅れたorz

System Test

o x x 1877->1914 今回の教訓は、最後まであきらめないこと、メンバ変数の初期化を忘れないこと、でしたorz

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