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; // NBD = neighborhood template struct SimulatedAnnealing { public: SimulatedAnnealing(double end_time, double start_temp, double end_temp) : end_time_(end_time), 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) { 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 % 10000 == 0) { // cout << sol.Eval() << " " << sol.Score() << endl; // cout << sol.Convert() << endl << endl; // } if ((g & 0xf) == 0) { #ifdef SA_MAX_G if (g >= SA_MAX_G) { break; } #endif UpdateTime(); UpdateTemp(); if (cur_time_ > end_time_) { break; } } // const auto prev_sol = sol; const auto nbd = nbd_generator.Generate(&sol, g); 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 { // const auto mid_sol = sol; nbd->Restore(&sol); // if (prev_sol != sol) { // for (const auto& obj : prev_sol.pos_pairs) { // cerr << obj.Idx() << " "; // } // for (const auto& obj : mid_sol.pos_pairs) { // cerr << obj.Idx() << " "; // } // for (const auto& obj : sol.pos_pairs) { // cerr << obj.Idx() << " "; // } // abort(); // } } } 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_.ms(); } void UpdateTemp() { cur_temp_ = max(0.0, start_temp_ - cur_time_ * diff_temp_ * inv_time_); } }; enum Dir { // y-1, y+1, x-1, x+1 kU, kD, kL, kR }; 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()); } bool Move(const Dir dir) { if (move_to[dir][*this].IsDummy()) { return false; } else { *this = move_to[dir][*this]; return true; } } 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, const int z) { 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}; 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); } } } } } static int N, N2, N4; static vector> adj_poses; static vector> adj_dirs; static vector> move_to; static vector pos_2_x, pos_2_y; }; 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; /* start */ template class Graph_T { public: struct Edge { Point to; Dist dist; Edge(const Point _to, const Dist _dist) : to(_to), dist(_dist) {} }; explicit Graph_T(const int n) : n_(n), adjs_(n) {} int N() const { return n_; } void AddEdge(const Point a, const Point b, const Dist dist) { adjs_[a].emplace_back(b, dist); } const vector& Adj(const Point a) const { return adjs_[a]; } void RemoveEdge(const Point a, const Point b) { { const auto itr = std::find_if( all(adjs_[a]), [&](const Edge& edge) { return edge.to == b; }); adjs_[a].erase(itr); } } private: int n_; vector> adjs_; }; template struct DijkstraData { Dist dist = 1e9; Point prev; }; template vector> Dijkstra(const Graph& graph, const Point& base_point) { vector> datas(graph.N()); using P = tuple; priority_queue, greater

> pq; datas[base_point] = {0, base_point}; pq.emplace(0, base_point, base_point); while (pq.size() > 0) { const auto [dist, point, prev_point] = pq.top(); pq.pop(); if (datas[point].dist < dist) continue; for (const auto& edge : graph.Adj(point)) { const Point to = edge.to; const Dist edge_dist = edge.dist; const Dist new_dist = dist + edge_dist; if (datas[to].dist > new_dist) { datas[to].dist = new_dist; datas[to].prev = point; pq.emplace(new_dist, to, point); } } } return datas; } template vector Keiro(const vector>& dijkstra_results, const Point& from, const Point& to) { // 到達可能であることは仮定 vector ret; Point p = to; while (p != from) { ret.emplace_back(p); p = dijkstra_results[p].prev; } ret.emplace_back(from); reverse(all(ret)); return ret; } /* start */ struct Board { using Graph = Graph_T; Board() {} Board(istream& is) { is >> N >> D >> H; Pos::StaticInit(N); rep(i, N) { string s; is >> s; S += s; } is >> M; rep(i, M) { int y, x, d; is >> y >> x >> d; Tanchiki tanchiki{Pos(x, y), d}; tanchikies_.emplace_back(tanchiki); } rep(idx, Pos::N2) { const Pos p(idx); if (S[p] == 'S') { start_pos = p; } else if (S[p] == 'G') { goal_pos = p; } else if (S[p] == 'K') { key_pos = p; } else if (S[p] == 'J') { jewel_count++; } if (IsCheckPoint(p)) { check_points.emplace_back(p); } } InitBeamCount(); InitDist(); } void InitBeamCount() { pm2beams_.resize(Pos::N2, vector(60)); for (const auto& tanchiki : tanchikies_) { for (const auto dir : {kU, kD, kL, kR}) { Pos p = tanchiki.p; while (p.Move(dir) && CanMove(p)) { rep(t, 60) { if (t % tanchiki.d == 0) { pm2beams_[p][t]++; } } } } } } void InitDist() { Graph graph(Pos::N2); rep(idx1, Pos::N2) { const Pos p1(idx1); if (!CanMove(p1)) continue; int acc_p1 = std::accumulate(all(pm2beams_[p1]), 0); for (const auto& p2 : p1.Adj()) { if (!CanMove(p2)) continue; const float expected_hps = (acc_p1 + std::accumulate(all(pm2beams_[p2]), 0)) * D * 0.7 / 120.0 + 1.0; graph.AddEdge(p1, p2, expected_hps); } } dists_.resize(Pos::N2); keiros_.resize(Pos::N2); rep(idx1, Pos::N2) { const Pos p1(idx1); if (!IsCheckPoint(p1)) continue; dists_[idx1].resize(Pos::N2, INF); keiros_[idx1].resize(Pos::N2); const auto ret = Dijkstra(graph, p1); rep(idx2, Pos::N2) { const Pos p2(idx2); if (!IsCheckPoint(p2)) continue; const auto& [dist, _] = ret[idx2]; dists_[idx1][idx2] = dist; if (dist < INF * 0.1) { keiros_[idx1][idx2] = ::Keiro(ret, p1, p2); } } } } bool IsCheckPoint(const Pos& p) const { // TODO: Fも追加 return S[p] == 'S' || S[p] == 'G' || S[p] == 'K' || S[p] == 'J'; } int BeamCount(const Pos& p, const int t) const { return pm2beams_[p][t % 60]; } bool CanMove(const Pos& p) const { return S[p] != '#' && S[p] != 'B' && S[p] != 'E'; } float Dist(const Pos& p1, const Pos& p2) const { return dists_[p1][p2]; } const vector& Keiro(const Pos& from, const Pos& to) const { return keiros_[from][to]; } // 消費したHPを返す int Simulate(const vector& poses, int t) const { // posesはSとGも含む int hp = (int)poses.size() - 1; reps(i, (int)poses.size() - 1) { const auto& p = poses[i]; hp += pm2beams_[p][(t + i) % 60] * D; } return hp; } // 消費したHPをDPで最小化してから、返す pair, int> DPSimulate(const vector& poses, int t, const int limit_hp) const { // posesはSとGも含む struct Data { int hp = INF; int prev_i; int prev_j; }; // dp[i][j] : poses[i]の行動が終わっていて、t%60がj (次のt%60はj+1) vector> dp(poses.size(), vector(60)); dp[0][t % 60].hp = 0; rep(i, (int)poses.size() - 1) { const Pos& p = poses[i]; const Pos& next_p = poses[i + 1]; rep(_, 2) { // トーラスなので2週する rep(t, 60) { const int hp = dp[i][t].hp; const int next_time = (t + 1) % 60; // 移動する { auto& next_data = dp[i + 1][next_time]; const int next_hp = hp + pm2beams_[next_p][next_time] * D + 1; if (next_hp < next_data.hp) { next_data.hp = next_hp; next_data.prev_i = i; next_data.prev_j = t; } } // その場にとどまる { auto& next_data = dp[i][next_time]; const int next_hp = hp + pm2beams_[p][next_time] * D + 1; if (next_hp < next_data.hp) { next_data.hp = next_hp; next_data.prev_i = i; next_data.prev_j = t; } } } } } int best_hp = INF; int best_i = (int)dp.size() - 1; int best_j = 0; rep(t, 60) { if (dp[best_i][t].hp < best_hp) { best_hp = dp[best_i][t].hp; best_j = t; } } if (best_hp > limit_hp) { return {{}, INF}; } vector ret; ret.reserve(poses.size() * 2); int i = best_i, j = best_j; while (i != t % 60 || j != 0) { ret.emplace_back(poses[i]); const int prev_i = dp[i][j].prev_i; const int prev_j = dp[i][j].prev_j; i = prev_i; j = prev_j; } ret.emplace_back(poses[i]); reverse(all(ret)); return {ret, best_hp}; } static vector Merge(const vector>& keiros) { assert(keiros.size() > 0); vector ret; for (const auto& kerio : keiros) { assert(kerio.size() > 0); ret.insert(ret.end(), kerio.begin(), kerio.begin() + ((int)kerio.size() - 1)); } ret.emplace_back(keiros.back().back()); return ret; } // public int N, D, H, M; string S; Pos start_pos, goal_pos, key_pos; int jewel_count = 0; // private struct Tanchiki { Pos p; int d; }; vector> dists_; vector>> keiros_; vector tanchikies_; vector check_points; // [pos][mod] vector> pm2beams_; }; ostream& operator<<(ostream& os, const vector keiro) { rep(i, (int)keiro.size() - 1) { const Pos from = keiro[i]; const Pos to = keiro[i + 1]; if (from == to) { os << "S"; } else if (from.Y() - 1 == to.Y()) { os << "M U"; } else if (from.Y() + 1 == to.Y()) { os << "M D"; } else if (from.X() - 1 == to.X()) { os << "M L"; } else if (from.X() + 1 == to.X()) { os << "M R"; } if (i != (int)keiro.size() - 2) { os << "\n"; } } return os; } /* start */ Board global_board; struct Individual { vector points; float hp = INF; bitset<3600> exists = 0; float DiffInsert(const Board& board, const int idx, const Pos& pos) const { assert(idx >= 1); assert(idx < (int)points.size()); return board.Dist(points[idx - 1], pos) + board.Dist(pos, points[idx]); } void Insert(const Board& board, const int idx, const Pos& pos) { hp += DiffInsert(board, idx, pos); points.insert(points.begin() + idx, pos); exists[pos] = true; } float DiffSwap(const Board& board, int l, int r) const { assert(l < r); assert(0 < l); assert(r < (int)points.size()); const float prev_dist = board.Dist(points[l - 1], points[l]) + board.Dist(points[r - 1], points[r]); // TODO: 無向辺に直す const float next_dist = board.Dist(points[l - 1], points[r - 1]) + board.Dist(points[l], points[r]); return next_dist - prev_dist; } void Swap(const Board& board, int l, int r) { hp += DiffSwap(board, l, r); reverse(points.begin() + l, points.begin() + r); } }; struct Population { vector inds; Population(const Board& board) : inds(board.jewel_count + 2) { inds[3].points = vector{board.start_pos, board.key_pos, board.goal_pos}; inds[3].hp = board.Dist(board.start_pos, board.key_pos) + board.Dist(board.key_pos, board.goal_pos); inds[3].exists[board.start_pos] = true; inds[3].exists[board.key_pos] = true; inds[3].exists[board.goal_pos] = true; } }; struct NBD { float Diff() const { return diff_; } virtual void Update(Population*) const = 0; void Restore(Population*) const {} float diff_; }; struct NBD_insert : public NBD { NBD_insert() {} NBD_insert(Population* const sol, const int ind_idx, const int insert_idx, const Pos& p) { ind_idx_ = ind_idx; insert_idx_ = insert_idx; p_ = p; const auto& ind = sol->inds[ind_idx]; assert(!ind.exists[p]); diff_ = ind.DiffInsert(global_board, insert_idx, p) + ind.hp - sol->inds[ind_idx + 1].hp; } void Update(Population* sol) const override { auto ind = sol->inds[ind_idx_]; ind.Insert(global_board, insert_idx_, p_); sol->inds[ind_idx_ + 1] = ind; } int ind_idx_; int insert_idx_; Pos p_; }; struct NBD_swap : public NBD { NBD_swap() {} NBD_swap(Population* const sol, const int ind_idx, const int l, const int r) { ind_idx_ = ind_idx; l_ = l; r_ = r; const auto& ind = sol->inds[ind_idx]; diff_ = ind.DiffSwap(global_board, l, r); } void Update(Population* sol) const override { sol->inds[ind_idx_].Swap(global_board, l_, r_); } int ind_idx_; int l_; int r_; }; struct NBDGenerator { NBDGenerator() {} NBD* Generate(Population* const sol, const int g) { while (true) { int ind_idx = rand(0, sol->inds.size()); while (sol->inds[ind_idx].hp == INF) { ind_idx = rand(0, sol->inds.size()); } auto& ind = sol->inds[ind_idx]; if (rand(0, 100) < 30 || ind.hp < global_board.H) { // insert const int insert_idx = rand(1, ind.points.size()); const Pos p = rand_vec(global_board.check_points); if (ind.exists[p]) continue; nbd_insert0 = NBD_insert(sol, ind_idx, insert_idx, p); return &nbd_insert0; } else { // swap const int r = rand(2, ind.points.size()); const int l = rand(1, r); nbd_swap0 = NBD_swap(sol, ind_idx, l, r); return &nbd_swap0; } } } NBD_insert nbd_insert0; NBD_swap nbd_swap0; }; class Solver { public: explicit Solver(istream& is) : board_(is) { global_board = board_; } vector Solve(int time_limit) { Timer timer; timer.start(); NBDGenerator nbd_generator; time_limit -= timer.ms(); SimulatedAnnealing sa(time_limit - 500, 0.3, 0.1); Population initial_pop(board_); auto best_pop = sa.run(initial_pop, nbd_generator); REP(i, best_pop.inds.size()) { vector> keiros; const auto& ind = best_pop.inds[i]; if (ind.hp == INF) continue; rep(j, (int)ind.points.size() - 1) { auto keiro = board_.Keiro(ind.points[j], ind.points[j + 1]); keiros.emplace_back(std::move(keiro)); } const auto ans_no_dp = Board::Merge(keiros); const auto& [ans, hp] = board_.DPSimulate(ans_no_dp, 0, board_.H - 1); if (hp != INF) { cerr << "Jewel Count: " << (int)ind.points.size() - 3 << "/" << board_.jewel_count << endl; return ans; } } assert(false); } private: Board board_; }; 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(); Solver solver(cin); const auto ans = solver.Solve(2950 - timer.ms()); cout << ans << endl; cerr << "ms: " << timer.ms() << endl; return 0; }