namespace atcoder {} #ifdef LOCAL #define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; #else #define NDEBUG #define dbg(x) true; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #ifdef GTEST #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef PERF #include #endif using namespace std; using namespace atcoder; #define fast_io \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define ll long long int #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define reps(i, n) for (int i = 1; i <= (int)(n); i++) #define REP(i, n) for (int i = n - 1; i >= 0; i--) #define REPS(i, n) for (int i = n; i > 0; i--) #define MOD (long long int)(1e9 + 7) #define INF (int)(1e9) #define LINF (long long int)(1e18) #define chmax(a, b) a = (((a) < (b)) ? (b) : (a)) #define chmin(a, b) a = (((a) > (b)) ? (b) : (a)) #define ALL(v) v.begin(), v.end() typedef pair Pii; typedef pair Pll; constexpr double PI = acos(-1); #ifdef NDEBUG #define CHECK(v1, op, v2) #else #define CHECK(v1, op, v2) \ if (!((v1)op(v2))) { \ cerr << "ERROR:" << (v1) << " " << (v2) << endl; \ assert((v1)op(v2)); \ } #endif long double nCr(const int n, const int r) { long double ret = 1; rep(t, r) { ret *= (n - t); ret /= (r - t); } return ret; } template string to_string(const vector& vec) { string ret = ""; rep(i, vec.size()) { ret += vec[i].to_string(); if (i + 1 != vec.size()) { ret += ","; } } return ret; } template ostream& operator<<(ostream& os, const vector& vec) { os << to_string(vec); return os; } uint32_t xorshift() { static uint32_t x = 12345789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; w ^= t ^ (t >> 8) ^ (w >> 19); return w; } int rand(const uint32_t l, const uint32_t r) { return xorshift() % (r - l) + l; } uint32_t rand_other_than(const uint32_t l, const uint32_t r, const uint32_t other) { const uint32_t num = rand(l, r - 1); return num + (num >= other); } template const T& rand_vec(const vector& vec) { assert(vec.size() > 0); return vec[rand(0, vec.size())]; } template void shuffle(vector& vec) { rep(l, (int)vec.size() - 1) { const int idx = rand(l, vec.size()); swap(vec[idx], vec[l]); } } class Timer { chrono::system_clock::time_point _start, _end; ll _sum = 0, _count = 0; public: void start() { _start = chrono::system_clock::now(); } void stop() { _end = chrono::system_clock::now(); } void add() { const chrono::system_clock::time_point now = chrono::system_clock::now(); _sum += static_cast( chrono::duration_cast(now - _start).count()); _count++; } ll sum() const { return _sum / 1000; } int count() const { return _count; } string average() const { if (_count == 0) { return "NaN"; } return to_string(_sum / 1000 / _count); } void reset() { _start = chrono::system_clock::now(); _sum = 0; _count = 0; } inline int ms() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count() / 1000); } inline int ns() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count()); } }; #ifdef LOCAL struct Timers : unordered_map { friend ostream& operator<<(ostream& os, const Timers& timers) { for (const auto& pa : timers) { os << pa.first << " time: " << pa.second.sum() / 1000 << " count: " << pa.second.count() << endl; } return os; } }; #else struct Timers { struct Dummy { void start() const {} void add() const {} }; Dummy dummy; const Dummy& operator[](const std::string& str) { return dummy; } friend ostream& operator<<(ostream& os, const Timers& timers) { return os; } }; #endif Timers global_timers; enum Dir { // y-1, y+1, x-1, x+1 kU, kD, kL, kR }; Dir RightDir(const Dir dir) { constexpr Dir kRightDirs[4] = {kR, kL, kU, kD}; return kRightDirs[dir]; } Dir InvDir(const Dir dir) { constexpr Dir kInvDirs[4] = {kD, kU, kR, kL}; return kInvDirs[dir]; } struct Pos { int idx_; Pos() {} explicit Pos(const int _idx) : idx_(_idx) {} Pos(int _x, int _y) : idx_(_y * N + _x) { assert(N > 0); } int X() const { return pos_2_x[*this]; } int Y() const { return pos_2_y[*this]; } int Idx() const { return idx_; } operator int() const { return Idx(); } operator size_t() const { return Idx(); } const vector& Adj() const { return adj_poses[*this]; } const vector& AdjDirs() const { return adj_dirs[*this]; } int Manhattan(const Pos& other) const { return abs(X() - other.X()) + abs(Y() - other.Y()); } int Euclid2(const Pos& other) const { const int dx = X() - other.X(); const int dy = Y() - other.Y(); return dx * dx + dy * dy; } bool Move(const Dir dir) { if (move_to[dir][*this].IsDummy()) { return false; } else { *this = move_to[dir][*this]; return true; } } template bool IsConnectedAfterRemoving(const vector& ids) const { // 自身を削除してもids[p]の連結性が維持されるか3x3を見て判定 bitset<8> bs = 0; int adj_count = 0; int i = -1; const auto& p = *this; const int base_id = ids[p]; for (const auto adj : p.Adj()) { i++; if (ids[adj] == base_id) { adj_count++; bs[i] = true; } } if (adj_count <= 1) return true; i = 3; for (const auto adjadj : adjadjs_check_remove[p]) { i++; bs[i] = ids[adjadj] == base_id; } return can_remove_bses[p][bs.to_ulong()]; } bool operator<(const Pos& other) const { return this->Idx() < other.Idx(); } bool operator==(const Pos& other) const { return this->Idx() == other.Idx(); } bool operator!=(const Pos& other) const { return this->Idx() != other.Idx(); } friend ostream& operator<<(ostream& os, const Pos& pos) { os << pos.X() << " " << pos.Y(); return os; } bool IsDummy() const { return this->idx_ < 0; } static Pos Dummy() { Pos p; p.idx_ = -1; return p; } static Pos TryCreate(const int x, const int y) { if (y < 0 || y >= N || x < 0 || x >= N) { return Pos::Dummy(); } else { return Pos(x, y); } } static void StaticInit(const int n) { N = n; N2 = N * N; N4 = N2 * N2; adj_poses = vector>(N2); adj_dirs = vector>(N2); move_to = vector>(4, vector(N2, Pos::Dummy())); pos_2_y.resize(N2); pos_2_x.resize(N2); rep(y, N) { rep(x, N) { const Pos p{x, y}; all_poses.push_back(p); pos_2_y[p] = y; pos_2_x[p] = x; for (int dy = -1; dy <= 1; ++dy) { for (int dx = -1; dx <= 1; ++dx) { if (abs(dy) + abs(dx) != 1) continue; const int adj_y = y + dy; const int adj_x = x + dx; if (adj_y < 0 || adj_y >= N) continue; if (adj_x < 0 || adj_x >= N) continue; adj_poses[p].emplace_back(adj_x, adj_y); Dir dir; if (dy == -1) { dir = kU; } else if (dy == 1) { dir = kD; } else if (dx == -1) { dir = kL; } else if (dx == 1) { dir = kR; } else { assert(false); } move_to[dir][p] = {adj_x, adj_y}; adj_dirs[p].emplace_back(dir); } } } } all_poses.shrink_to_fit(); if (N * N * 256 <= 1e7) { can_remove_bses.resize(N2); adjadjs_check_remove.resize(N2); rep(idx, N * N) { const Pos p(idx); set S; for (const auto adj : p.Adj()) { for (const auto adjadj : adj.Adj()) { if (adjadj == p) continue; if (S.count(adjadj) > 0) { adjadjs_check_remove[p].push_back(adjadj); } else { S.insert(adjadj); } } } assert(adjadjs_check_remove[p].size() <= 4); rep(bit, 256) { // adj0, adj1, ..., adjadj0, adjdadj1, ... を詰めずに並べる bitset<8> bs(bit); set adjs, adjadjs; rep(j, p.Adj().size()) { if (bs[j]) { adjs.insert(p.Adj()[j]); } } rep(j, adjadjs_check_remove[p].size()) { const auto adjadj = adjadjs_check_remove[p][j]; if (bs[j + 4]) { int count = 0; for (const auto adjadjadj : adjadj.Adj()) { count += adjs.count(adjadjadj); } if (count >= 2) { adjadjs.insert(adjadj); } } } can_remove_bses[p][bs.to_ulong()] = ((int)adjadjs.size() >= (int)adjs.size() - 1); } } } } static int N, N2, N4; static vector all_poses; static vector> adj_poses; static vector> adj_dirs; static vector> move_to; static vector pos_2_x, pos_2_y; // 2^8のbit列を受け取って削除可能かを返す // adj_poses[0], ..., adj_poses[3], adjadjs_check_remove[0], ..., // adjadjs_check_remove[3] // の順に詰めずに並べること 左が上位桁。 static vector> can_remove_bses; static vector> adjadjs_check_remove; }; vector Pos::all_poses; vector> Pos::adj_poses; vector> Pos::adj_dirs; vector> Pos::move_to; vector Pos::pos_2_x, Pos::pos_2_y; int Pos::N, Pos::N2, Pos::N4; vector> Pos::can_remove_bses; vector> Pos::adjadjs_check_remove; /* start */ using BS = bitset<50 * 50>; using ShopBS = bitset<128>; Timer global_timer; const int N = 50, M = 20, PDelta = -20; const char kEmpty = '.'; const char kBlock = '#'; const char kShop = '@'; vector A; struct Bomb { int C; int L; vector ps; }; struct Explosion { int id; Pos p; bool operator<(const Explosion& other) const { if (id != other.id) { return id < other.id; } return p.Idx() < other.p.Idx(); } }; vector bombs; vector shops; ShopBS all_shop_bs; BS input_blocks; struct Action { Pos p = Pos::Dummy(); int buy_bomb = -1; int use_bomb = -1; static Action CreateMove(const Pos p) { Action action; action.p = p; return action; } static Action CreateBuy(const int id) { Action action; action.buy_bomb = id; return action; } static Action CreateUse(const int id) { Action action; action.use_bomb = id; return action; } friend ostream& operator<<(ostream& os, const vector& actions) { stringstream ss; int command_count = 0; Pos current_pos = Pos(0, 0); for (const auto action : actions) { const Pos p = action.p; if (!p.IsDummy()) { while (current_pos != p) { ss << "\n"; command_count++; ss << "1 "; if (current_pos.Y() != p.Y()) { if (current_pos.Y() < p.Y()) { ss << "D"; current_pos.Move(kD); } else { ss << "U"; current_pos.Move(kU); } } else { if (current_pos.X() < p.X()) { ss << "R"; current_pos.Move(kR); } else { ss << "L"; current_pos.Move(kL); } } } } else if (action.buy_bomb != -1) { command_count++; ss << "\n"; ss << "2 " << action.buy_bomb + 1; } else { command_count++; ss << "\n"; ss << "3 " << action.use_bomb + 1; } } os << command_count; os << ss.str(); return os; } }; vector> _bomb_id2pos2bs; const BS& BombId2Pos2BS(const int bomb_id, const Pos p) { return _bomb_id2pos2bs[bomb_id][p]; } void InitBombId2Pos2BS() { // 破壊するなら0 _bomb_id2pos2bs.resize(M, vector(N * N, 0)); rep(bomb_id, M) { rep(idx, N * N) { const Pos base_p(idx); _bomb_id2pos2bs[bomb_id][base_p] = ~(BS{0}); for (const auto delta : bombs[bomb_id].ps) { const Pos p = Pos::TryCreate(base_p.X() + delta.X() + PDelta, base_p.Y() + delta.Y() + PDelta); if (p.IsDummy()) continue; _bomb_id2pos2bs[bomb_id][base_p][p] = false; } } } } vector> _bomb_id2pos2shop_bs; const ShopBS& BombId2Pos2ShopBS(const int bomb_id, const Pos p) { return _bomb_id2pos2shop_bs[bomb_id][p]; } void InitBombId2Pos2ShopBS() { // 破壊するなら0 _bomb_id2pos2shop_bs.assign(M, vector(N * N, ~(ShopBS{0}))); rep(bomb_id, M) { rep(idx, N * N) { const Pos base_p(idx); const auto bs = BombId2Pos2BS(bomb_id, base_p); rep(shop_id, shops.size()) { if (!bs[shops[shop_id]]) { // 破壊対象 _bomb_id2pos2shop_bs[bomb_id][base_p][shop_id] = false; } } } } } struct Output { static void StaticInit(istream& is) { global_timer.start(); Pos::StaticInit(N); int _; is >> _ >> _; input_blocks = 0; A.resize(N * N); all_shop_bs = 0; rep(i, N) { string s; is >> s; rep(j, N) { const Pos p(j, i); A[p] = s[j]; if (s[j] == kShop) { all_shop_bs[(int)shops.size()] = true; shops.push_back(p); } if (s[j] != kEmpty) { input_blocks[p] = true; } } } shops.shrink_to_fit(); rep(t, M) { int C, L; is >> C >> L; vector ps; rep(i, L) { int y, x; is >> y >> x; Pos p{x - PDelta, y - PDelta}; ps.push_back(p); } bombs.push_back(Bomb{C, L, ps}); } bombs.shrink_to_fit(); InitBombId2Pos2BS(); InitBombId2Pos2ShopBS(); } friend ostream& operator<<(ostream& os, const Output& output) { return os; } }; /* start */ vector PARAMS = {1.0, 0.1}; /* start */ struct ExplosionSolution { set S; BS blocks; ShopBS remain_shops; Explosion last_explosion; ExplosionSolution() : blocks(input_blocks), remain_shops(0) { rep(i, shops.size()) { remain_shops[i] = true; } } int CountBlock() const { return blocks.count(); } int CountRemainShop() const { return remain_shops.count(); } int CountDestroy(const Explosion& exp) const { return (blocks & ~BombId2Pos2BS(exp.id, exp.p)).count(); } void Add(Explosion exp) { if (S.count(exp)) return; S.insert(exp); blocks &= BombId2Pos2BS(exp.id, exp.p); remain_shops &= BombId2Pos2ShopBS(exp.id, exp.p); last_explosion = exp; } }; class BombSolver { public: BombSolver() {} ExplosionSolution Zatsu() { ExplosionSolution sol; while (true) { Explosion exp{rand(0, M), rand_vec(Pos::all_poses)}; auto next_sol = sol; next_sol.Add(exp); if (next_sol.CountBlock() == 0) return next_sol; if (sol.CountBlock() == next_sol.CountBlock()) continue; if (next_sol.CountRemainShop() == 0) continue; sol = next_sol; } assert(false); } vector Solve() { auto best_sol = Zatsu(); best_sol.S.erase(best_sol.last_explosion); auto ret_vec = vector(ALL(best_sol.S)); ret_vec.push_back(best_sol.last_explosion); return ret_vec; } private: }; /* start */ // NBD = neighborhood template struct SimulatedAnnealing { public: SimulatedAnnealing(double end_time, double start_temp, double end_temp) : end_time_(end_time * 1000), // ns inv_time_(1.0 / end_time_), cur_time_(0.0), start_temp_(start_temp), end_temp_(end_temp), diff_temp_(end_temp_ / start_temp_), cur_temp_(start_temp) { assert(start_temp >= end_temp); timer_.start(); } Solution run(const Solution& initial_sol, NBDGenerator& nbd_generator) { Solution sol(initial_sol); int acc = 0; int g = 0; for (;; ++g) { if ((g & 0xff) == 0) { #ifdef SA_MAX_G if (g >= SA_MAX_G) { break; } #endif UpdateTime(); UpdateTemp(); if (cur_time_ > end_time_) { break; } } const auto nbd = nbd_generator.Generate(&sol, g, cur_time_ * inv_time_); constexpr int mod = 1'000'000'000; const int r = rand(0, mod); if (static_cast(r) / mod < exp(-nbd->Diff() / cur_temp_)) { acc++; nbd->Update(&sol); } else { nbd->Restore(&sol); } } cerr << "g,acc: " << g << " " << acc << endl; return sol; } private: double end_time_, inv_time_, cur_time_; double start_temp_, end_temp_, diff_temp_, cur_temp_; Timer timer_; void UpdateTime() { cur_time_ = timer_.ns(); } void UpdateTemp() { cur_temp_ = start_temp_ * pow(diff_temp_, cur_time_ * inv_time_); // cur_temp_ = max(0.0, start_temp_ - cur_time_ * diff_temp_ * inv_time_); } }; /* 実装手順 0. Output::StaticInit(istream&)を実装 1. Solutionの初期解生成を書く 2. Solutionに対する操作とEvalの更新を書く 3. Evalの初期値計算を書く 4. Eval::Sum()とSolution::Score()を書く 5. 近傍操作と復元操作を書く 6. 近傍の各確率を調整 */ struct Eval { // 最小化問題とすること int dist_sum = 0; int no_shop_count = 0; double Sum() const { return (double)dist_sum + (double)no_shop_count * INF; } }; struct Solution { // 爆弾を置く順番 // 購入は最寄りの店から一つずつ貪欲に vector order; vector actions; Eval eval; static vector all_explosions; static void InitAllExplosions(const vector& explosions) { all_explosions = explosions; } Solution() : order(all_explosions.size()) { assert((int)all_explosions.size() > 0); std::iota(ALL(order), 0); InitEval(false); } void InitEval(const bool update_action) { eval = Eval(); actions.clear(); ShopBS remain_shops = all_shop_bs; Pos current_pos = Pos(0, 0); for (const int exp_idx : order) { const auto& exp = all_explosions[exp_idx]; const auto& explode_shop = BombId2Pos2ShopBS(exp.id, exp.p); // 残っている店のうち最も近いところ // TODO: 高速化 int best_shop_id = -1; int min_manhattan = INF; rep(shop_id, shops.size()) { if (!remain_shops[shop_id]) continue; const auto shop_pos = shops[shop_id]; const int manhattan = current_pos.Manhattan(shop_pos) + shop_pos.Manhattan(exp.p); if (manhattan < min_manhattan) { min_manhattan = manhattan; best_shop_id = shop_id; } } if (best_shop_id == -1) { eval.no_shop_count += 1; cerr << "hoge" << endl; continue; } if (update_action) { // 店に移動、購入、犯行現場に移動、爆破 actions.push_back(Action::CreateMove(shops[best_shop_id])); actions.push_back(Action::CreateBuy(exp.id)); actions.push_back(Action::CreateMove(exp.p)); actions.push_back(Action::CreateUse(exp.id)); } remain_shops &= explode_shop; eval.dist_sum += min_manhattan; current_pos = exp.p; } } static Solution CreateInitialSol() { Solution sol; sol.InitEval(false); return sol; } double Evaluate() const { return eval.Sum(); } double Score() const { // 最大化問題とすること return -Evaluate(); } friend ostream& operator<<(ostream& os, const Solution& sol) { return os; } }; vector Solution::all_explosions; struct NBD { double Diff() const { return diff; } void Update(Solution*) const {}; virtual void Restore(Solution*) const = 0; double diff; }; struct NBD1 : public NBD { NBD1() {} NBD1(Solution* const sol) { diff = -sol->Evaluate(); } void Restore(Solution* sol) const override {} }; struct NBD2 : public NBD { NBD2() {} NBD2(Solution* const sol) { diff = -sol->Evaluate(); } void Restore(Solution* sol) const override {} }; struct NBDGenerator { NBD* Generate(Solution* const sol, const int g, const double progress) { if (sol->Score() > best_sol.Score()) { best_sol = *sol; } const int random = rand(0, 100); if (random < 50) { nbd1_ = NBD1(sol); return &nbd1_; } else if (random < 100) { nbd2_ = NBD2(sol); return &nbd2_; } else { assert(false); } } const Solution& GetBestSol() const { return best_sol; } private: NBD1 nbd1_; NBD2 nbd2_; Solution best_sol; }; vector SARun() { Solution first_sol = Solution::CreateInitialSol(); // NBDGenerator gen; // SimulatedAnnealing SA(1950 - global_timer.ms(), // PARAMS[0], PARAMS[1]); // const auto final_sol = SA.run(first_sol, gen); // const auto best_sol = gen.GetBestSol(); // cerr << "score: " << best_sol.Score() << endl; // cout << best_sol << endl; // return best_sol; first_sol.InitEval(true); // cerr << first_sol.actions.size() << " " << Solution::all_explosions.size() // << endl; // const auto bs = BombId2Pos2BS(0, Pos(21, 16)); // rep(y, N) { // rep(x, N) { cerr << bs[Pos(x, y)]; } // cerr << endl; // } return first_sol.actions; } /* start */ class PlanSolver { public: PlanSolver() {} void Solve(const vector& explosions) { Solution::InitAllExplosions(explosions); const auto actions = SARun(); cout << actions << endl; } private: }; /* start */ class Solver { public: Solver() {} void Solve() { BombSolver solver; const auto sol = solver.Solve(); PlanSolver solver2; solver2.Solve(sol); return; } private: }; int main(int argc, char* argv[]) { fast_io; if (argc >= 2) { int idx = 0; for (int i = 1; i < argc; ++i) { PARAMS[idx++] = std::stod(argv[i]); } } Timer timer; timer.start(); Output::StaticInit(cin); Solver solver; solver.Solve(); return 0; }