結果

問題 No.5015 Escape from Labyrinth
ユーザー FplusFplusFFplusFplusF
提出日時 2023-04-16 17:49:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,872 ms / 3,000 ms
コード長 14,033 bytes
コンパイル時間 5,207 ms
コンパイル使用メモリ 268,768 KB
実行使用メモリ 63,924 KB
スコア 138,290
最終ジャッジ日時 2023-04-16 17:55:11
合計ジャッジ時間 265,714 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,632 ms
63,644 KB
testcase_01 AC 2,789 ms
63,636 KB
testcase_02 AC 2,693 ms
63,696 KB
testcase_03 AC 2,193 ms
63,716 KB
testcase_04 AC 1,942 ms
63,248 KB
testcase_05 AC 2,737 ms
63,652 KB
testcase_06 AC 2,635 ms
63,568 KB
testcase_07 AC 2,165 ms
63,644 KB
testcase_08 AC 2,530 ms
63,640 KB
testcase_09 AC 1,817 ms
63,644 KB
testcase_10 AC 2,704 ms
63,652 KB
testcase_11 AC 2,722 ms
63,640 KB
testcase_12 AC 2,495 ms
63,636 KB
testcase_13 AC 2,726 ms
63,784 KB
testcase_14 AC 1,555 ms
63,636 KB
testcase_15 AC 2,848 ms
63,696 KB
testcase_16 AC 2,619 ms
63,656 KB
testcase_17 AC 2,620 ms
63,692 KB
testcase_18 AC 2,747 ms
63,792 KB
testcase_19 AC 2,257 ms
63,656 KB
testcase_20 AC 2,771 ms
63,768 KB
testcase_21 AC 2,644 ms
63,764 KB
testcase_22 AC 2,690 ms
63,584 KB
testcase_23 AC 1,762 ms
63,700 KB
testcase_24 AC 2,050 ms
63,728 KB
testcase_25 AC 2,802 ms
63,648 KB
testcase_26 AC 2,694 ms
63,692 KB
testcase_27 AC 2,754 ms
63,604 KB
testcase_28 AC 2,360 ms
63,632 KB
testcase_29 AC 2,418 ms
63,724 KB
testcase_30 AC 2,707 ms
63,692 KB
testcase_31 AC 2,739 ms
63,828 KB
testcase_32 AC 2,734 ms
63,924 KB
testcase_33 AC 2,371 ms
63,712 KB
testcase_34 AC 1,830 ms
63,680 KB
testcase_35 AC 2,682 ms
63,816 KB
testcase_36 AC 2,632 ms
63,628 KB
testcase_37 AC 2,708 ms
63,316 KB
testcase_38 AC 2,770 ms
63,720 KB
testcase_39 AC 1,913 ms
63,764 KB
testcase_40 AC 2,766 ms
63,844 KB
testcase_41 AC 2,716 ms
63,612 KB
testcase_42 AC 2,717 ms
63,660 KB
testcase_43 AC 2,373 ms
63,448 KB
testcase_44 AC 2,067 ms
63,720 KB
testcase_45 AC 2,781 ms
63,844 KB
testcase_46 AC 2,704 ms
63,724 KB
testcase_47 AC 2,646 ms
63,628 KB
testcase_48 AC 2,376 ms
63,432 KB
testcase_49 AC 2,169 ms
63,656 KB
testcase_50 AC 2,673 ms
63,912 KB
testcase_51 AC 2,706 ms
63,612 KB
testcase_52 AC 2,745 ms
63,896 KB
testcase_53 AC 2,651 ms
63,648 KB
testcase_54 AC 1,918 ms
63,568 KB
testcase_55 AC 2,777 ms
63,700 KB
testcase_56 AC 2,872 ms
63,648 KB
testcase_57 AC 2,765 ms
63,912 KB
testcase_58 AC 2,251 ms
63,652 KB
testcase_59 AC 1,895 ms
63,640 KB
testcase_60 AC 2,796 ms
63,484 KB
testcase_61 AC 2,646 ms
63,764 KB
testcase_62 AC 2,655 ms
63,712 KB
testcase_63 AC 2,439 ms
63,544 KB
testcase_64 AC 2,059 ms
63,652 KB
testcase_65 AC 2,713 ms
63,640 KB
testcase_66 AC 2,815 ms
63,648 KB
testcase_67 AC 2,724 ms
63,764 KB
testcase_68 AC 2,784 ms
63,704 KB
testcase_69 AC 2,502 ms
63,640 KB
testcase_70 AC 2,726 ms
63,640 KB
testcase_71 AC 2,619 ms
63,628 KB
testcase_72 AC 2,545 ms
63,840 KB
testcase_73 AC 2,622 ms
63,644 KB
testcase_74 AC 1,945 ms
63,568 KB
testcase_75 AC 2,836 ms
63,576 KB
testcase_76 AC 2,673 ms
63,696 KB
testcase_77 AC 2,757 ms
63,648 KB
testcase_78 AC 2,610 ms
63,848 KB
testcase_79 AC 2,054 ms
63,652 KB
testcase_80 AC 2,758 ms
63,652 KB
testcase_81 AC 2,672 ms
63,764 KB
testcase_82 AC 2,782 ms
63,428 KB
testcase_83 AC 2,162 ms
63,652 KB
testcase_84 AC 2,523 ms
63,720 KB
testcase_85 AC 2,789 ms
63,636 KB
testcase_86 AC 2,618 ms
63,784 KB
testcase_87 AC 2,707 ms
63,768 KB
testcase_88 AC 2,640 ms
63,760 KB
testcase_89 AC 1,693 ms
63,648 KB
testcase_90 AC 2,727 ms
63,316 KB
testcase_91 AC 2,720 ms
63,476 KB
testcase_92 AC 2,166 ms
63,652 KB
testcase_93 AC 2,742 ms
63,780 KB
testcase_94 AC 1,873 ms
63,540 KB
testcase_95 AC 2,758 ms
63,624 KB
testcase_96 AC 2,769 ms
63,552 KB
testcase_97 AC 2,789 ms
63,648 KB
testcase_98 AC 2,187 ms
63,464 KB
testcase_99 AC 1,988 ms
63,448 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
using ll=long long;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll,ll>;
const ll INF=(1ll<<60);
template<class T> void chmin(T &a,T b){
    if(a>b){
        a=b;
    }
}
template<class T> void chmax(T &a,T b){
    if(a<b){
        a=b;
    }
}
auto start=chrono::system_clock::now();
mt19937 mt;
vector<int> pi={0,1,0,-1},pj={1,0,-1,0};
string dir="RDLU";
struct enemy{
    int i,j,d;
};
struct input{
    int n,d,h;
    vector<string> s;
    int m;
    vector<enemy> e;
    vector<vector<int>> grid_enemy;
    int si,sj,ki,kj,gi,gj;
    void input_cin(){
        cin >> n >> d >> h;
        s.resize(n);
        rep(i,n) cin >> s[i];
        cin >> m;
        e.resize(m);
        grid_enemy.resize(n);
        rep(i,n) grid_enemy[i].resize(n,0);
        rep(i,m){
            cin >> e[i].i >> e[i].j >> e[i].d;
            grid_enemy[e[i].i][e[i].j]=e[i].d;
        }
        rep(i,n){
            rep(j,n){
                if(s[i][j]=='S'){
                    si=i;
                    sj=j;
                }
                if(s[i][j]=='K'){
                    ki=i;
                    kj=j;
                }
                if(s[i][j]=='G'){
                    gi=i;
                    gj=j;
                }
            }
        }
    }
}
input;
struct solver{
    vector<vector<double>> grid;
    struct result{
        int score,hp;
        vector<vector<bool>> visited;
    };
    bool outside(int i,int j){
        if(i<0||input.n<=i||j<0||input.n<=j) return true;
        else return false;
    }
    int char_idx(char c){
        if(c=='R') return 0;
        else if(c=='D') return 1;
        else if(c=='L') return 2;
        else return 3;
    }
    int dist_root(vector<pair<int,int>> &v,vector<vector<vector<vector<int>>>> &dist_juwel){
        int n=v.size();
        int ret=0;
        rep(i,n-1){
            int d=dist_juwel[v[i].first][v[i].second][v[i+1].first][v[i+1].second];
            if(d==-1) return 1e9;
            ret+=d;
        }
        return ret;
    }
    result play(string &s){
        int nt=s.size();
        int ni=input.si,nj=input.sj;
        vector<vector<bool>> visited(input.n,vector<bool>(input.n));
        result ret={0,input.h,visited};
        ret.visited[ni][nj]=true;
        rep(t,nt){
            ni+=pi[char_idx(s[t])];
            nj+=pj[char_idx(s[t])];
            if(outside(ni,nj)){
                ret.score=-1e9;
                ret.hp=-1e9;
                return ret;
            }
            if(!ret.visited[ni][nj]&&input.s[ni][nj]=='J') ret.score+=10;
            ret.visited[ni][nj]=true;
            ret.hp--;
            for(int i=ni;0<=i;i--){
                if(input.s[i][nj]=='#') break;
                if(input.s[i][nj]=='E'){
                    if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d;
                    break;
                }
            }
            for(int i=ni;i<input.n;i++){
                if(input.s[i][nj]=='#') break;
                if(input.s[i][nj]=='E'){
                    if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d;
                    break;
                }
            }
            for(int j=nj;0<=j;j--){
                if(input.s[ni][j]=='#') break;
                if(input.s[ni][j]=='E'){
                    if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
                    break;
                }
            }
            for(int j=nj;j<input.n;j++){
                if(input.s[ni][j]=='#') break;
                if(input.s[ni][j]=='E'){
                    if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
                    break;
                }
            }
            if(ret.hp<=0){
                ret.score=(int)-1e9;
                ret.hp=(int)-1e9;
                return ret;
            }
        }
        if(ni==input.gi&&nj==input.gj) ret.hp++;
        else{
            ret.score=-1e9;
            //ret.hp=0;
        }
        return ret;
    }
    result play_free(int si,int sj,string &s){
        int nt=s.size();
        int ni=si,nj=sj;
        vector<vector<bool>> visited(input.n,vector<bool>(input.n));
        result ret={0,input.h,visited};
        ret.visited[ni][nj]=true;
        rep(t,nt){
            ni+=pi[char_idx(s[t])];
            nj+=pj[char_idx(s[t])];
            if(outside(ni,nj)){
                ret.score=-1e9;
                ret.hp=-1e9;
                return ret;
            }
            if(!ret.visited[ni][nj]&&input.s[ni][nj]=='J') ret.score+=10;
            ret.visited[ni][nj]=true;
            ret.hp--;
            for(int i=ni;0<=i;i--){
                if(input.s[i][nj]=='#') break;
                if(input.s[i][nj]=='E'){
                    if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d;
                    break;
                }
            }
            for(int i=ni;i<input.n;i++){
                if(input.s[i][nj]=='#') break;
                if(input.s[i][nj]=='E'){
                    if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d;
                    break;
                }
            }
            for(int j=nj;0<=j;j--){
                if(input.s[ni][j]=='#') break;
                if(input.s[ni][j]=='E'){
                    if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
                    break;
                }
            }
            for(int j=nj;j<input.n;j++){
                if(input.s[ni][j]=='#') break;
                if(input.s[ni][j]=='E'){
                    if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
                    break;
                }
            }
            if(ret.hp<=0){
                ret.score=(int)-1e9;
                ret.hp=(int)-1e9;
                return ret;
            }
        }
        if(ni==input.gi&&nj==input.gj) ret.hp++;
        else{
            ret.score=-1e9;
            //ret.hp=0;
        }
        return ret;
    }
    vector<vector<int>> bfs(int si,int sj){
        queue<pair<int,int>> q;
        q.push({si,sj});
        vector<vector<int>> dist(input.n,vector<int>(input.n,-1));
        dist[si][sj]=0;
        while(!q.empty()){
            int ni,nj;
            tie(ni,nj)=q.front();
            q.pop();
            rep(k,4){
                int ti=ni+pi[k],tj=nj+pj[k];
                if(outside(ti,tj)) continue;
                if(input.s[ti][tj]=='#'||input.s[ti][tj]=='E') continue;
                if(dist[ti][tj]==-1){
                    dist[ti][tj]=dist[ni][nj]+1;
                    q.push({ti,tj});
                }
            }
        }
        return dist;
    }
    string min_path(int si,int sj,int gi,int gj){
        string ret;
        priority_queue<tuple<double,int,int>,vector<tuple<double,int,int>>,greater<tuple<double,int,int>>> pq;
        pq.push({0,gi,gj});
        vector<vector<double>> dist(input.n,vector<double>(input.n,1e9));
        vector<vector<pair<int,int>>> per(input.n,vector<pair<int,int>>(input.n));
        dist[gi][gj]=0;
        while(!pq.empty()){
            int d,ni,nj;
            tie(d,ni,nj)=pq.top();
            pq.pop();
            rep(k,4){
                int ti=ni+pi[k],tj=nj+pj[k];
                if(outside(ti,tj)) continue;
                if(input.s[ti][tj]=='#'||input.s[ti][tj]=='E') continue;
                if(d+grid[ti][tj]<dist[ti][tj]){
                    dist[ti][tj]=d+grid[ti][tj];
                    per[ti][tj]={ni,nj};
                    pq.push({d+grid[ti][tj],ti,tj});
                }
            }
        }
        if(dist[si][sj]==1e9) return "";
        int ni=si,nj=sj;
        while(ni!=gi||nj!=gj){
            rep(k,4){
                int ti=ni+pi[k],tj=nj+pj[k];
                if(outside(ti,tj)) continue;
                if(per[ni][nj]==make_pair(ti,tj)){
                    ni=ti;
                    nj=tj;
                    ret.push_back(dir[k]);
                    break;
                }
            }
        }
        return ret;
    }
    string solve_root(string first_root,int si,int sj,int gi,int gj,int min_hp,vector<vector<vector<vector<int>>>> &dist_juwel){
        string root=first_root;
        vector<pair<int,int>> visit_juwel;
        int ni=si,nj=sj;
        while(true){
            vector<vector<bool>> visited=play(root).visited;
            bool first_flag=true,end_flag=false;
            while(true){
                vector<vector<int>> dist=bfs(ni,nj);
                pair<int,pair<int,int>> p={(int)1e9,{0,0}};
                rep(i,input.n){
                    rep(j,input.n){
                        if(dist[i][j]==-1) continue;
                        if(!visited[i][j]&&input.s[i][j]=='J') chmin(p,{dist[i][j],{i,j}});
                    }
                }
                if(p.first==1e9) break;
                int ti,tj;
                tie(ti,tj)=p.second;
                string new_root=root;
                new_root+=min_path(ni,nj,ti,tj);
                string new_new_root=new_root+min_path(ti,tj,gi,gj);
                if(play(new_new_root).hp<=min_hp){
                    if(first_flag) end_flag=true;
                    break;
                }
                visit_juwel.emplace_back(ti,tj);
                result res=play(new_root);
                ni=ti;
                nj=tj;
                root=new_root;
                visited=res.visited;
                first_flag=false;
            }
            if(end_flag) break;
            int n=visit_juwel.size();
            if(n==0) break;
            while(true){
                bool reversed=false;
                rep(i,n-1){
                    for(int j=i+2;j<n-1;j++){
                        int x=dist_juwel[visit_juwel[i].first][visit_juwel[i].second][visit_juwel[i+1].first][visit_juwel[i+1].second];
                        int y=dist_juwel[visit_juwel[j].first][visit_juwel[j].second][visit_juwel[j+1].first][visit_juwel[j+1].second];
                        int a=dist_juwel[visit_juwel[i].first][visit_juwel[i].second][visit_juwel[j].first][visit_juwel[j].second];
                        int b=dist_juwel[visit_juwel[i+1].first][visit_juwel[i+1].second][visit_juwel[j+1].first][visit_juwel[j+1].second];
                        if(a+b<x+y){
                            reverse(visit_juwel.begin()+i+1,visit_juwel.begin()+j+1);
                            reversed=true;
                            break;
                        }
                    }
                    if(reversed) break;
                }
                if(!reversed) break;
            }
            string new_root=first_root;
            if((int)visit_juwel.size()!=0){
                new_root+=min_path(si,sj,visit_juwel.front().first,visit_juwel.front().second);
                rep(i,n-1){
                    new_root+=min_path(visit_juwel[i].first,visit_juwel[i].second,visit_juwel[i+1].first,visit_juwel[i+1].second);
                }
            }
            string new_new_root=new_root;
            new_new_root+=min_path(visit_juwel.back().first,visit_juwel.back().second,gi,gj);
            if(play(new_new_root).hp<=min_hp) break;
            root=new_root;
            ni=visit_juwel.back().first;
            nj=visit_juwel.back().second;
        }
        root+=min_path(ni,nj,gi,gj);
        return root;
    }
    void solve(){
        vector<vector<vector<vector<int>>>> dist_juwel(input.n,vector<vector<vector<int>>>(input.n,vector<vector<int>>(input.n,vector<int>(input.n,-1))));
        rep(i,input.n){
            rep(j,input.n){
                if(input.s[i][j]=='J') dist_juwel[i][j]=bfs(i,j);
            }
        }
        grid.resize(input.n);
        rep(ni,input.n){
            grid[ni].resize(input.n,100);
            rep(nj,input.n){
                if(input.s[ni][nj]=='J') grid[ni][nj]-=50;
                for(int i=ni;0<=i;i--){
                    if(input.s[i][nj]=='#') break;
                    if(input.s[i][nj]=='E'){
                        grid[ni][nj]+=input.d*(1/(double)input.grid_enemy[i][nj]);
                    }
                }
                for(int i=ni;i<input.n;i++){
                    if(input.s[i][nj]=='#') break;
                    if(input.s[i][nj]=='E'){
                        grid[ni][nj]+=input.d*(1/(double)input.grid_enemy[i][nj]);
                    }
                }
                for(int j=nj;0<=j;j--){
                    if(input.s[ni][j]=='#') break;
                    if(input.s[ni][j]=='E'){
                        grid[ni][nj]+=input.d*(1/(double)input.grid_enemy[ni][j]);
                    }
                }
                for(int j=nj;j<input.n;j++){
                    if(input.s[ni][j]=='#') break;
                    if(input.s[ni][j]=='E'){
                        grid[ni][nj]+=input.d*(1/input.grid_enemy[ni][j]);
                    }
                }
            }
        }
        pair<int,string> ans={(int)-1e9,""};
        string root=min_path(input.si,input.sj,input.ki,input.kj);
        root=solve_root(root,input.ki,input.kj,input.gi,input.gj,0,dist_juwel);
        chmax(ans,{play(root).score,root});
        string x=min_path(input.ki,input.kj,input.gi,input.gj);
        root="";
        root=solve_root(root,input.si,input.sj,input.ki,input.kj,input.h-play_free(input.ki,input.kj,x).hp,dist_juwel);
        root+=x;
        chmax(ans,{play(root).score,root});
        for(int i=100;i<=input.h-100;i+=100){
            auto now=chrono::system_clock::now();
            if(2600<=chrono::duration_cast<chrono::milliseconds>(now-start).count()) break;
            root="";
            root=solve_root(root,input.si,input.sj,input.ki,input.kj,i,dist_juwel);
            root=solve_root(root,input.ki,input.kj,input.gi,input.gj,0,dist_juwel);
            chmax(ans,{play(root).score,root});
        }
        for(auto &i:ans.second){
            cout << "M " << i << '\n';
        }
    }
}
solver;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    input.input_cin();
    solver.solve();
}
0