Hatena::Grouptopcoder

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

 | 

2010-07-06

2010 TCO Marathon Round 1 22:44 2010 TCO Marathon Round 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 2010 TCO Marathon Round 1 - nodchipのTopCoder日記 2010 TCO Marathon Round 1 - nodchipのTopCoder日記 のブックマークコメント

Planarity

  • なるべく線が交わらないように配置するらしい
  • 良く分からないけど良く分からないときはとりあえず焼きなませばおk(ぉぃ
  • とりあえずそれっぽいの書いてみた
  • 全く勝負にならないorz
  • 要らない処理を省いてみた
  • 交線判定も少し速くしてみた
  • まぁまぁいい感じ
  • 思いつかないしこれでいいや・・・

結果

RankHandleProvisional RankProvisional ScoreFinal ScoreLanguage
89nodchip9875.13303.09C++
static int V;
static vector<vector<int> > graph;
static vector<int> edges;

// ------------- class Point -----------------------------
struct P {
	int x, y;
	P() : x(0), y(0) { }
	P(int x1, int y1) : x(x1), y(y1) { }
	inline bool operator == (const P& rh) const {
		return x == rh.x && y == rh.y;
	}
	inline bool operator < (const P& rh) const {
		return x != rh.x ? x < rh.x : y < rh.y;
	}
	inline P& operator -= (const P& rh) {
		x -= rh.x;
		y -= rh.y;
		return *this;
	}
	inline P operator - (const P& rh) const {
		return P(*this) -= rh;
	}
	inline double norm() const {
		return hypot(x, y);
	}
	inline int dot(const P& rh) const {
		return x * rh.x + y * rh.y;
	}
	inline int cross(const P& rh) const {
		return x * rh.y - y * rh.x;
	}
	inline double dist(const P& rh) const {
		return hypot(x - rh.y, y - rh.y);
	}
};

// ------------- class Edge ------------------------------
struct Edge {
	const P& p1;
	const P& p2;
	const P vect;    //vector p1 -> p2
	int minX;
	int maxX;
	int minY;
	int maxY;
	inline Edge(const P& p1n, const P& p2n) : p1(p1n), p2(p2n), vect(p2n - p1n)
	{
		if (p1n.x < p2n.x) {
			minX = p1n.x;
			maxX = p2n.x;
		} else {
			minX = p2n.x;
			maxX = p1n.x;
		}

		if (p1n.y < p2n.y) {
			minY = p1n.y;
			maxY = p2n.y;
		} else {
			minY = p2n.y;
			maxY = p1n.y;
		}
	}
	inline bool eq(double a, double b) const {
		return abs(a-b) < 1e-9;
	}
	// ---------------------------------------------------
	inline bool intersect(const Edge& other) const {
		//do edges "this" and "other" intersect?
		if (other.maxX < minX || maxX < other.minX || other.maxY < minY || maxY < other.minY) {
			return false;
		}

		int den = other.vect.y * vect.x - other.vect.x * vect.y;

		//parallel edges
		if (den==0) {
			if (min(other.dist2(*this),dist2(other)) > 0)
				return false;
			//on the same line - "not intersect" only if one of the vertices is common,
			//and the other doesn't belong to the line
			const double distance = vect.norm() + other.vect.norm();
			if ((p1==other.p1 && eq(p2.dist(other.p2), distance)) ||
				(p1==other.p2 && eq(p2.dist(other.p1), distance)) ||
				(p2==other.p1 && eq(p1.dist(other.p2), distance)) ||
				(p2==other.p2 && eq(p1.dist(other.p1), distance)))
				return false;
			return true;
		}

		int num1 = other.vect.x*(p1.y-other.p1.y)-other.vect.y*(p1.x-other.p1.x);
		int num2 =       vect.x*(p1.y-other.p1.y)-      vect.y*(p1.x-other.p1.x);

		//common vertices
		if (p1 == other.p1 || p1 == other.p2 || p2 == other.p1 || p2 == other.p2)
			return false;

		if (den < 0) {
			den = -den;
			num1 = -num1;
			num2 = -num2;
		}

		return 0 <= num1 && num1 <= den && 0 <= num2 && num2 <= den;
	}
	// ---------------------------------------------------
	inline double dist(const P& p) const {
		//distance from p to the edge
		if (vect.dot(p - p1)<=0)
			return p.dist(p1);            //from p to p1
		if (vect.dot(p - p2)>=0)
			return p.dist(p2);            //from p to p2
		//distance to the line itself
		return abs(-vect.y*p.x+vect.x*p.y+p1.x*p2.y-p1.y*p2.x)/vect.norm();
	}
	// ---------------------------------------------------
	inline double dist2(const Edge& other) const {
		//distance from the closest of the endpoints of "other" to "this"
		return min(dist(other.p1), dist(other.p2));
	}
};

//TODO:状態を表す型/構造体を作成する
class STATE
{
public:
	explicit STATE();
	void next();
	void prev();
	double energy();
	const P* getPositions() const { return positions; }
private:
	int countIntersectionFrom(int a) const;

	P positions[128];
	P previousPosition;
	int previousIndex;
	int currentEnergy;
	int previousEnergy;
	set<P> positionSet;
};

class SimulatedAnnealing
{
public:
	//TODO:コンストラクタに必要な引数を追加する
	SimulatedAnnealing();
	STATE run();
private:
	static const int TIME_LIMIT;
	double calculateProbability(double score, double scoreNeighbor, double temperature);
};

SimulatedAnnealing::SimulatedAnnealing()
{
}

//TODO:計算時間をミリ秒単位で設定する
const int SimulatedAnnealing::TIME_LIMIT = 9;

// http://www.jstatsoft.org/v08/i14/xorshift.pdf
unsigned long xor128() {     // 周期は 2^128-1
    static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned long t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

STATE SimulatedAnnealing::run()
{
	const int timeStart = (int)time(NULL);
	const int timeEnd = timeStart + TIME_LIMIT;
	STATE state;
	double energy = state.energy();
	STATE result = state;
	double minEnergy = energy;
	int counter = 0;
	int timeCurrent;
	while ((timeCurrent = time(NULL)) < timeEnd){
		for (int loop = 0; loop < 1000; ++loop) {
			state.next();
			const double energyNeighbor = state.energy();
			const double random = xor128() * 0.00000000023283064365386962890625;
			const double probability = calculateProbability(energy, energyNeighbor, (double)(timeEnd - timeCurrent) / (double)(timeEnd - timeStart) + 1e-8);
			if (random < probability){
				//Accept
				if (minEnergy > energyNeighbor) {
					//fprintf(stderr, "minEnergy updated! %.5lf -> %.5lf\n", minEnergy, energyNeighbor);
					minEnergy = energyNeighbor;
					result = state;
				}
				//fprintf(stderr, "Accepted %.5lf -> %.5lf : minEnergy=%.5lf\n", energy, energyNeighbor, minEnergy);
				energy = energyNeighbor;
			} else {
				//Decline
				state.prev();
				//fprintf(stderr, "Declined\n");
			}
			++counter;
		}
	}
	fprintf(stderr, "counter:%d minEnergy:%.5lf\n", counter, minEnergy);
	return result;
}

double SimulatedAnnealing::calculateProbability(double energy, double energyNeighbor, double temperature)
{
	if (energyNeighbor < energy){
		return 1;
	} else {
		const double result = exp((energy - energyNeighbor) / temperature * 1e-1);
		//fprintf(stderr, "%lf -> %lf * %lf = %lf\n", energy, energyNeighbor, temperature, result);
		return result;
	}
}

//TODO:初期状態を作る関数を記述する
STATE::STATE()
{
	for (int v = 0; v < V; ++v) {
		P p;
		do {
			p.x = xor128() % 700;
			p.y = xor128() % 700;
		} while (positionSet.count(p));
		positions[v] = p;
		positionSet.insert(p);
	}

	const int M = edges.size();
	int counter = 0;
	for (int i = 0; i < M; i += 2) {
		const int a = edges[i];
		const int b = edges[i + 1];
		Edge edge0(positions[a], positions[b]);

		for (int j = i + 2; j < M; j += 2) {
			const int c = edges[j];
			const int d = edges[j + 1];
			if (a == c || a == d || b == c || b == d) {
				continue;
			}

			Edge edge1(positions[c], positions[d]);

			if (edge0.intersect(edge1)) {
				++counter;
			}
		}
	}

	currentEnergy = counter;
}

//TODO:遷移後の状態を作る関数を記述する
void STATE::next()
{
	previousEnergy = currentEnergy;
	previousIndex = xor128() % V;
	currentEnergy -= countIntersectionFrom(previousIndex);

	previousPosition = positions[previousIndex];
	positionSet.erase(previousPosition);

	P p;
	do {
		p.x = xor128() % 700;
		p.y = xor128() % 700;
	} while (positionSet.count(p));
	positionSet.insert(p);
	positions[previousIndex] = p;

	currentEnergy += countIntersectionFrom(previousIndex);
}

//TODO:遷移前の状態を作る関数を記述する
void STATE::prev()
{
	currentEnergy = previousEnergy;
	positionSet.erase(positions[previousIndex]);
	positions[previousIndex] = previousPosition;
	positionSet.insert(previousPosition);
}

//TODO:状態のエネルギーを計算する関数を記述する
//(状態はエネルギーの低い所に遷移する点に注意する)
double STATE::energy()
{
	return currentEnergy;
}

int STATE::countIntersectionFrom(int a) const {
	int counter = 0;
	const P* positions = this->positions;
	for (vector<int>::iterator it = graph[a].begin(), itEnd = graph[a].end(); it != itEnd; ++it) {
		const int b = *it;

		Edge edge0(positions[a], positions[b]);

		for (int c = 0; c < V; ++c) {
			if (c == a || c == b) {
				continue;
			}

			for (vector<int>::iterator jt = graph[c].begin(), jtEnd = graph[c].end(); jt != jtEnd; ++jt) {
				const int d = *jt;

				if (d < c || d == a || d == b) {
					continue;
				}

				Edge edge1(positions[c], positions[d]);
				if (edge0.intersect(edge1)) {
					++counter;
				}
			}
		}
	}
	return counter;
}

struct Planarity {
	vector <int> untangle(int V, vector <int> edges) {
		::V = V;
		::edges = edges;
		::graph.resize(V);
		for (int i = 0; i < edges.size(); i += 2) {
			const int a = edges[i];
			const int b = edges[i + 1];
			graph[a].push_back(b);
			graph[b].push_back(a);
		}
		for (vector<vector<int> >::iterator it = graph.begin(), itEnd = graph.end(); it != itEnd; ++it) {
			sort(it->begin(), it->end());
		}


		STATE state = SimulatedAnnealing().run();
		vector<int> result;
		for (int i = 0; i < V; ++i) {
			result.push_back(state.getPositions()[i].x);
			result.push_back(state.getPositions()[i].y);
		}
		return result;
	}
};

SRM 475 22:14 SRM 475 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SRM 475 - nodchipのTopCoder日記 SRM 475 - nodchipのTopCoder日記 のブックマークコメント

Easy 300 RabbitStepping

  • シミュレーション・・・?
  • そんでメモ探・・・?
  • 嫌な予感がするけどとりあえず書いてみる・・・。
  • TLEしたorz
  • いやな予感が当たったorz

結果: Opened

  • @kinaba先生が偶奇を見れば良いとつぶやいている
  • もしや偶奇のウサギの個数の偶奇を見れば良いのか?
  • 書いてみた
  • 通ったorz

以下はPracticeで通ったものです

class RabbitStepping {
public:
	double getExpected(string field, int r) {
		vector<int> v(field.size());
		fill(v.begin(), v.begin() + r, 1);
		sort(ALL(v));

		int total = 0;
		int rabit = 0;
		do {
			int even = 0;
			int odd = 0;
			REP(i, v.size()) {
				if (i % 2 == 0) {
					even ^= v[i];
				} else {
					odd ^= v[i];
				}
			}
			++total;
			rabit += even;
			rabit += odd;
		} while (next_permutation(ALL(v)));

		return rabit / (double)total;
	}
}

Middle 600 RabbitIncreasing

  • とりあえず紙に書き出してみようか
  • フィボナッチ数臭がする・・・
  • 行列のN乗じゃね?
  • (N+1)/2の部分が分からんorz

結果: Opened

Hard 900 RabbitProgramming

  • 謎・・・orz

Challenge Phase

  • 今回は撃墜祭になるに違いない!
  • とりあえず再帰を見たら投げてしまえ!
  • いた!
  • 投げた!
  • ・・・失敗orz
  • -25.0でfinishですorz

System Test

x x x -25.0 2132->1966 せっかく貯めたレーティングが・・・orz

ゲスト



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