結果
| 問題 |
No.5015 Escape from Labyrinth
|
| コンテスト | |
| ユーザー |
 Yu_212
|
| 提出日時 | 2023-04-16 16:43:33 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 18,171 bytes |
| コンパイル時間 | 4,646 ms |
| コンパイル使用メモリ | 267,856 KB |
| 実行使用メモリ | 42,780 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-04-16 16:48:56 |
| 合計ジャッジ時間 | 319,749 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 100 |
ソースコード
#include <bits/stdc++.h>
// #include "atcoder/all"
using namespace std;
using i64 = long long;
const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18);
template <typename T>
bool chmin(T& x, T y){
if(x > y){
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T& x, T y){
if(x < y){
x = y;
return true;
}
return false;
}
double elapsed_time(timespec& time_st){
timespec time_now;
clock_gettime(CLOCK_REALTIME, &time_now);
return (time_now.tv_sec - time_st.tv_sec) + (time_now.tv_nsec - time_st.tv_nsec) / 1000000000.0;
}
struct Rnd{
uint64_t x;
Rnd(uint64_t seed) :
x(0xdeadbeef0110dead ^ seed)
{
}
uint64_t rnd(){
x ^= x << 7;
x ^= x >> 9;
return x;
}
uint64_t rnd(int n){
return rnd() % n;
}
double rnd_double(){
return 1.0 * rnd() / numeric_limits<uint64_t>::max();
}
vector<int> rnd_perm(int n){
vector<int> v(n);
iota(v.begin(), v.end(), 0);
for(int i = n - 1; i >= 1; --i){
int j = rnd(i + 1);
swap(v[i], v[j]);
}
return v;
}
template<typename T>
void shuffle(vector<T>& v){
int n = v.size();
for(int i = n - 1; i >= 1; --i){
int j = rnd(i + 1);
swap(v[i], v[j]);
}
}
};
// #define OPTIMIZE
namespace params{
void load_params(){
ifstream ifs("../params.txt");
assert(ifs.is_open());
}
}
void read_file(istream& ifs){
// TODO: input
}
clock_t st;
void solve(){
constexpr int K = 60;
int n, damage, hp_max;
cin >> n >> damage >> hp_max;
vector<string> s(n);
vector<vector<int>> v(n, vector<int>(n, 0));
vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};
// 0: .
// 1: #
// 2: J (jewel)
// 3: F (fire?)
// 4: E (detecter)
int sx, sy, ex, ey, kx, ky;
vector<pair<pair<int,int>, int>> detectors;
vector<pair<int,int>> jewels_;
for(int i = 0; i < n; ++i){
cin >> s[i];
for(int j = 0; j < n; ++j){
if(s[i][j] == '.'){
v[i][j] = 0;
}
else if(s[i][j] == '#'){
v[i][j] = 1;
}
else if(s[i][j] == 'S'){
sx = i;
sy = j;
}
else if(s[i][j] == 'G'){
ex = i;
ey = j;
}
else if(s[i][j] == 'K'){
kx = i;
ky = j;
}
else if(s[i][j] == 'J'){
v[i][j] = 2;
jewels_.emplace_back(i, j);
}
else if(s[i][j] == 'F'){
v[i][j] = 3;
}
else if(s[i][j] == 'E'){
v[i][j] = 4;
}
}
}
vector<pair<int,int>> jewels;
jewels.emplace_back(sx, sy);
jewels.emplace_back(kx, ky);
jewels.emplace_back(ex, ey);
for(auto& p : jewels_){
jewels.emplace_back(p);
}
int num_detectors;
cin >> num_detectors;
for(int i = 0; i < num_detectors; ++i){
int x, y, d;
cin >> x >> y >> d;
detectors.emplace_back(make_pair(x, y), d);
}
auto is_jewel = [&](int x, int y){
return v[x][y] == 2;
};
auto is_wall = [&](int x, int y){
if(x < 0 || y < 0 || x >= n || y >= n){
return true;
}
return v[x][y] == 1 || v[x][y] == 4;
};
vector<vector<vector<int>>> damage_vec(n, vector<vector<int>>(n, vector<int>(K, 0)));
vector<vector<int>> damage_sum(n, vector<int>(n, 0));
for(auto [p, interval] : detectors){
for(int d = 0; d < 4; ++d){
auto [x, y] = p;
do{
// for(int i = interval - 1; i < K; i += interval){
for(int i = 0; i < K; i += interval){
damage_vec[x][y][i] += damage;
}
damage_sum[x][y] += damage * K / interval;
x += dx[d];
y += dy[d];
}while(!is_wall(x, y));
}
}
int m = jewels.size();
// dijkstra by average damage
vector<vector<double>> dist_ave(m, vector<double>(m, MOD));
vector<vector<vector<int>>> table_move(m, vector<vector<int>>(m));
auto connected = [&](int x, int y){
return dist_ave[x][y] < 1e9;
};
for(int jewel_idx = 0; jewel_idx < m; ++jewel_idx){
// dijkstra
auto [jx, jy] = jewels[jewel_idx];
vector<vector<double>> dist(n, vector<double>(n, MOD));
vector<vector<int>> prev(n, vector<int>(n, -1));
priority_queue<pair<double,pair<int,int>>, vector<pair<double,pair<int,int>>>, greater<>> que;
dist[jx][jy] = 0;
que.emplace(0, make_pair(jx, jy));
while(!que.empty()){
auto [now_dist, p] = que.top();
auto [x, y] = p;
que.pop();
if(now_dist != dist[x][y]){
continue;
}
for(int d = 0; d < 4; ++d){
int nx = x + dx[d];
int ny = y + dy[d];
if(is_wall(nx, ny)){
continue;
}
if(chmin(dist[nx][ny], now_dist + 1.0 * damage_sum[nx][ny] / K + 1)){
prev[nx][ny] = d;
que.emplace(dist[nx][ny], make_pair(nx, ny));
}
}
}
for(int i = 0; i < m; ++i){
dist_ave[jewel_idx][i] = dist[jewels[i].first][jewels[i].second];
int x = jewels[i].first;
int y = jewels[i].second;
if(prev[x][y] == -1){
continue;
}
vector<int> moves;
while(x != jx || y != jy){
int d = prev[x][y];
moves.emplace_back(prev[x][y]);
x += dx[d ^ 2];
y += dy[d ^ 2];
}
reverse(moves.begin(), moves.end());
table_move[jewel_idx][i] = moves;
}
}
auto simulate = [&](vector<int>& moves){
int x = sx, y = sy;
bool key = false;
int turn = 1;
int damage = 0;
int jewel = 0;
set<pair<int,int>> jew;
for(auto d : moves){
if(d < 4){
x += dx[d], y += dy[d];
}
++damage;
damage += damage_vec[x][y][turn % 60];
if(is_jewel(x, y) && !jew.count(make_pair(x, y))){
++jewel;
jew.emplace(x, y);
}
++turn;
assert(!is_wall(x, y));
if(x == kx && y == ky){
key = true;
}
}
assert(x == ex && y == ey);
assert(key);
return make_pair(jewel, damage);
};
auto output = [&](vector<int>& moves){
for(auto d : moves){
// cout << dx[d] << " " << dy[d] << " " << "RDLU"[d] << endl;
if(d < 4){
cout << "M " << "RDLU"[d] << endl;
}
else{
cout << "S" << endl;
}
}
};
Rnd rn(0);
auto get_moves = [&](vector<int>& route){
assert(route.front() == 0);
assert(route.back() == 2);
vector<int> moves;
for(int i = 0; i < route.size() - 1; ++i){
auto [x, y] = jewels[route[i]];
for(auto d : table_move[route[i]][route[i + 1]]){
x += dx[d];
y += dy[d];
moves.emplace_back(d);
}
assert(make_pair(x, y) == jewels[route[i + 1]]);
}
return moves;
};
auto get_optimal_moves = [&](vector<int>& route){
auto moves = get_moves(route);
vector<vector<int>> dp(moves.size() + 1, vector<int>(60, MOD));
vector<vector<int>> pre(moves.size() + 1, vector<int>(60, MOD));
int x = sx, y = sy;
int su = 0;
for(int i = 0; i < 60; ++i){
dp[0][i] = su;
su += damage_vec[x][y][(i + 1) % 60] + 1;
}
for(int i = 0; i < moves.size(); ++i){
int d = moves[i];
int nx = x + dx[d];
int ny = y + dy[d];
auto v = dp[i];
vector<int> v_pre(60);
iota(v_pre.begin(), v_pre.end(), 0);
for(int j = 0; j < 120; ++j){
if(chmin(v[(j + 1) % 60], v[j % 60] + damage_vec[x][y][(j + 1) % 60] + 1)){
v_pre[(j + 1) % 60] = v_pre[j % 60];
}
}
for(int j = 0; j < 60; ++j){
dp[i + 1][(j + 1) % 60] = v[j] + damage_vec[nx][ny][(j + 1) % 60] + 1;
pre[i + 1][(j + 1) % 60] = v_pre[j];
}
x = nx;
y = ny;
}
int j = distance(dp.back().begin(), min_element(dp.back().begin(), dp.back().end()));
vector<int> mods{j};
for(int i = moves.size() - 1; i >= 0; --i){
int pre_j = pre[i + 1][j];
j = pre_j;
mods.emplace_back(j);
}
reverse(mods.begin(), mods.end());
vector<int> res;
for(int i = 0; i < mods[0]; ++i){
// wait
res.emplace_back(5);
}
assert(moves.size() + 1 == mods.size());
for(int i = 0; i < mods.size() - 1; ++i){
int cn = 0;
for(int j_ = mods[i]; (j_ + 1) % 60 != mods[i + 1]; ++j_){
++cn;
res.emplace_back(5);
}
res.emplace_back(moves[i]);
}
return res;
};
auto get_damage = [&](vector<int>& route){
array<int, 60> dp{};
array<int, 60> nex{};
int x = sx, y = sy;
int su = 0;
for(int i = 0; i < 60; ++i){
dp[i] = su;
su += damage_vec[x][y][(i + 1) % 60] + 1;
}
auto moves = get_moves(route);
for(auto d : moves){
int nx = x + dx[d];
int ny = y + dy[d];
assert(!is_wall(x, y));
assert(!is_wall(nx, ny));
for(int i = 0; i < 120; ++i){
chmin(dp[(i + 1) % 60], dp[i % 60] + damage_vec[x][y][(i + 1) % 60] + 1);
}
for(int i = 0; i < 60; ++i){
nex[(i + 1) % 60] = dp[i] + damage_vec[nx][ny][(i + 1) % 60] + 1;
}
x = nx;
y = ny;
swap(dp, nex);
}
// auto moves_ = get_optimal_moves(route);
// auto [sc, dam] = simulate(moves_);
// assert(*min_element(dp.begin(), dp.end()) == dam);
return *min_element(dp.begin(), dp.end());
};
clock_t mid = clock();
double mid_elapsed = 1.0 * (mid - st) / CLOCKS_PER_SEC;
constexpr double TIME_MAX = 3.0;
auto sa = [&](vector<int>& route, vector<int>& fl, double& dist_sum){
while(true){
double tim = 1.0 * (clock() - mid) / CLOCKS_PER_SEC;
double per = tim / (TIME_MAX - mid_elapsed);
if(per >= 1.0){
break;
}
// erase != add
vector<pair<double, int>> erase_adv;
for(int erase_pos = 1; erase_pos < route.size() - 2; ++erase_pos){
int x = route[erase_pos - 1];
int y = route[erase_pos];
int z = route[erase_pos + 1];
if(y == 1){
continue;
}
erase_adv.emplace_back(dist_ave[x][y] + dist_ave[y][z] - dist_ave[x][z], erase_pos);
}
vector<tuple<double, int, int>> add_adv;
for(int add_pos = 1; add_pos < route.size() - 2; ++add_pos){
int x = route[add_pos - 1];
int y = route[add_pos];
for(int j = 3; j < jewels.size(); ++j){
if(fl[j]){
continue;
}
if(!connected(x, j) || !connected(j, y)){
continue;
}
double adv = dist_ave[x][y] - dist_ave[x][j] - dist_ave[j][y];
add_adv.emplace_back(adv, add_pos, j);
}
}
constexpr int T = 3;
nth_element(erase_adv.begin(), erase_adv.begin() + T, erase_adv.end(), greater<>());
nth_element(add_adv.begin(), add_adv.begin() + T, add_adv.end(), greater<>());
tuple<double,int,int,int> bes(-INF, 0, 0, 0);
for(int i = 0; i < T; ++i){
auto [e_val, erase_pos] = erase_adv[i];
for(int j = 0; j < T; ++j){
auto [a_val, add_pos, add_elm] = add_adv[j];
if(erase_pos == add_pos || erase_pos + 1 == add_pos){
continue;
}
chmax(bes, make_tuple(e_val + a_val, erase_pos, add_pos, add_elm));
}
}
auto [adv, erase_pos, add_pos, add_elm] = bes;
// cout << get<0>(bes) << ": " << erase_pos << " " << add_pos << " " << add_elm << endl << endl;
fl[route[erase_pos]] = false;
fl[add_elm] = true;
dist_sum -= dist_ave[route[erase_pos - 1]][route[erase_pos]];
dist_sum -= dist_ave[route[erase_pos]][route[erase_pos + 1]];
dist_sum += dist_ave[route[erase_pos - 1]][route[erase_pos + 1]];
dist_sum += dist_ave[route[add_pos - 1]][add_elm];
dist_sum += dist_ave[add_elm][route[add_pos]];
dist_sum -= dist_ave[route[add_pos - 1]][route[add_pos]];
route.erase(route.begin() + erase_pos);
if(erase_pos < add_pos){
--add_pos;
}
route.insert(route.begin() + add_pos, add_elm);
{
if(dist_sum < hp_max){
return true;
}
}
}
return false;
};
/*
auto sa = [&](vector<int>& route, vector<int>& fl, double& dist_sum){
// int now_damage = get_damage(route);
while(true){
double tim = 1.0 * (clock() - mid) / CLOCKS_PER_SEC;
double per = tim / (TIME_MAX - mid_elapsed);
cout << dist_sum << endl;
if(per >= 1.0){
break;
}
vector<int> bef = route;
int x = rn.rnd(route.size() - 2) + 1;
bool key_emp = route[x] == 1;
int add = key_emp ? 1 : (rn.rnd(jewels.size() - 2) + 2);
if(!key_emp && fl[add]){
continue;
}
int y = rn.rnd(route.size() - 2) + 1;
if(!connected(route[y - 1], add) || !connected(add, route[y])){
continue;
}
fl[route[x]] = false;
fl[add] = true;
double bef_dist_sum = dist_sum;
dist_sum -= dist_ave[route[x - 1]][route[x]];
dist_sum += dist_ave[route[x - 1]][add];
dist_sum += dist_ave[add][route[x]];
route.erase(route.begin() + x);
route.insert(route.begin() + y, add);
{
if(bef_dist_sum < dist_sum){
route = move(bef);
dist_sum = bef_dist_sum;
fl[add] = false;
fl[route[x]] = true;
}else{
if(dist_sum < hp_max){
cout << "OK: " << route.size() << " " << dist_sum << endl;
return true;
}
}
}
{
int nex_damage = get_damage(route);
if(now_damage < nex_damage){
route = move(bef);
fl[add] = false;
fl[route[x]] = true;
}else{
now_damage = nex_damage;
if(now_damage < hp_max){
cout << "OK: " << route.size() << " " << now_damage << endl;
return true;
}
}
}
}
return false;
};
*/
vector<int> fl(jewels.size(), 0);
fl[0] = fl[1] = fl[2] = true;
for(int i = 1; i <= 10; ++i){
fl[i * 10] = true;
}
vector<int> route{0, 10, 20, 30, 40, 50, 1, 60, 70, 80, 90, 100, 2};
double dist_sum = 0;
for(int i = 0; i < route.size() - 1; ++i){
dist_sum += dist_ave[route[i]][route[i + 1]];
}
auto bef = route;
while(true){
if(sa(route, fl, dist_sum)){
/*
auto moves = get_optimal_moves(route);
auto [sc, dam] = simulate(moves);
cout << route.size() << ": " << sc << endl;
*/
bef = route;
if(route.size() == jewels.size()){
break;
}
while(true){
int pos = rn.rnd(route.size() - 2) + 1;
int add = rn.rnd(jewels.size() - 2) + 2;
if(!connected(route[pos - 1], add) || !connected(add, route[pos])){
continue;
}
if(fl[add]){
continue;
}
else{
dist_sum -= dist_ave[route[pos - 1]][route[pos]];
dist_sum += dist_ave[route[pos - 1]][add];
dist_sum += dist_ave[add][route[pos]];
route.insert(route.begin() + pos, add);
fl[add] = true;
break;
}
}
}
else{
route = bef;
break;
}
}
auto moves = get_optimal_moves(route);
output(moves);
auto [sc, dam] = simulate(moves);
clog << "turn: " << moves.size() << endl;
clog << "score: " << sc << endl;
clog << "damage: " << dam << endl;
}
signed main(){
st = clock();
#ifdef OPTIMIZE
params::load_params();
#endif
#ifndef HAND
read_file(cin);
#else
ifstream ifs("./tools/in/0000.txt");
assert(ifs.is_open());
read_file(ifs);
#endif
solve();
}