#860264 (C++17) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	Yu_212
提出日時	2023-04-16 17:39:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	22,121 bytes
コンパイル時間	6,253 ms
コンパイル使用メモリ	296,276 KB
実行使用メモリ	43,388 KB
スコア	168,300
最終ジャッジ日時	2023-04-16 17:42:44
合計ジャッジ時間	77,850 ms
ジャッジサーバーID （参考情報）	judge14 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	630 ms 31,788 KB
testcase_01	AC	2,842 ms 33,168 KB
testcase_02	AC	655 ms 35,980 KB
testcase_03	AC	2,812 ms 31,008 KB
testcase_04	AC	2,812 ms 27,296 KB
testcase_05	AC	2,817 ms 37,832 KB
testcase_06	AC	2,838 ms 34,256 KB
testcase_07	AC	2,835 ms 29,940 KB
testcase_08	AC	694 ms 33,332 KB
testcase_09	AC	634 ms 35,336 KB
testcase_10	AC	2,818 ms 34,368 KB
testcase_11	AC	744 ms 34,032 KB
testcase_12	AC	2,811 ms 30,396 KB
testcase_13	AC	1,145 ms 43,388 KB
testcase_14	AC	758 ms 42,092 KB
testcase_15	AC	2,841 ms 34,116 KB
testcase_16	AC	755 ms 35,696 KB
testcase_17	AC	842 ms 36,016 KB
testcase_18	AC	835 ms 33,720 KB
testcase_19	AC	630 ms 32,196 KB
testcase_20	AC	2,867 ms 33,680 KB
testcase_21	AC	755 ms 36,500 KB
testcase_22	AC	2,839 ms 31,992 KB
testcase_23	AC	2,815 ms 31,876 KB
testcase_24	AC	826 ms 33,204 KB
testcase_25	AC	562 ms 31,636 KB
testcase_26	AC	537 ms 30,044 KB
testcase_27	AC	1,356 ms 38,788 KB
testcase_28	AC	2,815 ms 32,224 KB
testcase_29	AC	1,051 ms 36,512 KB
testcase_30	AC	2,816 ms 34,616 KB
testcase_31	AC	517 ms 31,028 KB
testcase_32	AC	634 ms 36,732 KB
testcase_33	AC	684 ms 31,152 KB
testcase_34	AC	2,838 ms 35,284 KB
testcase_35	AC	2,817 ms 37,528 KB
testcase_36	AC	952 ms 36,888 KB
testcase_37	AC	2,844 ms 42,400 KB
testcase_38	AC	2,829 ms 39,972 KB
testcase_39	AC	645 ms 35,164 KB
testcase_40	AC	789 ms 33,244 KB
testcase_41	AC	872 ms 33,980 KB
testcase_42	AC	2,819 ms 37,872 KB
testcase_43	AC	2,838 ms 31,820 KB
testcase_44	AC	777 ms 36,828 KB
testcase_45	AC	2,819 ms 38,464 KB
testcase_46	AC	2,850 ms 36,776 KB
testcase_47	AC	595 ms 33,924 KB
testcase_48	AC	2,821 ms 38,772 KB
testcase_49	AC	556 ms 34,176 KB
testcase_50	AC	507 ms 33,308 KB
testcase_51	AC	674 ms 33,732 KB
testcase_52	AC	740 ms 34,408 KB
testcase_53	AC	2,815 ms 33,872 KB
testcase_54	AC	704 ms 37,084 KB
testcase_55	AC	640 ms 36,276 KB
testcase_56	AC	948 ms 37,916 KB
testcase_57	AC	892 ms 35,616 KB
testcase_58	AC	2,838 ms 34,404 KB
testcase_59	AC	721 ms 31,936 KB
testcase_60	AC	2,845 ms 33,612 KB
testcase_61	AC	2,843 ms 32,292 KB
testcase_62	AC	2,843 ms 33,152 KB
testcase_63	AC	2,866 ms 34,964 KB
testcase_64	AC	2,824 ms 33,052 KB
testcase_65	AC	2,845 ms 34,040 KB
testcase_66	AC	960 ms 33,456 KB
testcase_67	AC	641 ms 35,144 KB
testcase_68	AC	2,845 ms 33,216 KB
testcase_69	AC	2,819 ms 35,540 KB
testcase_70	TLE	-
testcase_71	AC	1,214 ms 37,944 KB
testcase_72	AC	820 ms 34,208 KB
testcase_73	AC	2,865 ms 35,508 KB
testcase_74	AC	788 ms 35,148 KB
testcase_75	AC	787 ms 33,364 KB
testcase_76	AC	2,843 ms 41,576 KB
testcase_77	AC	2,843 ms 32,744 KB
testcase_78	AC	1,123 ms 38,828 KB
testcase_79	AC	892 ms 32,676 KB
testcase_80	AC	2,849 ms 34,208 KB
testcase_81	AC	2,813 ms 27,784 KB
testcase_82	AC	641 ms 30,852 KB
testcase_83	AC	860 ms 32,060 KB
testcase_84	AC	2,843 ms 38,820 KB
testcase_85	AC	508 ms 31,460 KB
testcase_86	AC	838 ms 37,768 KB
testcase_87	AC	2,878 ms 34,680 KB
testcase_88	AC	792 ms 35,132 KB
testcase_89	AC	2,866 ms 35,676 KB
testcase_90	AC	2,868 ms 32,540 KB
testcase_91	AC	516 ms 30,360 KB
testcase_92	AC	2,848 ms 42,992 KB
testcase_93	AC	2,825 ms 40,420 KB
testcase_94	AC	2,821 ms 37,612 KB
testcase_95	AC	726 ms 34,192 KB
testcase_96	AC	789 ms 35,628 KB
testcase_97	AC	715 ms 35,660 KB
testcase_98	AC	2,821 ms 37,524 KB
testcase_99	AC	669 ms 36,192 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
                }
            }
            constexpr size_t T = 10000;
            int te = min(erase_adv.size(), T);
            int ta = min(add_adv.size(), T);
            // nth_element(erase_adv.begin(), erase_adv.begin() + te, erase_adv.end(), greater<>());
            // nth_element(add_adv.begin(), add_adv.begin() + ta, add_adv.end(), greater<>());
            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;
                }
            }
        }
        return false;
    };

    auto sa2 = [&](vector<int>& route, vector<int>& fl, double& dist_sum){
        // cout << "sa2" << endl;
        auto now_damage = get_damage(route);
        if(now_damage < hp_max){
            return true;
        }
        /*
        // TODO: koko iranai kamo
        while(true){
            // cout << "sa2 iter" << endl;
            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 size_t T = 3;
            int te = min(erase_adv.size(), T);
            int ta = min(add_adv.size(), T);
            nth_element(erase_adv.begin(), erase_adv.begin() + te, erase_adv.end(), greater<>());
            nth_element(add_adv.begin(), add_adv.begin() + ta, add_adv.end(), greater<>());
            // sort(erase_adv.begin(), erase_adv.end(), greater<>());
            // sort(add_adv.begin(), add_adv.end(), greater<>());

            tuple<int,int,int,int> bes(MOD, 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;
                    }

                    // TODO
                    fl[route[erase_pos]] = false;
                    fl[add_elm] = true;
                    auto nex_route = route;
                    nex_route.erase(nex_route.begin() + erase_pos);
                    if(erase_pos < add_pos){
                        --add_pos;
                    }
                    nex_route.insert(nex_route.begin() + add_pos, add_elm);
                    auto nex_damage = get_damage(nex_route);
                    if(now_damage < nex_damage){
                        // NG
                    }
                    else{
                        // OK
                        chmin(bes, make_tuple(nex_damage, erase_pos, add_pos, add_elm));
                    }
                }
            }
            if(get<0>(bes) < now_damage){
                auto [nex_damage, erase_pos, add_pos, add_elm] = bes;
                now_damage = nex_damage;
                fl[route[erase_pos]] = false;
                fl[add_elm] = true;
                route.erase(route.begin() + erase_pos);
                if(erase_pos < add_pos){
                    --add_pos;
                }
                route.insert(route.begin() + add_pos, add_elm);
                if(nex_damage < hp_max){
                    // cout << "OK: " << route.size() << endl;
                    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.2;
        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) || sa2(route, fl, dist_sum)){
            // auto moves = get_optimal_moves(route);
            // auto [sc, dam] = simulate(moves);
            // cout << route.size() << ": " << sc << " " << dam << 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;
        }
    }

    sa2(route, fl, dist_sum);

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

yukicoder

結果

テストケース

ソースコード