結果
問題 | 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; }