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

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	Yu_212
提出日時	2023-04-16 16:43:33
言語	C++17 (gcc 12.3.0 + boost 1.83.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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	TLE	-
testcase_31	TLE	-
testcase_32	TLE	-
testcase_33	TLE	-
testcase_34	TLE	-
testcase_35	TLE	-
testcase_36	TLE	-
testcase_37	TLE	-
testcase_38	TLE	-
testcase_39	TLE	-
testcase_40	TLE	-
testcase_41	TLE	-
testcase_42	TLE	-
testcase_43	TLE	-
testcase_44	TLE	-
testcase_45	TLE	-
testcase_46	TLE	-
testcase_47	TLE	-
testcase_48	TLE	-
testcase_49	TLE	-
testcase_50	TLE	-
testcase_51	TLE	-
testcase_52	TLE	-
testcase_53	TLE	-
testcase_54	TLE	-
testcase_55	TLE	-
testcase_56	TLE	-
testcase_57	TLE	-
testcase_58	TLE	-
testcase_59	TLE	-
testcase_60	TLE	-
testcase_61	TLE	-
testcase_62	TLE	-
testcase_63	TLE	-
testcase_64	TLE	-
testcase_65	TLE	-
testcase_66	TLE	-
testcase_67	TLE	-
testcase_68	TLE	-
testcase_69	TLE	-
testcase_70	TLE	-
testcase_71	TLE	-
testcase_72	TLE	-
testcase_73	TLE	-
testcase_74	TLE	-
testcase_75	TLE	-
testcase_76	TLE	-
testcase_77	TLE	-
testcase_78	TLE	-
testcase_79	TLE	-
testcase_80	TLE	-
testcase_81	TLE	-
testcase_82	TLE	-
testcase_83	TLE	-
testcase_84	TLE	-
testcase_85	TLE	-
testcase_86	TLE	-
testcase_87	TLE	-
testcase_88	TLE	-
testcase_89	TLE	-
testcase_90	TLE	-
testcase_91	TLE	-
testcase_92	TLE	-
testcase_93	TLE	-
testcase_94	TLE	-
testcase_95	TLE	-
testcase_96	TLE	-
testcase_97	TLE	-
testcase_98	TLE	-
testcase_99	TLE	-

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

ソースコード

raw source code

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

}

yukicoder

結果

テストケース

ソースコード