Hatena::Grouptopcoder

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

 | 

2014-05-17

TCO'14 Algorithm Round 2A 02:50 TCO'14 Algorithm Round 2A - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - TCO'14 Algorithm Round 2A - nodchipのTopCoder日記 TCO'14 Algorithm Round 2A - nodchipのTopCoder日記 のブックマークコメント

Easy 250 SixteenBricks

  • 多分DPだよね
  • ・・・
  • 計算量どんな感じだろう
  • 1列ずつやると_{16}P_{4} 2^{16}状態できるので・・・
  • 全然終わらなそう
  • どうしよう・・・
  • ・・・
  • 焼鈍しちゃえ
  • Passed System Test
  • 通るんだ・・・
#ifdef _MSC_VER
#include <Windows.h>
ll getTime() {
	return GetTickCount();
}
#else
#include <sys/time.h>
ll getTime() {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	ll result = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
	//cerr << result << endl;
	return result;
}
#endif

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


int height[16];


//TODO:状態を表す型/構造体を作成する
class STATE {
public:
	//TODO:コンストラクタに必要な引数を追加する
	explicit STATE();
	void next();
	void prev();
	double energy();
private:
	int height[16];
	int s0, s1, s2;
	int swapType;
};

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

//TODO:コンストラクタに必要な引数を追加する
SimulatedAnnealing::SimulatedAnnealing() {
}

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

STATE SimulatedAnnealing::run() {
	const ll timeStart = getTime();
	const ll timeEnd = timeStart + TIME_LIMIT;
	STATE state;
	double energy = state.energy();
	STATE result = state;
	double minEnergy = energy;
	int counter = 0;
	ll timeCurrent;
	while ((timeCurrent = getTime()) < timeEnd){
		REP(loop, 100) {
			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) {
#ifdef _MSC_VER
					fprintf(stderr, "minEnergy updated! %.5lf -> %.5lf\n", minEnergy, energyNeighbor);
#endif
					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-9) * 0.6);
		//fprintf(stderr, "%lf -> %lf * %lf = %lf\n", energy, energyNeighbor, temperature, result);
		return result;
	}
}

//TODO:初期状態を作る関数を記述する
STATE::STATE() {
	copy(::height, ::height + 16, this->height);
}

//TODO:遷移後の状態を作る関数を記述する
void STATE::next() {
	swapType = xor128() % 2;
	if (swapType == 0) {
		s0 = xor128() % 16;
		do {
			s1 = xor128() % 16;
		} while (s0 == s1);
		swap(height[s0], height[s1]);
	}
	else {
		s0 = xor128() % 16;
		do {
			s1 = xor128() % 16;
		} while (s0 == s1);
		do {
			s2 = xor128() % 16;
		} while (s0 == s2 || s1 == s2);
		swap(height[s0], height[s1]);
		swap(height[s1], height[s2]);
	}
}

//TODO:遷移前の状態を作る関数を記述する
//     高々一つ前の状態までに戻れれば良い
void STATE::prev() {
	if (swapType == 0) {
		swap(height[s0], height[s1]);
	}
	else {
		swap(height[s1], height[s2]);
		swap(height[s0], height[s1]);
	}
}

//TODO:状態のエネルギーを計算する関数を記述する
//     状態はエネルギーの低い所に遷移する点に注意する
double STATE::energy() {
	int sum = height[0] + height[1] + height[2] + height[3] +
		height[0] + height[4] + height[8] + height[12] +
		height[3] + height[7] + height[11] + height[15] +
		height[12] + height[13] + height[14] + height[15] + 16;
	for (int i = 0; i < 16; ++i) {
		if ((i + 1) % 4 != 0) {
			sum += abs(height[i] - height[i + 1]);
		}
		if (i + 4 < 16) {
			sum += abs(height[i] - height[i + 4]);
		}
	}
	return -sum;
}

class SixteenBricks {
public:

	int maximumSurface(vector <int> height) {
		copy(ALL(height), ::height);

		int result = (int)(-SimulatedAnnealing().run().energy() + 0.5);
		return result;
	}
}

Medium 500 NarrowPassage

  • 並びを変えずに平行移動だけする狼がいた場合と、全員回廊の端に移動する場合で場合分けかな?
  • ・・・
  • サンプル合わない
  • 全員回廊の橋に移動する場合は何匹か入れ替えないとダメなのかなぁ
  • ・・・
  • よくわからない
  • Opened

Hard 1000 TreePuzzle

  • わかりませんでした

Challenge Phase

  • 500で並びを変えずに平行移動する狼がいた場合を忘れている人を探す。
  • そんな人いなかった。

System Test

o-- 160.87 346位 1889->1916 1900台に戻ってきました。2000目指します。

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