Hatena::Grouptopcoder

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

 | 

2014-02-26

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

Easy 250 TheMatrix

  • どこかで見たことあるような・・・
  • 先に市松模様でマスクしてから面積最大の長方形を見つける
  • そして反転してもう一度
  • Passed System Test
class TheMatrix {
public:
	int R, C;
	bool b[128][128];
	int go() {
		static int acc[128][128];
		CLEAR(acc);
		REP(r, R) {
			for (int c = C - 1; c >= 0; --c) {
				if (b[r][c]) {
					acc[r][c] = acc[r][c + 1] + 1;
				}
			}
		}
		int best = 0;
		REP(c, C) REP(r, R) {
			int columnBest = INT_MAX;
			for (int rr = r; rr < R; ++rr) {
				MIN_UPDATE(columnBest, acc[rr][c]);
				MAX_UPDATE(best, (rr - r + 1) * columnBest);
			}
		}
		return best;
	}
	void inverse() {
		REP(r, R) REP(c, C) {
			b[r][c] ^= true;
		}
	}
	int MaxArea(vector <string> board) {
		R = board.size();
		C = board[0].size();
		REP(r, R) REP(c, C) {
			b[r][c] = board[r][c] == '1';
			if ((r + c) % 2 == 0) {
				b[r][c] ^= true;
			}
		}

		int result = go();
		inverse();
		MAX_UPDATE(result, go());
		return result;
	}

	

};

Midium 550 AlbertoTheAviator

  • わからん・・・
  • とりあえず焼きなまそうか
  • 巡回セールスマン解くのと同じ要領で、適当に並べたあと先頭から見ていって取れるやつを取る
  • サンプル通った
  • ランダム入力1つ作って入れて出力が安定した
  • 温度調整が難しいけど勘で適当に・・・
  • Passed System Test
  • びっくりした。正直びっくりした。
int N;
int F;
int duration[64];
int refuel[64];

#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)));
}

//TODO:状態を表す型/構造体を作成する
class STATE {
public:
	//TODO:コンストラクタに必要な引数を追加する
	explicit STATE();
	void next();
	void prev();
	double energy();

	int order[64];
	int answer;
	int swapped0;
	int swapped1;
	int lastAnswer;
};

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 = 1900;

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) * 1.0);
		//fprintf(stderr, "%lf -> %lf * %lf = %lf\n", energy, energyNeighbor, temperature, result);
		return result;
	}
}

//TODO:初期状態を作る関数を記述する
STATE::STATE() {
	REP(n, N) {
		order[n] = n;
	}

	answer = 0;
	int f = F;
	REP(n, N) {
		int missionIndex = order[n];
		if (duration[missionIndex] > f) {
			continue;
		}
		f -= duration[missionIndex];
		f += refuel[missionIndex];
		++answer;
	}
}

//TODO:遷移後の状態を作る関数を記述する
void STATE::next() {
	lastAnswer = answer;
	int swapped0 = xor128() % N;
	int swapped1;
	do {
		swapped1 = xor128() % N;
	} while (swapped0 == swapped1);
	swap(order[swapped0], order[swapped1]);
	this->swapped0 = swapped0;
	this->swapped1 = swapped1;

	answer = 0;
	int f = F;
	REP(n, N) {
		int missionIndex = order[n];
		if (duration[missionIndex] > f) {
			continue;
		}
		f -= duration[missionIndex];
		f += refuel[missionIndex];
		++answer;
	}
}

//TODO:遷移前の状態を作る関数を記述する
//     高々一つ前の状態までに戻れれば良い
void STATE::prev() {
	answer = lastAnswer;
	swap(order[swapped0], order[swapped1]);
}

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

class AlbertoTheAviator {
public:
	int MaximumFlights(int F, vector <int> duration, vector <int> refuel) {

		//vector<int> a, b;
		//REP(i, 50) {
		//	a.push_back(xor128() % 5001);
		//	b.push_back(xor128() % 5001);
		//	if (a.back() < b.back()) {
		//		swap(a.back(), b.back());
		//	}
		//}
		//copy(ALL(a), ostream_iterator<int>(cout, ","));
		//cout << endl;
		//copy(ALL(b), ostream_iterator<int>(cout, ","));
		//cout << endl;


		::N = duration.size();
		::F = F;
		copy(ALL(duration), ::duration);
		copy(ALL(refuel), ::refuel);

		if (::N == 1) {
			if (F >= duration[0]) {
				return 1;
			}
			else {
				return 0;
			}
		}

		int result = SimulatedAnnealing().run().answer;
		return result;
	}
}

Hard 900 MiningGoldHard

  • 分かりませんでした

Challenge Phase

  • 250でO(N^4)の人を探しましたが見つかりませんでした

System Test

oxx 45位 1722->1844 焼きなましが通るとは思っていませんでした。本当に思っていませんでした。

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