結果
| 問題 |
No.5015 Escape from Labyrinth
|
| コンテスト | |
| ユーザー |
 Jiro_tech15
|
| 提出日時 | 2023-04-16 15:24:19 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 33,112 bytes |
| コンパイル時間 | 5,514 ms |
| コンパイル使用メモリ | 244,236 KB |
| 実行使用メモリ | 205,004 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-04-16 15:24:36 |
| 合計ジャッジ時間 | 14,221 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge16 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 99 |
コンパイルメッセージ
main.cpp: メンバ関数 ‘std::vector<Action> Solver::Solve(int)’ 内:
main.cpp:1263:3: 警告: 制御が非 void 関数の終りに到達しました [-Wreturn-type]
1263 | }
| ^
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);
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] = optimizer.Run(board_.H - 1);
if (hp != INF) {
cerr << "Jewel Count: " << (int)check_points.size() - 3 << "/"
<< board_.jewel_count << endl;
cerr << global_timers << 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;
}