結果
問題 | No.5002 stick xor |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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;}