結果

問題 No.5015 Escape from Labyrinth
ユーザー Yu_212Yu_212
提出日時 2023-04-16 17:49:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,819 ms / 3,000 ms
コード長 17,590 bytes
コンパイル時間 5,876 ms
コンパイル使用メモリ 295,760 KB
実行使用メモリ 43,248 KB
スコア 127,670
最終ジャッジ日時 2023-04-16 17:51:55
合計ジャッジ時間 51,495 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 321 ms
31,836 KB
testcase_01 AC 336 ms
32,788 KB
testcase_02 AC 345 ms
35,464 KB
testcase_03 AC 257 ms
30,748 KB
testcase_04 AC 257 ms
27,280 KB
testcase_05 AC 345 ms
37,948 KB
testcase_06 AC 325 ms
34,272 KB
testcase_07 AC 302 ms
29,876 KB
testcase_08 AC 271 ms
33,376 KB
testcase_09 AC 288 ms
35,424 KB
testcase_10 AC 335 ms
34,092 KB
testcase_11 AC 270 ms
34,204 KB
testcase_12 AC 267 ms
30,116 KB
testcase_13 AC 453 ms
43,248 KB
testcase_14 AC 342 ms
41,420 KB
testcase_15 AC 323 ms
34,228 KB
testcase_16 AC 348 ms
35,816 KB
testcase_17 AC 341 ms
36,044 KB
testcase_18 AC 380 ms
33,716 KB
testcase_19 AC 274 ms
31,920 KB
testcase_20 AC 338 ms
33,604 KB
testcase_21 AC 364 ms
36,472 KB
testcase_22 AC 273 ms
32,044 KB
testcase_23 AC 327 ms
31,884 KB
testcase_24 AC 293 ms
33,236 KB
testcase_25 AC 287 ms
31,444 KB
testcase_26 AC 286 ms
30,032 KB
testcase_27 AC 451 ms
38,660 KB
testcase_28 AC 300 ms
32,360 KB
testcase_29 AC 323 ms
36,024 KB
testcase_30 AC 345 ms
34,624 KB
testcase_31 AC 273 ms
30,844 KB
testcase_32 AC 313 ms
36,068 KB
testcase_33 AC 321 ms
31,140 KB
testcase_34 AC 314 ms
35,224 KB
testcase_35 AC 370 ms
37,656 KB
testcase_36 AC 342 ms
37,020 KB
testcase_37 AC 461 ms
42,276 KB
testcase_38 AC 362 ms
39,972 KB
testcase_39 AC 274 ms
35,032 KB
testcase_40 AC 270 ms
33,328 KB
testcase_41 AC 325 ms
34,080 KB
testcase_42 AC 422 ms
37,584 KB
testcase_43 AC 300 ms
31,236 KB
testcase_44 AC 341 ms
36,452 KB
testcase_45 AC 2,814 ms
38,624 KB
testcase_46 AC 310 ms
36,308 KB
testcase_47 AC 296 ms
33,780 KB
testcase_48 AC 381 ms
38,520 KB
testcase_49 AC 287 ms
34,128 KB
testcase_50 AC 321 ms
33,248 KB
testcase_51 AC 303 ms
33,832 KB
testcase_52 AC 303 ms
34,468 KB
testcase_53 AC 291 ms
33,824 KB
testcase_54 AC 331 ms
37,072 KB
testcase_55 AC 331 ms
36,224 KB
testcase_56 AC 391 ms
37,900 KB
testcase_57 AC 329 ms
35,448 KB
testcase_58 AC 309 ms
34,388 KB
testcase_59 AC 341 ms
31,748 KB
testcase_60 AC 359 ms
33,660 KB
testcase_61 AC 315 ms
32,296 KB
testcase_62 AC 344 ms
33,104 KB
testcase_63 AC 354 ms
34,716 KB
testcase_64 AC 318 ms
32,476 KB
testcase_65 AC 348 ms
34,612 KB
testcase_66 AC 339 ms
33,628 KB
testcase_67 AC 348 ms
34,848 KB
testcase_68 AC 288 ms
33,224 KB
testcase_69 AC 310 ms
35,332 KB
testcase_70 AC 384 ms
37,884 KB
testcase_71 AC 2,817 ms
37,880 KB
testcase_72 AC 321 ms
34,088 KB
testcase_73 AC 347 ms
35,320 KB
testcase_74 AC 296 ms
35,212 KB
testcase_75 AC 282 ms
33,144 KB
testcase_76 AC 375 ms
41,396 KB
testcase_77 AC 278 ms
32,620 KB
testcase_78 AC 376 ms
38,828 KB
testcase_79 AC 308 ms
32,416 KB
testcase_80 AC 318 ms
34,152 KB
testcase_81 AC 257 ms
27,708 KB
testcase_82 AC 282 ms
30,316 KB
testcase_83 AC 281 ms
32,200 KB
testcase_84 AC 338 ms
38,152 KB
testcase_85 AC 2,819 ms
31,324 KB
testcase_86 AC 294 ms
37,252 KB
testcase_87 AC 280 ms
34,540 KB
testcase_88 AC 301 ms
34,960 KB
testcase_89 AC 368 ms
35,544 KB
testcase_90 AC 274 ms
32,592 KB
testcase_91 AC 273 ms
30,324 KB
testcase_92 AC 328 ms
42,740 KB
testcase_93 AC 365 ms
40,356 KB
testcase_94 AC 346 ms
37,532 KB
testcase_95 AC 336 ms
34,016 KB
testcase_96 AC 310 ms
35,708 KB
testcase_97 AC 330 ms
35,700 KB
testcase_98 AC 312 ms
37,000 KB
testcase_99 AC 308 ms
35,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#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 = 2.75;

    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);
                }
            }
            int te = erase_adv.size();
            int ta = add_adv.size();
            sort(erase_adv.begin(), erase_adv.end(), greater<>());
            sort(add_adv.begin(), add_adv.end(), greater<>());

            tuple<double,int,int,int> bes(-INF, 0, 0, 0);
            for(int i = 0; i < te; ++i){
                auto [e_val, erase_pos] = erase_adv[i];
                for(int j = 0; j < ta; ++j){
                    auto [a_val, add_pos, add_elm] = add_adv[j];
                    if(e_val + a_val < get<0>(bes)){
                        break;
                    }
                    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;
            if(adv < 0){
                return false;
            }

            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;
                }
            }
        }
        auto now_damage = get_damage(route);
        if(now_damage < hp_max){
            return true;
        }
        return false;
    };

    vector<int> fl(jewels.size(), 0);
    vector<int> route;

    auto greed = [&](){
        int dist = 0;
        route.emplace_back(0);
        fl[0] = fl[1] = fl[2] = true;
        constexpr double coef = 0.4;
        while(true){
            pair<double,int> mi(INF, 0);
            for(int i = 3; i < m; ++i){
                if(!fl[i]){
                    chmin(mi, make_pair(dist_ave[route.back()][i] + coef * dist_ave[i][1], i));
                }
            }
            if(dist + dist_ave[route.back()][mi.second] + dist_ave[route.back()][1] > hp_max / 2){
                break;
            }
            dist += dist_ave[route.back()][mi.second];
            route.emplace_back(mi.second);
            fl[mi.second] = true;
        }
        route.emplace_back(1);
        while(true){
            pair<double,int> mi(INF, 0);
            for(int i = 3; i < m; ++i){
                if(!fl[i]){
                    chmin(mi, make_pair(dist_ave[route.back()][i] + coef * dist_ave[i][2], i));
                }
            }
            if(dist + dist_ave[route.back()][mi.second] + dist_ave[route.back()][2] > hp_max){
                break;
            }
            dist += dist_ave[route.back()][mi.second];
            route.emplace_back(mi.second);
            fl[mi.second] = true;
        }
        route.emplace_back(2);
    };
    greed();

    /*
    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};
     *

    /*
    vector<int> route{0};
    for(int i = 0; i < min(20, int(jewels.size())); ++i){
        route.emplace_back(i + 2);
    }
    route.emplace_back(1);
    for(int i = 0; i < min(20, int(jewels.size() - 22)); ++i){
        route.emplace_back(i + 22);
    }
    route.emplace_back(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){
        clog << route.size() << endl;
        if(sa(route, fl, dist_sum)){
            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);
}

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();
}
0