提出 #67393646

---

ソースコード 拡げる

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

class XorShift {
	unsigned int x, y, z, w, t;
public:
	XorShift() {
		x = 133553533;
		y = 314867339;
		z = 664298413;
		w = 999999937;
		t = 0;
	}
	unsigned int rand() {
		t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w & 0x7fffffff;
	}
};

XorShift xs;
constexpr int N = 40;
int M;
vector<vector<int>>wall(N + 2, vector<int>(N + 2));

long double best_score = 0;
vector<pair<int, int>>best_ans;

int dir[] = { 1,0,-1,0,1,0,-1 };

pair<int, int>Place(vector<vector<int>>& wall, int y, int x, int dy, int dx) {
	while (wall[y + dy][x + dx] == 0) {
		y += dy;
		x += dx;
	}
	return { y, x };
}

long double current_place_flavor = -2e3;
long double neighbour_flavor = 0.4;
long double far_flavor = -1;

vector<vector<long double>>CalculateNextP(vector<vector<long double>>p, vector<vector<int>>& wall) {
	vector<vector<long double>>np(N + 2, vector<long double>(N + 2));
	for (int i = 1; i <= N; i++) {
		long double add = 0;
		int x = 1;
		for (int j = 1; j <= N + 1; j++) {
			if (wall[i][j]) {
				np[i][j - 1] += add / 4;
				add = 0;
				x = j + 1;
			}
			else {
				np[i][x] += p[i][j] / 4;
				add += p[i][j];
			}
		}
	}
	for (int j = 1; j <= N; j++) {
		long double add = 0;
		int y = 1;
		for (int i = 1; i <= N + 1; i++) {
			if (wall[i][j]) {
				np[i - 1][j] += add / 4;
				add = 0;
				y = i + 1;
			}
			else {
				add += p[i][j];
				np[y][j] += p[i][j] / 4;
			}
		}
	}
	return np;
}

long double CalculateNeighbourFlavor(vector<vector<long double>>& p, vector<vector<int>>& wall, int y, int x) {
	long double ret = 0;
	for (int d = 0; d < 4; d++) {
		ret += p[y + dir[d]][x + dir[d + 1]] * neighbour_flavor;
		auto n = Place(wall, y, x, dir[d], dir[d + 1]);
		if (abs(y - n.first) + abs(x - n.second) > 1) {
			ret += p[n.first][n.second] * far_flavor;
		}
	}
	return ret;
}

vector<vector<long double>>InitP() {
	vector<vector<long double>>p(N + 2, vector<long double>(N + 2));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (wall[i][j])continue;
			p[i][j] = 1;
			p[i][j] /= N * N - M;
		}
	}
	return p;
}

clock_t st;

pair<vector<pair<int, int>>, long double>Build() {
	auto p = InitP();
	long double add = 1;
	auto current_wall = wall;
	vector<pair<int, int>>ans;
	long double score = 0;
	for (int loop = 0; loop < N * N - M; loop++) {
		auto np = CalculateNextP(p, current_wall);
		long double best_flavor = -1e9;
		pair<int, int> best_place = { 0,0 };
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (current_wall[i][j])continue;
				long double current_flavor = current_place_flavor * np[i][j];
				current_flavor += CalculateNeighbourFlavor(np, current_wall, i, j);
				if (best_flavor < current_flavor) {
					best_flavor = current_flavor;
					best_place = { i,j };
				}
			}
		}
		add -= np[best_place.first][best_place.second];
		score += add;
		np[best_place.first][best_place.second] = 0;
		p = np;
		ans.push_back(best_place);
		current_wall[best_place.first][best_place.second] = 1;
	}
	return { ans,score };
}

void Init() {
	int dummy;
	cin >> dummy;
	st = clock();
	cin >> M;
	for (int i = 0; i < N + 2; i++) {
		wall.front()[i] = wall[i].front() = wall.back()[i] = wall[i].back() = 1;
	}
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < N; j++) {
			if (s[j] == '#') {
				wall[i + 1][j + 1] = 1;
			}
		}
	}
	// 広場+階段みたいな構造が強そう
	// うそっぽい

	vector<pair<int, int>>ans;
	long double score = 0;
	tie(best_ans, best_score) = Build();
	current_place_flavor = -1e3;
	neighbour_flavor = 0.4;
	far_flavor = -1;
	tie(ans, score) = Build();
	if (best_score < score) {
		best_score = score;
		best_ans = ans;
	}
	current_place_flavor = -2e3;
	neighbour_flavor = 0.3;
	far_flavor = -1;
	tie(ans, score) = Build();
	if (best_score < score) {
		best_score = score;
		best_ans = ans;
	}
	current_place_flavor = -1e3;
	neighbour_flavor = 0.3;
	far_flavor = -1;
	tie(ans, score) = Build();
	if (best_score < score) {
		best_score = score;
		best_ans = ans;
	}
}

long double CalculateScore(vector<pair<int, int>>ans) {
	auto current_wall = wall;
	auto p = InitP();
	long double add = 1;
	long double score = 0;
	for (auto i : ans) {
		auto np = CalculateNextP(p, current_wall);
		add -= np[i.first][i.second];
		score += add;
		np[i.first][i.second] = 0;
		p = np;
		current_wall[i.first][i.second] = 1;
	}
	return score;
}

void Solve() {
	int cnt = 0;
	auto ans = best_ans;
	while (1) {
		cnt++;
		if (cnt % 1 == 0) {
			auto ed = clock();
			if ((ed - st) * 1000 / CLOCKS_PER_SEC > 1900) {
				cerr << cnt << endl;
				break;
			}
		}
		int a = xs.rand() % best_ans.size();
		int b = xs.rand() % (best_ans.size() - 1);
		b += a;
		b %= best_ans.size();
		if (a > b)swap(a, b);
		swap(ans[a], ans[b]);
		auto current_score = CalculateScore(ans);
		//cerr << current_score << endl;
		if (best_score < current_score) {
			best_score = current_score;
			best_ans = ans;
			cerr << best_score << endl;
		}
		else {
			swap(ans[a], ans[b]);
		}
	}
}

void Output() {
	for (auto i : best_ans) {
		cout << i.first - 1 << " " << i.second - 1 << endl;
	}
	cerr << best_score / (N * N - M - 1) << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	Init();
	Solve();
	Output();
}

提出情報

ジャッジ結果