Hatena::Grouptopcoder

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

 | 

2014-05-10

AtCoder Beginner Contest #008 23:18 AtCoder Beginner Contest #008 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Beginner Contest #008 - nodchipのTopCoder日記 AtCoder Beginner Contest #008 - nodchipのTopCoder日記 のブックマークコメント

A - アルバム

  • 引き算
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);

	int S, T;
	cin >> S >> T;
	cout << T - S + 1 << endl;
}

B - 投票

  • mapに突っ込んでごにょごにょ
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);
	int N;
	cin >> N;
	map<string, int> votes;
	REP(n, N) {
		string name;
		cin >> name;
		votes[name]++;
	}

	int bestVotes = 0;
	string bestName;
	for (const auto& v : votes) {
		if (bestVotes < v.second) {
			bestVotes = v.second;
			bestName = v.first;
		}
	}
	cout << bestName << endl;
}

C - コイン

  • とりあえず99点はnext_permutation()でいける
  • 100点はどうやるんだろう・・・
  • 確率と期待値と数え上げは本当に苦手・・・orz
  • これもしかして1枚ずつ独立に計算できるのかなぁ?
  • ・・・
  • あるコインに着目して、そのコインより左にある枚数と、そのコインより左にある割り切れる数字を持ったコインの枚数とかで、掛け算しまくる感じ・・・?
  • うむむ・・・
  • 多分大丈夫だと思う
  • Accepted
double C[128][128];
double BIKKURI[128];

int main() {
	std::ios::sync_with_stdio(false);

	REP(i, 128) {
		C[i][0] = 1.0;
	}
	for (int i = 1; i < 128; ++i) {
		for (int j = 1; j < 128; ++j) {
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
	}

	BIKKURI[0] = 1.0;
	for (int i = 1; i < 128; ++i) {
		BIKKURI[i] = BIKKURI[i - 1] * i;
	}

	int N;
	cin >> N;
	vector<int> coins;
	REP(n, N) {
		int coin;
		cin >> coin;
		coins.push_back(coin);
	}

	double sum = 0.0;
	REP(base, N) {
		int counter = 0;
		REP(other, N) {
			if (base == other) {
				continue;
			}

			if (coins[base] % coins[other] == 0) {
				++counter;
			}
		}

		for (int left = 0; left <= N - 1; ++left) {
			int right = N - 1 - left;
			for (int leftHit = 0; leftHit <= counter && leftHit <= left; ++leftHit) {
				if (leftHit % 2 != 0) {
					continue;
				}
				int rightHit = counter - leftHit;
				if (rightHit > right) {
					continue;
				}

				sum += C[left][leftHit] * C[right][rightHit] * BIKKURI[counter] * BIKKURI[N - counter - 1];
			}
		}
	}


	printf("%.20f\n", sum / BIKKURI[N]);
}

D - 金塊ゲーム

  • 80点は全通り試すだけ・・・
  • 99点->100点は座標圧縮かなぁ・・・
  • 80点->99点が素で分からない。
  • 諦めて苦肉の策で焼き鈍そう・・・orz
  • いい加減バカの一つ覚えから抜け出したいorz
  • 80点のコードを焼きなましライブラリにつなげる
  • 近傍状態は異なる2つの順序を入れ替えて作る
  • WA・・・
  • 諦めきれないので焼きなまし温度パラメーターを変えて複数サブミットしてみる
  • 温度パラメーター=0.040で99点出た!
  • ごめんなさい。本当にごめんなさい。
const int DX[] = { 0, 0, 1, -1 };
const int DY[] = { 1, -1, 0, 0 };

vector<pair<int, int> > initialMachines;
int N;

vector<int> space(const vector<int>& xs, int X) {
	vector<int> ret;
	ret.push_back(xs[0] - 1);
	ret.push_back(1);
	REP(i, xs.size() - 1) {
		ret.push_back(xs[i + 1] - xs[i] - 1);
		ret.push_back(1);
	}
	ret.push_back(X - xs.back());
	return ret;
}

int spacesX[64];
int spacesY[64];
ll calculate(const vector<pair<int, int> >& machines, int W, int H) {
	bool memo[64][64];
	CLEAR(memo);

	int counter = 0;
	for (const auto& machine : machines) {
		counter += spacesX[machine.first] * spacesY[machine.second];
		memo[machine.first][machine.second] = true;

		REP(dir, 4) {
			int x = machine.first + DX[dir];
			int y = machine.second + DY[dir];
			while (0 <= x && x < N * 2 + 1 && 0 <= y && y < N * 2 + 1 && !memo[x][y]) {
				counter += spacesX[x] * spacesY[y];
				memo[x][y] = true;
				x += DX[dir];
				y += DY[dir];
			}
		}
	}

	return counter;
}

#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();
public:
	vector<pair<int, int> > machines;
	int src, dst;
};

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

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

//TODO:初期状態を作る関数を記述する
STATE::STATE() {
	machines = initialMachines;
}

//TODO:遷移後の状態を作る関数を記述する
void STATE::next() {
	if (machines.size() == 1) {
		return;
	}

	src = xor128() % machines.size();
	do {
		dst = xor128() % machines.size();
	} while (src == dst);
	swap(machines[src], machines[dst]);
}

//TODO:遷移前の状態を作る関数を記述する
//     高々一つ前の状態までに戻れれば良い
void STATE::prev() {
	if (machines.size() == 1) {
		return;
	}

	swap(machines[src], machines[dst]);
}

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

int main() {
	std::ios::sync_with_stdio(false);

	ifstream cin("C:\\cygwin\\home\\nodchip\\procon\\abc008_4.2.in.txt");

	int W, H;
	cin >> W >> H;

	cin >> N;
	vector<pair<int, int> > machines;
	vector<int> xs;
	vector<int> ys;
	REP(n, N) {
		int x, y;
		cin >> x >> y;
		machines.push_back(MP(x, y));
		xs.push_back(x);
		ys.push_back(y);
	}

	sort(ALL(xs));
	sort(ALL(ys));

	vector<int> spacesX = space(xs, W);
	vector<int> spacesY = space(ys, H);

	REP(i, spacesX.size()) {
		::spacesX[i] = spacesX[i];
	}
	REP(i, spacesY.size()) {
		::spacesY[i] = spacesY[i];
	}

	for (auto& machine : machines) {
		machine.first = distance(xs.begin(), find(ALL(xs), machine.first)) * 2 + 1;
		machine.second = distance(ys.begin(), find(ALL(ys), machine.second)) * 2 + 1;
	}
	initialMachines = machines;

	STATE state = SimulatedAnnealing().run();
	cout << calculate(state.machines, N * 2 + 1, N * 2 + 1) << endl;

	//ll bestCounter = calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1);
	//bool updated = true;
	//while (updated) {
	//	updated = false;

	//	for (int n = 0; n + 1 < N; ++n) {
	//		swap(machines[n], machines[n + 1]);
	//		ll counter = calculate(machines, compressedBase, N * 2 + 1, N * 2 + 1);
	//		if (bestCounter < counter) {
	//			bestCounter = counter;
	//			updated = true;
	//		}
	//		else {
	//			swap(machines[n], machines[n + 1]);
	//		}
	//	}
	//}

	//cout << bestCounter << endl;
}

結果

順位ユーザ名アルバム投票コイン金塊ゲーム得点 / Total
19nodchip100 00:36100 02:24100 (1) 104:3999 (15) 87:48399 (16)184:39

どうにかこうにか1ページ目に入ることができました。Dは動的計画法だそうです。動的計画法は苦手です。

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