結果
問題 | No.5015 Escape from Labyrinth |
ユーザー | Jiro_tech15 |
提出日時 | 2023-04-16 15:52:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 34,257 bytes |
コンパイル時間 | 6,104 ms |
コンパイル使用メモリ | 249,772 KB |
実行使用メモリ | 224,196 KB |
スコア | 180,660 |
最終ジャッジ日時 | 2023-04-16 15:58:00 |
合計ジャッジ時間 | 306,002 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,930 ms
200,248 KB |
testcase_01 | AC | 2,935 ms
199,396 KB |
testcase_02 | AC | 2,928 ms
202,340 KB |
testcase_03 | AC | 2,869 ms
189,168 KB |
testcase_04 | WA | - |
testcase_05 | AC | 2,947 ms
216,556 KB |
testcase_06 | AC | 2,886 ms
205,440 KB |
testcase_07 | AC | 2,897 ms
184,980 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 2,991 ms
200,492 KB |
testcase_12 | AC | 2,874 ms
193,584 KB |
testcase_13 | AC | 2,875 ms
224,196 KB |
testcase_14 | AC | 2,891 ms
216,584 KB |
testcase_15 | AC | 2,884 ms
208,188 KB |
testcase_16 | WA | - |
testcase_17 | AC | 2,931 ms
206,972 KB |
testcase_18 | AC | 2,942 ms
200,788 KB |
testcase_19 | AC | 2,900 ms
187,664 KB |
testcase_20 | AC | 2,875 ms
207,468 KB |
testcase_21 | AC | 2,867 ms
204,160 KB |
testcase_22 | AC | 2,957 ms
194,024 KB |
testcase_23 | WA | - |
testcase_24 | AC | 2,888 ms
195,888 KB |
testcase_25 | AC | 2,874 ms
197,520 KB |
testcase_26 | AC | 2,884 ms
192,652 KB |
testcase_27 | AC | 2,937 ms
214,440 KB |
testcase_28 | AC | 2,869 ms
193,884 KB |
testcase_29 | AC | 2,894 ms
206,088 KB |
testcase_30 | AC | 2,950 ms
208,932 KB |
testcase_31 | AC | 2,945 ms
190,456 KB |
testcase_32 | AC | 2,885 ms
205,524 KB |
testcase_33 | WA | - |
testcase_34 | AC | 2,902 ms
198,228 KB |
testcase_35 | AC | 2,927 ms
215,556 KB |
testcase_36 | AC | 2,893 ms
207,120 KB |
testcase_37 | WA | - |
testcase_38 | AC | 2,876 ms
217,048 KB |
testcase_39 | AC | 2,915 ms
197,516 KB |
testcase_40 | AC | 2,861 ms
204,516 KB |
testcase_41 | WA | - |
testcase_42 | AC | 2,938 ms
210,176 KB |
testcase_43 | AC | 2,874 ms
190,928 KB |
testcase_44 | AC | 2,884 ms
199,820 KB |
testcase_45 | AC | 2,897 ms
217,480 KB |
testcase_46 | AC | 2,930 ms
207,152 KB |
testcase_47 | WA | - |
testcase_48 | AC | 2,861 ms
206,376 KB |
testcase_49 | WA | - |
testcase_50 | AC | 2,866 ms
205,664 KB |
testcase_51 | WA | - |
testcase_52 | AC | 2,923 ms
199,452 KB |
testcase_53 | WA | - |
testcase_54 | WA | - |
testcase_55 | WA | - |
testcase_56 | AC | 2,918 ms
213,684 KB |
testcase_57 | AC | 2,876 ms
203,312 KB |
testcase_58 | WA | - |
testcase_59 | AC | 2,944 ms
191,708 KB |
testcase_60 | AC | 2,954 ms
205,308 KB |
testcase_61 | AC | 2,868 ms
194,180 KB |
testcase_62 | AC | 2,902 ms
195,872 KB |
testcase_63 | WA | - |
testcase_64 | WA | - |
testcase_65 | WA | - |
testcase_66 | AC | 2,885 ms
200,568 KB |
testcase_67 | AC | 2,867 ms
201,172 KB |
testcase_68 | WA | - |
testcase_69 | WA | - |
testcase_70 | AC | 2,933 ms
216,420 KB |
testcase_71 | WA | - |
testcase_72 | AC | 2,962 ms
200,636 KB |
testcase_73 | AC | 2,865 ms
199,536 KB |
testcase_74 | AC | 2,943 ms
195,708 KB |
testcase_75 | WA | - |
testcase_76 | AC | 2,899 ms
218,876 KB |
testcase_77 | WA | - |
testcase_78 | AC | 2,900 ms
210,256 KB |
testcase_79 | AC | 2,896 ms
194,620 KB |
testcase_80 | AC | 2,875 ms
209,292 KB |
testcase_81 | AC | 2,947 ms
182,212 KB |
testcase_82 | AC | 2,906 ms
194,432 KB |
testcase_83 | AC | 2,915 ms
190,720 KB |
testcase_84 | AC | 2,881 ms
209,528 KB |
testcase_85 | AC | 2,888 ms
198,300 KB |
testcase_86 | AC | 2,947 ms
212,044 KB |
testcase_87 | WA | - |
testcase_88 | AC | 2,924 ms
203,364 KB |
testcase_89 | WA | - |
testcase_90 | AC | 2,866 ms
200,100 KB |
testcase_91 | AC | 2,919 ms
193,964 KB |
testcase_92 | AC | 2,940 ms
219,744 KB |
testcase_93 | WA | - |
testcase_94 | AC | 2,892 ms
208,160 KB |
testcase_95 | AC | 2,931 ms
208,712 KB |
testcase_96 | WA | - |
testcase_97 | AC | 2,918 ms
206,600 KB |
testcase_98 | AC | 2,892 ms
202,996 KB |
testcase_99 | AC | 2,867 ms
200,980 KB |
コンパイルメッセージ
main.cpp: 静的メンバ関数 ‘static void Pos::StaticInit(int)’ 内: main.cpp:390:24: 警告: ‘dir’ may be used uninitialized [-Wmaybe-uninitialized] 390 | move_to[dir][p] = {adj_x, adj_y}; | ^ main.cpp:377:17: 備考: ‘dir’ はここで宣言されています 377 | Dir dir; | ^~~
ソースコード
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 <gtest/gtest.h> #endif #include <math.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cstdlib> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <unordered_map> #include <unordered_set> #include <vector> #ifdef PERF #include <gperftools/profiler.h> #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<int, int> Pii; typedef pair<ll, ll> 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 <typename T> string to_string(const vector<T>& vec) { string ret = ""; rep(i, vec.size()) { ret += vec[i].to_string(); if (i + 1 != vec.size()) { ret += ","; } } return ret; } template <typename T> ostream& operator<<(ostream& os, const vector<T>& 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 <typename T> const T& rand_vec(const vector<T>& vec) { assert(vec.size() > 0); return vec[rand(0, vec.size())]; } template <typename T> void shuffle(vector<T>& 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<double>( chrono::duration_cast<chrono::nanoseconds>(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<double>( chrono::duration_cast<chrono::microseconds>(now - _start).count() / 1000); } inline int ns() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast<double>( chrono::duration_cast<chrono::microseconds>(now - _start).count()); } }; #ifdef LOCAL struct Timers : unordered_map<string, Timer> { 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 <class Solution, class NBDGenerator> 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<double>(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<Pos>& Adj() const { return adj_poses[*this]; } const vector<Dir>& 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<vector<Pos>>(N2); adj_dirs = vector<vector<Dir>>(N2); move_to = vector<vector<Pos>>(4, vector<Pos>(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<vector<Pos>> adj_poses; static vector<vector<Dir>> adj_dirs; static vector<vector<Pos>> move_to; static vector<int> pos_2_x, pos_2_y; }; vector<vector<Pos>> Pos::adj_poses; vector<vector<Dir>> Pos::adj_dirs; vector<vector<Pos>> Pos::move_to; vector<int> Pos::pos_2_x, Pos::pos_2_y; int Pos::N, Pos::N2, Pos::N4; /* start */ template <typename Point, typename Dist> 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<Edge>& 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<vector<Edge>> adjs_; }; template <typename Point, typename Dist> struct DijkstraData { Dist dist = 1e9; Point prev; }; template <class Graph, typename Point, typename Dist> vector<DijkstraData<Point, Dist>> Dijkstra(const Graph& graph, const Point& base_point) { vector<DijkstraData<Point, Dist>> datas(graph.N()); using P = tuple<Dist, Point, Point>; priority_queue<P, vector<P>, greater<P>> 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 <typename Point, typename Dist> vector<Point> Keiro(const vector<DijkstraData<Point, Dist>>& dijkstra_results, const Point& from, const Point& to) { // 到達可能であることは仮定 vector<Point> 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<Pos, float>; Board() {} Board(istream& is) { is >> N >> D >> H; Pos::StaticInit(N); rep(i, N) { string s; is >> s; S += s; } enemy_ds_.resize(Pos::N2); is >> M; rep(i, M) { int y, x, d; is >> y >> x >> d; Tanchiki tanchiki{Pos(x, y), d}; tanchikies_.emplace_back(tanchiki); enemy_ds_[Pos(x, y)] = d; } 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<int>(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, Pos, float>(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'; } bool IsEnemy(const Pos& p) const { return S[p] == 'E'; } bool IsDefaultEmpty(const Pos& p) const { return S[p] == '.' || S[p] == 'S'; } int GetEnemyD(const Pos& p) const { assert(IsEnemy(p)); assert(enemy_ds_[p] > 0); return enemy_ds_[p]; } float Dist(const Pos& p1, const Pos& p2) const { return dists_[p1][p2]; } const vector<Pos>& Keiro(const Pos& from, const Pos& to) const { return keiros_[from][to]; } // 消費したHPを返す int Simulate(const vector<Pos>& 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<vector<Pos>, int> DPSimulate(const vector<Pos>& 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<vector<Data>> dp(poses.size(), vector<Data>(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<Pos> 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}; } // checkpointを削るDP vector<vector<Pos>> DPReduceCheckPoints( const vector<Pos>& original_poses) const { // dp[i][j] : // 現在original_poses[i]にいて、j個のposをskipしているなかで、消費HPの期待値の最小値 struct Data { float hp = INF; int prev_i; int prev_j; }; int key_idx = 0; rep(i, original_poses.size()) { if (key_pos == original_poses[i]) { key_idx = i; break; } } const int max_skip_count = 200; vector<vector<Data>> dp(original_poses.size(), vector<Data>(max_skip_count + 1)); dp[0][0].hp = 0; rep(i, (int)original_poses.size() - 1) { rep(j, max_skip_count) { const auto current_hp = dp[i][j].hp; for (int k = 1; i + k < (int)original_poses.size() && j + k - 1 <= max_skip_count; ++k) { const int next_i = i + k; if (i < key_idx && key_idx < next_i) { break; } const int next_j = j + k - 1; const float next_hp = Dist(original_poses[i], original_poses[next_i]) + current_hp; auto& next_dp = dp[next_i][next_j]; if (next_hp < next_dp.hp) { next_dp.hp = next_hp; next_dp.prev_i = i; next_dp.prev_j = j; } } } } vector<vector<Pos>> ret; ret.reserve(max_skip_count + 1); rep(skip_count, max_skip_count + 1) { int i = (int)original_poses.size() - 1; int j = skip_count; ret.emplace_back(); while (i != 0 || j != 0) { ret.back().emplace_back(original_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.back().emplace_back(original_poses[i]); reverse(all(ret.back())); } return ret; } static vector<Pos> Merge(const vector<vector<Pos>>& keiros) { assert(keiros.size() > 0); vector<Pos> 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<int> enemy_ds_; vector<vector<float>> dists_; vector<vector<vector<Pos>>> keiros_; vector<Tanchiki> tanchikies_; vector<Pos> check_points; // [pos][mod] vector<vector<int>> pm2beams_; }; ostream& operator<<(ostream& os, const vector<Pos> 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 */ enum ActionKind { kStart, kStay, kMove, kPut }; struct Action { Pos p; ActionKind kind; }; ostream& operator<<(ostream& os, const vector<Action>& actions) { Pos from = actions.front().p; reps(i, (int)actions.size() - 1) { const auto kind = actions[i].kind; const auto to = actions[i].p; assert(kind != kStart); if (kind == kStay) { os << "S"; } else if (kind == kMove) { 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"; } from = to; } else if (kind == kPut) { if (from.Y() - 1 == to.Y()) { os << "B U"; } else if (from.Y() + 1 == to.Y()) { os << "B D"; } else if (from.X() - 1 == to.X()) { os << "B L"; } else if (from.X() + 1 == to.X()) { os << "B R"; } } if (i != (int)actions.size() - 1) { os << "\n"; } } return os; } struct BlockOptimizer { // keiroはS,Gも含む BlockOptimizer(Board* const board, const vector<Pos> keiro) : board_(board), keiro_(keiro) {} pair<vector<Action>, int> Run(const int limit_hp) const { struct Data { int hp = INF; // 今後のdamage期待値のdiff // 減少量 正の値 float expected_damage_diff = 0; int prev_i = -1; int prev_j = -1; Action prev_action; // blockがあるならtrue bitset<3600> bs = 0; bitset<3600> empty_bs = 0; }; // 消費したHPをDPで最小化 // Stay, Move, Put // 各マスを通る回数を事前計算 vector<int> move_counts(Pos::N2, 0); for (const auto& p : keiro_) { move_counts[p]++; } auto calc_expected_damage = [&](const Pos& base_p, const bitset<3600>& bs) { float sum = 0.0; for (const auto dir : {kU, kD, kL, kR}) { Pos p = base_p; bool is_no_dummy = true; while ((is_no_dummy = p.Move(dir)) && board_->CanMove(p) && !bs[p]) { } if (!is_no_dummy) continue; if (!board_->IsEnemy(p)) continue; const int d = board_->GetEnemyD(p); sum += 1.0 / d; } return sum * board_->D; }; auto calc_true_damage = [&](const Pos& base_p, const int t, const bitset<3600>& bs) { int sum = 0; for (const auto dir : {kU, kD, kL, kR}) { Pos p = base_p; bool is_no_dummy = true; while ((is_no_dummy = p.Move(dir)) && board_->CanMove(p) && !bs[p]) { } if (!is_no_dummy) continue; if (!board_->IsEnemy(p)) continue; const int d = board_->GetEnemyD(p); sum += (t % d == 0); } return sum * board_->D; }; auto calc_block_value = [&](const Pos& base_p, const bitset<3600>& bs) { assert(move_counts[base_p] == 0); float sum = 0.0; vector<int> move_count_sums(4); vector<int> enemy_ds(4); int idx = -1; for (const auto dir : {kU, kD, kL, kR}) { idx++; Pos p = base_p; bool is_no_dummy = true; while ((is_no_dummy = p.Move(dir)) && board_->CanMove(p) && !bs[p]) { move_count_sums[idx] += move_counts[p]; } if (!is_no_dummy) continue; if (!board_->IsEnemy(p)) continue; enemy_ds[idx] = board_->GetEnemyD(p); } rep(i, 4) { if (enemy_ds[i] == 0) continue; sum += move_count_sums[i / 2 * 2 + (1 - i % 2)] * 1.0 / enemy_ds[i]; } return sum * board_->D; }; // dp[i][j] : poses[i]の行動が終わっていて、t%60がj (次のt%60はj+1) vector<vector<Data>> dp(keiro_.size(), vector<Data>(60)); dp[0][0].hp = 0; dp[0][0].bs = 0; dp[0][0].empty_bs = 0; rep(idx, Pos::N2) { const Pos p(idx); dp[0][0].empty_bs[p] = board_->IsDefaultEmpty(p); } rep(i, (int)keiro_.size() - 1) { const auto p = keiro_[i]; const auto next_p = keiro_[i + 1]; move_counts[p]--; // dpの更新 // トーラス rep(_, 2) { rep(t, 60) { const auto& current_data = dp[i][t]; const int hp = current_data.hp; const float expected_damage_diff = current_data.expected_damage_diff; const int next_time = (t + 1) % 60; // 移動する { auto& next_data = dp[i + 1][next_time]; const int next_hp = hp + calc_true_damage(next_p, next_time, current_data.bs) + 1; // 次のマスのdamage期待値 // TODO:高速化? const float next_expected_damage = calc_expected_damage(next_p, current_data.bs); const float next_expected_damage_diff = expected_damage_diff - next_expected_damage; if (next_hp - next_expected_damage_diff < next_data.hp - next_data.expected_damage_diff) { next_data.hp = next_hp; next_data.expected_damage_diff = next_expected_damage_diff; next_data.prev_i = i; next_data.prev_j = t; next_data.prev_action = Action{next_p, kMove}; // TODO:高速化 next_data.bs = current_data.bs; next_data.empty_bs = current_data.empty_bs; next_data.empty_bs[next_p] = true; } } // その場にとどまる { auto& next_data = dp[i][next_time]; const int next_hp = hp + calc_true_damage(p, next_time, current_data.bs) + 1; if (next_hp - expected_damage_diff < next_data.hp - next_data.expected_damage_diff) { next_data.hp = next_hp; next_data.expected_damage_diff = expected_damage_diff; next_data.prev_i = i; next_data.prev_j = t; next_data.prev_action = Action{p, kStay}; // TODO:高速化 next_data.bs = current_data.bs; next_data.empty_bs = current_data.empty_bs; } } // ブロックを置く { auto& next_data = dp[i][next_time]; for (const auto dir : {kU, kD, kL, kR}) { Pos to = p; if (!to.Move(dir)) continue; if (!current_data.empty_bs[to]) continue; if (move_counts[to] > 0) continue; auto bs = current_data.bs; bs[to] = true; const int next_hp = hp + calc_true_damage(p, next_time, bs) + 1; // ブロックを置いた場合のdamage減少量の期待値 const auto next_expected_damage_diff = calc_block_value(to, current_data.bs) + current_data.expected_damage_diff; if (next_hp - next_expected_damage_diff < next_data.hp - next_data.expected_damage_diff) { next_data.hp = next_hp; next_data.expected_damage_diff = next_expected_damage_diff; next_data.prev_i = i; next_data.prev_j = t; next_data.prev_action = Action{to, kPut}; // TODO:高速化 next_data.bs = bs; next_data.empty_bs = current_data.empty_bs; next_data.empty_bs[to] = false; } } } } } } 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<Action> ret; ret.reserve(keiro_.size() * 3); int i = best_i, j = best_j; while (true) { const int prev_i = dp[i][j].prev_i; const int prev_j = dp[i][j].prev_j; if (prev_i == -1) break; const auto prev_action = dp[i][j].prev_action; ret.emplace_back(prev_action); i = prev_i; j = prev_j; } ret.emplace_back(Action{keiro_.front(), kStart}); reverse(all(ret)); return {ret, best_hp}; } Board* const board_; vector<Pos> keiro_; }; /* start */ Board global_board; struct Solution { vector<Pos> points; float hp = INF; bitset<3600> exists = 0; static Solution CreateGreedy(const Board& board) { Solution sol; sol.points.emplace_back(board.start_pos); set<Pos> S(all(board.check_points)); S.erase(board.start_pos); S.erase(board.goal_pos); Pos p = board.start_pos; while (S.size() > 0) { const auto itr = std::min_element(all(S), [&](const auto& l, const auto& r) { return board.Dist(p, l) < board.Dist(p, r); }); if (board.Dist(p, *itr) > INF * 0.1) { break; } p = *itr; sol.points.emplace_back(p); S.erase(itr); } sol.points.emplace_back(board.goal_pos); sol.hp = 0; rep(i, (int)sol.points.size()) { sol.exists[sol.points[i]] = true; if (i + 1 < (int)(sol.points.size())) { sol.hp += board.Dist(sol.points[i], sol.points[i + 1]); } } return sol; } 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 NBD { float Diff() const { return diff_; } virtual void Update(Solution*) const = 0; void Restore(Solution*) const {} float diff_; }; struct NBD_swap : public NBD { NBD_swap() {} NBD_swap(Solution* const sol, const int l, const int r) { l_ = l; r_ = r; diff_ = sol->DiffSwap(global_board, l, r); } void Update(Solution* sol) const override { sol->Swap(global_board, l_, r_); } int l_; int r_; }; struct NBDGenerator { NBDGenerator() {} NBD* Generate(Solution* const sol, const int g) { // swap const int r = rand(2, sol->points.size()); const int l = rand(1, r); nbd_swap0 = NBD_swap(sol, l, r); return &nbd_swap0; } NBD_swap nbd_swap0; }; class Solver { public: explicit Solver(istream& is) : board_(is) { global_board = board_; } vector<Action> Solve(int time_limit) { Timer timer; timer.start(); NBDGenerator nbd_generator; time_limit -= timer.ms(); SimulatedAnnealing<Solution, NBDGenerator> sa(time_limit - 2000, 0.3, 0.1); Solution initial_sol = Solution::CreateGreedy(board_); auto best_sol = sa.run(initial_sol, nbd_generator); const auto skip_count2check_points = board_.DPReduceCheckPoints(best_sol.points); int best_skip_count = INF; vector<Action> best_actions; rep(skip_count, skip_count2check_points.size()) { const auto& check_points = skip_count2check_points[skip_count]; vector<vector<Pos>> keiros; rep(j, (int)check_points.size() - 1) { auto keiro = board_.Keiro(check_points[j], check_points[j + 1]); assert(keiro.size() > 0); keiros.emplace_back(std::move(keiro)); } const auto ans_no_dp = Board::Merge(keiros); BlockOptimizer optimizer(&board_, ans_no_dp); const auto& [ans, hp] = board_.DPSimulate(ans_no_dp, 0, board_.H - 1); if (hp != INF) { best_skip_count = skip_count; cerr << "Jewel Count: " << (int)check_points.size() - 3 << "/" << board_.jewel_count << endl; break; } } for (const int delta : {5, 1}) { for (int skip_count = best_skip_count - delta; skip_count >= 0; skip_count -= delta) { if (timer.ms() >= time_limit) break; const auto& check_points = skip_count2check_points[skip_count]; vector<vector<Pos>> keiros; rep(j, (int)check_points.size() - 1) { auto keiro = board_.Keiro(check_points[j], check_points[j + 1]); assert(keiro.size() > 0); keiros.emplace_back(std::move(keiro)); } const auto ans_no_dp = Board::Merge(keiros); BlockOptimizer optimizer(&board_, ans_no_dp); const auto& [ans, hp] = optimizer.Run(board_.H - 1); if (hp != INF) { best_skip_count = skip_count; best_actions = ans; } } } assert(best_skip_count != INF); cerr << "Jewel Count: " << (int)skip_count2check_points[best_skip_count].size() - 3 << "/" << board_.jewel_count << endl; #ifndef LOCAL cout << best_actions << endl; std::quick_exit(0); #endif return best_actions; } 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(2850 - timer.ms()); cout << ans << endl; cerr << "ms: " << timer.ms() << endl; return 0; }