Submission #169615


Source Code Expand

#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <locale>
#include <memory>
#include <stdexcept>
#include <utility>
#include <string>
#include <fstream>
#include <ios>
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <streambuf>
#include <complex>
#include <numeric>
#include <valarray>
#include <exception>
#include <limits>
#include <new>
#include <typeinfo>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdlib>
#include <cstddef>
#include <cstdarg>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <cwchar>
#include <cwctype>
using namespace std;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
typedef long long ll;
typedef unsigned long long ull;

#define ALL(c) (c).begin(), (c).end()
#define CLEAR(v) memset(v,0,sizeof(v))
#define MP(a,b) make_pair((a),(b))
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define ABS(a) ((a)>0?(a):-(a))
template<class T> T MIN(const T& a, const T& b) { return a < b ? a : b; }
template<class T> T MAX(const T& a, const T& b) { return a > b ? a : b; }
template<class T> void MIN_UPDATE(T& a, const T& b) { if (a > b) a = b; }
template<class T> void MAX_UPDATE(T& a, const T& b) { if (a < b) a = b; }

const int DX[] = { 0, 0, 1, -1 };
const int DY[] = { 1, -1, 0, 0 };

vector<pair<int, int> > initialMachines;
int N;
ll compressedBase[64][64];

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

ll calculate(const vector<pair<int, int> >& machines, ll compressedBase[64][64], int W, int H) {
	ll compressed[64][64];
	bool memo[64][64];
	memcpy(compressed, compressedBase, sizeof(compressed));
	CLEAR(memo);

	ll counter = 0;
	for (const auto& machine : machines) {
		counter += compressed[machine.first][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 += compressed[x][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) * 1.000);
		//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, compressedBase, N * 2 + 1, N * 2 + 1);
}

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

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

	CLEAR(compressedBase);
	REP(x, spacesX.size()) {
		REP(y, spacesY.size()) {
			compressedBase[x][y] = spacesX[x] * spacesY[y];
		}
	}

	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, compressedBase, 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;
}

Submission Info

Submission Time
Task D - 金塊ゲーム
User nodchip
Language C++11 (GCC 4.8.1)
Score 0
Code Size 7965 Byte
Status WA
Exec Time 3928 ms
Memory 1072 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 80 0 / 19 0 / 1
Status
AC × 3
AC × 24
WA × 1
AC × 37
WA × 13
AC × 52
WA × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt
Subtask2 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt, subtask3_15.txt, subtask3_16.txt, subtask3_17.txt, subtask3_18.txt, subtask3_19.txt, subtask3_20.txt, subtask3_21.txt, subtask3_22.txt, subtask3_23.txt, subtask3_24.txt, subtask3_25.txt
Case Name Status Exec Time Memory
sample_01.txt AC 3923 ms 916 KB
sample_02.txt AC 3922 ms 932 KB
sample_03.txt AC 3921 ms 944 KB
subtask1_01.txt AC 3923 ms 1072 KB
subtask1_02.txt AC 3923 ms 884 KB
subtask1_03.txt AC 3923 ms 944 KB
subtask1_04.txt AC 3924 ms 1068 KB
subtask1_05.txt AC 3923 ms 928 KB
subtask1_06.txt AC 3921 ms 928 KB
subtask1_07.txt AC 3922 ms 784 KB
subtask1_08.txt AC 3922 ms 932 KB
subtask1_09.txt AC 3923 ms 1060 KB
subtask1_10.txt AC 3923 ms 880 KB
subtask1_11.txt AC 3922 ms 1060 KB
subtask1_12.txt AC 3921 ms 1048 KB
subtask1_13.txt AC 3921 ms 864 KB
subtask1_14.txt WA 3922 ms 1056 KB
subtask1_15.txt AC 3923 ms 956 KB
subtask1_16.txt AC 3922 ms 1060 KB
subtask1_17.txt AC 3923 ms 1064 KB
subtask1_18.txt AC 3924 ms 964 KB
subtask1_19.txt AC 3923 ms 1056 KB
subtask1_20.txt AC 3923 ms 1060 KB
subtask1_21.txt AC 3923 ms 1064 KB
subtask1_22.txt AC 3924 ms 1060 KB
subtask1_23.txt AC 3922 ms 960 KB
subtask1_24.txt AC 3923 ms 1056 KB
subtask1_25.txt AC 3923 ms 956 KB
subtask2_01.txt AC 3923 ms 1060 KB
subtask2_02.txt AC 3923 ms 864 KB
subtask2_03.txt AC 3923 ms 960 KB
subtask2_04.txt WA 3923 ms 1056 KB
subtask2_05.txt WA 3924 ms 952 KB
subtask2_06.txt WA 3923 ms 1060 KB
subtask2_07.txt AC 3922 ms 1052 KB
subtask2_08.txt AC 3923 ms 960 KB
subtask2_09.txt WA 3922 ms 1048 KB
subtask2_10.txt AC 3922 ms 944 KB
subtask2_11.txt WA 3928 ms 1060 KB
subtask2_12.txt AC 3924 ms 1060 KB
subtask2_13.txt AC 3924 ms 1068 KB
subtask2_14.txt AC 3922 ms 1044 KB
subtask2_15.txt AC 3922 ms 956 KB
subtask2_16.txt WA 3922 ms 1056 KB
subtask2_17.txt WA 3921 ms 948 KB
subtask2_18.txt AC 3921 ms 860 KB
subtask2_19.txt AC 3922 ms 960 KB
subtask2_20.txt WA 3921 ms 960 KB
subtask2_21.txt AC 3924 ms 1068 KB
subtask2_22.txt WA 3924 ms 960 KB
subtask2_23.txt WA 3923 ms 1056 KB
subtask2_24.txt WA 3924 ms 1064 KB
subtask2_25.txt WA 3923 ms 956 KB
subtask3_01.txt AC 3923 ms 924 KB
subtask3_02.txt WA 3923 ms 928 KB
subtask3_03.txt AC 3923 ms 928 KB
subtask3_04.txt AC 3923 ms 1056 KB
subtask3_05.txt AC 3922 ms 960 KB
subtask3_06.txt AC 3923 ms 928 KB
subtask3_07.txt WA 3923 ms 804 KB
subtask3_08.txt AC 3922 ms 932 KB
subtask3_09.txt WA 3924 ms 932 KB
subtask3_10.txt AC 3920 ms 800 KB
subtask3_11.txt WA 3923 ms 928 KB
subtask3_12.txt WA 3923 ms 1052 KB
subtask3_13.txt AC 3922 ms 804 KB
subtask3_14.txt AC 3921 ms 800 KB
subtask3_15.txt WA 3922 ms 916 KB
subtask3_16.txt AC 3923 ms 808 KB
subtask3_17.txt WA 3921 ms 796 KB
subtask3_18.txt AC 3923 ms 932 KB
subtask3_19.txt WA 3923 ms 924 KB
subtask3_20.txt AC 3921 ms 800 KB
subtask3_21.txt AC 3923 ms 920 KB
subtask3_22.txt WA 3922 ms 920 KB
subtask3_23.txt AC 3922 ms 928 KB
subtask3_24.txt AC 3921 ms 928 KB
subtask3_25.txt WA 3924 ms 920 KB