結果

問題 No.5002 stick xor
ユーザー pirozhki
提出日時 2018-05-29 12:52:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 891 ms / 1,000 ms
コード長 4,609 bytes
コンパイル時間 29,526 ms
実行使用メモリ 1,760 KB
スコア 27,273
最終ジャッジ日時 2018-05-29 12:53:28
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <type_traits>

using namespace std;

enum Dir {
	UP,
	DOWN,
	RIGHT,
	LEFT
};

struct Param {
	int x;
	int y;
	int k;
	Dir d;
};

void PrintParam(const Param& param) {
	int x1 = param.x;
	int y1 = param.y;
	int x2 = param.x;
	int y2 = param.y;

	switch (param.d) {
	case Dir::UP:
		y1 -= param.k - 1;
		break;
	case Dir::DOWN:
		y2 += param.k - 1;
		break;
	case Dir::RIGHT:
		x2 += param.k - 1;
		break;
	case Dir::LEFT:
		x1 -= param.k - 1;
		break;
	}
	cout << y1 + 1 << " " << x1 + 1 << " " << y2 + 1 << " " << x2 + 1 << endl;
}

void PrintArray(const vector<bool>& arr, int n) {
	for (unsigned int i = 0; i < arr.size(); i++) {
		cout << arr[i] << " ";
		if ((i + 1) % n == 0) {
			cout << endl;
		}
	}
	cout << endl;
}

void Flip(vector<bool>& arr, int n, const Param& param) {
	for (int i = 0; i < param.k; i++) {
		switch (param.d) {
		case Dir::UP:
			arr[(param.y - i) * n + param.x].flip();
			break;
		case Dir::DOWN:
			arr[(param.y + i) * n + param.x].flip();
			break;
		case Dir::RIGHT:
			arr[param.y * n + (param.x + i)].flip();
			break;
		case Dir::LEFT:
			arr[param.y * n + (param.x - i)].flip();
			break;
		}
	}
}

int Evaluate(vector<bool> arr, int n, const vector<Param>& params, bool print = false) {
	for (const Param& param : params) {
		Flip(arr, n, param);
		if (print) {
			PrintArray(arr, n);
		}
	}
	return count(arr.begin(), arr.end(), true);
}

bool IsValid(const Param& param, int n) {
	switch (param.d) {
	case Dir::UP:
		if (param.y - (param.k - 1) < 0) {
			return false;
		}
		break;
	case Dir::DOWN:
		if (param.y + (param.k - 1) > n - 1) {
			return false;
		}
		break;
	case Dir::RIGHT:
		if (param.x + (param.k - 1) > n - 1) {
			return false;
		}
		break;
	case Dir::LEFT:
		if (param.x - (param.k - 1) < 0) {
			return false;
		}
		break;
	}
	return true;
}

void Read(vector<Param>& params, vector<bool>& arr, int& n) {
	int k;
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		Param p = { 0 };
		cin >> p.k;
		params.push_back(p);
	}

	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (char& c : s) {
			if (c == '0') {
				arr.push_back(0);
			}
			else {
				arr.push_back(1);
			}
		}
	}
}

template<class T>
class Random
{
public:
	Random(T min, T max) : mt_(rd_()), dist_(min, max) {}

	T operator()() {
		return dist_(mt_);
	}
private:
	random_device rd_;
	mt19937 mt_;
	typename conditional<is_floating_point<T>::value, uniform_real_distribution<>, uniform_int_distribution<>>::type dist_;
};

double Probability(double e1, double e2, double t) {
	if (e1 >= e2) {
		return 1;
	}
	else {
		return exp((e1 - e2) / t);
	}
}

double Temperature(double r) {
	double alpha = 0.5;
	return pow(alpha, r);
}

class Randomize {
public:
	Randomize(int n, int size) : rand_(0, size - 1), rand_pos_(0, n - 1), rand_dir_(0, 3), n_(n) {}

	vector<Param> One(vector<Param>& params) {
		int i = rand_();
		do {
			params[i].d = static_cast<Dir>(rand_dir_());
			params[i].x = rand_pos_();
			params[i].y = rand_pos_();
		} while (!IsValid(params[i], n_));
		return params;
	}

	vector<Param> All(vector<Param>& params) {
		for (Param& param : params) {
			do {
				param.d = static_cast<Dir>(rand_dir_());
				param.x = rand_pos_();
				param.y = rand_pos_();
			} while (!IsValid(param, n_));
		}
		return params;
	}

private:
	int n_;
	Random<int> rand_;
	Random<int> rand_pos_;
	Random<int> rand_dir_;
};

// 黒の数を最小化
vector<Param> Yakinamasi(const vector<Param>& params, const vector<bool>& arr, int n) {
	vector<Param> current_params(params);
	Randomize randomize(n, current_params.size());
	randomize.All(current_params);
	double current_e = Evaluate(arr, n, current_params);
	vector<Param> best_params = current_params;
	double best_e = current_e;

	Random<double> rand(0, 1);
	int goal_e = 0;
	int itr_count = 35000;
	for (int i = 0; i < itr_count; i++) {
		vector<Param> next_params(current_params);
		randomize.One(next_params);
		double next_e = Evaluate(arr, n, next_params);
		if (next_e < best_e) {
			best_params = next_params;
			best_e = next_e;
			//cout << best_e << endl;
			if (best_e <= goal_e) {
				return best_params;
			}
		}
		if (rand() <= Probability(current_e, next_e, Temperature(static_cast<double>(i) / itr_count))) {
			current_params = next_params;
			current_e = next_e;
		}
	}
	return best_params;
}

int main() {
	vector<Param> params;
	vector<bool> arr;
	int n;

	Read(params, arr, n);

	vector<Param> best_params = Yakinamasi(params, arr, n);

	for (const Param& param : best_params) {
		PrintParam(param);
	}

	return 0;
}
0