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

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	FplusFplusF
提出日時	2023-04-16 16:01:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	13,256 bytes
コンパイル時間	4,457 ms
コンパイル使用メモリ	247,056 KB
実行使用メモリ	64,240 KB
スコア	84,630
最終ジャッジ日時	2023-04-16 16:06:13
合計ジャッジ時間	263,050 ms
ジャッジサーバーID （参考情報）	judge15 / judge16

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,822 ms 63,948 KB
testcase_01	RE	-
testcase_02	AC	2,820 ms 63,992 KB
testcase_03	AC	2,819 ms 63,216 KB
testcase_04	AC	2,820 ms 63,424 KB
testcase_05	AC	2,821 ms 63,932 KB
testcase_06	AC	2,822 ms 63,864 KB
testcase_07	RE	-
testcase_08	AC	2,822 ms 63,896 KB
testcase_09	AC	2,819 ms 63,248 KB
testcase_10	AC	2,822 ms 63,320 KB
testcase_11	AC	2,823 ms 64,220 KB
testcase_12	AC	2,821 ms 63,948 KB
testcase_13	AC	2,820 ms 63,240 KB
testcase_14	RE	-
testcase_15	AC	2,821 ms 64,116 KB
testcase_16	AC	2,821 ms 63,480 KB
testcase_17	AC	2,821 ms 63,948 KB
testcase_18	AC	2,820 ms 64,128 KB
testcase_19	AC	2,820 ms 63,768 KB
testcase_20	AC	2,821 ms 63,936 KB
testcase_21	AC	2,821 ms 63,952 KB
testcase_22	AC	2,820 ms 63,828 KB
testcase_23	AC	2,819 ms 63,912 KB
testcase_24	AC	2,821 ms 64,036 KB
testcase_25	AC	2,822 ms 63,304 KB
testcase_26	AC	2,820 ms 63,932 KB
testcase_27	AC	2,820 ms 63,828 KB
testcase_28	AC	2,821 ms 64,036 KB
testcase_29	AC	2,820 ms 64,220 KB
testcase_30	AC	2,821 ms 63,940 KB
testcase_31	AC	2,821 ms 63,924 KB
testcase_32	AC	2,820 ms 63,256 KB
testcase_33	AC	2,820 ms 64,000 KB
testcase_34	AC	2,818 ms 64,144 KB
testcase_35	AC	2,821 ms 63,320 KB
testcase_36	AC	2,820 ms 64,232 KB
testcase_37	AC	2,821 ms 63,668 KB
testcase_38	AC	2,820 ms 63,940 KB
testcase_39	AC	2,819 ms 63,920 KB
testcase_40	AC	2,820 ms 63,364 KB
testcase_41	AC	2,819 ms 63,912 KB
testcase_42	AC	2,821 ms 63,860 KB
testcase_43	AC	2,819 ms 63,672 KB
testcase_44	AC	2,821 ms 63,896 KB
testcase_45	AC	2,822 ms 63,932 KB
testcase_46	AC	2,821 ms 63,944 KB
testcase_47	AC	2,821 ms 63,872 KB
testcase_48	AC	2,819 ms 63,676 KB
testcase_49	AC	2,820 ms 63,896 KB
testcase_50	AC	2,821 ms 63,408 KB
testcase_51	RE	-
testcase_52	AC	2,824 ms 63,936 KB
testcase_53	AC	2,819 ms 63,244 KB
testcase_54	AC	2,819 ms 64,172 KB
testcase_55	AC	2,821 ms 64,156 KB
testcase_56	AC	2,822 ms 64,180 KB
testcase_57	AC	2,819 ms 63,432 KB
testcase_58	AC	2,820 ms 63,896 KB
testcase_59	RE	-
testcase_60	AC	2,820 ms 63,744 KB
testcase_61	AC	2,820 ms 63,852 KB
testcase_62	AC	2,820 ms 64,176 KB
testcase_63	AC	2,819 ms 63,768 KB
testcase_64	AC	2,819 ms 64,116 KB
testcase_65	AC	2,820 ms 64,060 KB
testcase_66	RE	-
testcase_67	RE	-
testcase_68	AC	2,820 ms 64,216 KB
testcase_69	AC	2,819 ms 64,240 KB
testcase_70	RE	-
testcase_71	AC	2,819 ms 63,972 KB
testcase_72	AC	2,820 ms 63,928 KB
testcase_73	RE	-
testcase_74	AC	2,820 ms 63,848 KB
testcase_75	AC	2,821 ms 63,880 KB
testcase_76	AC	2,820 ms 63,244 KB
testcase_77	RE	-
testcase_78	AC	2,820 ms 63,952 KB
testcase_79	AC	2,820 ms 63,940 KB
testcase_80	AC	2,822 ms 63,948 KB
testcase_81	RE	-
testcase_82	AC	2,821 ms 63,792 KB
testcase_83	AC	2,820 ms 64,052 KB
testcase_84	AC	2,819 ms 63,908 KB
testcase_85	AC	2,821 ms 63,248 KB
testcase_86	AC	2,821 ms 63,936 KB
testcase_87	AC	2,820 ms 64,004 KB
testcase_88	RE	-
testcase_89	AC	2,819 ms 64,084 KB
testcase_90	AC	2,820 ms 63,660 KB
testcase_91	AC	2,820 ms 63,768 KB
testcase_92	AC	2,820 ms 63,936 KB
testcase_93	RE	-
testcase_94	AC	2,820 ms 63,924 KB
testcase_95	AC	2,822 ms 63,956 KB
testcase_96	AC	2,820 ms 64,052 KB
testcase_97	AC	2,820 ms 63,932 KB
testcase_98	AC	2,821 ms 63,944 KB
testcase_99	AC	2,820 ms 63,732 KB

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

ソースコード

raw source code

#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{
    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;
        vector<string> now_s=input.s;
        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]&&now_s[ni][nj]=='J') ret.score+=10;
            ret.visited[ni][nj]=true;
            ret.hp--;
            for(int i=ni;0<=i;i--){
                if(now_s[i][nj]=='#'||now_s[i][nj]=='B') break;
                if(now_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(now_s[i][nj]=='#'||now_s[i][nj]=='B') break;
                if(now_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(now_s[ni][j]=='#'||now_s[ni][j]=='B') break;
                if(now_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(now_s[ni][j]=='#'||now_s[ni][j]=='B') break;
                if(now_s[ni][j]=='E'){
                    if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
                    break;
                }
            }
            if(ret.hp<=0){
                ret.score=-1e9;
                ret.hp=-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) return {(int)-1e9,(int)-1e9};
        }
        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;
    }
    vector<vector<int>> min_path_dist;
    string min_path(int si,int sj,int gi,int gj){
        string ret;
        queue<pair<int,int>> q;
        q.push({gi,gj});
        if(gi==input.ki&&gj==input.kj){
            min_path_dist.resize(input.n);
            rep(i,input.n) min_path_dist[i].resize(input.n,-1);
        }
        min_path_dist[gi][gj]=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(min_path_dist[ti][tj]==-1){
                    min_path_dist[ti][tj]=min_path_dist[ni][nj]+1;
                    q.push({ti,tj});
                }
            }
        }
        if(min_path_dist[si][sj]==-1){
            rep(i,input.n){
                rep(j,input.n){
                    min_path_dist[i][j]=-1;
                }
            }
            return "";
        }
        int ni=si,nj=sj;
        while(ni!=gi||nj!=gj){
            int x=0;
            rep(k,4){
                int ti=ni+pi[k],tj=nj+pj[k];
                if(outside(ti,tj)) continue;
                if(min_path_dist[ti][tj]==min_path_dist[ni][nj]-1){
                    x=k;
                    if(input.s[ti][tj]=='J') break;
                }
            }
            int ti=ni+pi[x],tj=nj+pj[x];
            ni=ti;
            nj=tj;
            ret.push_back(dir[x]);
        }
        rep(i,input.n){
            rep(j,input.n){
                min_path_dist[i][j]=-1;
            }
        }
        return ret;
    }
    string min_path_v(int si,int sj,int gi,int gj,vector<pair<int,int>> &v){
        if((int)v.size()==0){
            return min_path(si,sj,gi,gj);
        }
        string ret;
        ret+=min_path(si,sj,v.front().first,v.front().second);
        rep(i,(int)v.size()-1){
            ret+=min_path(v[i].first,v[i].second,v[i+1].first,v[i+1].second);
        }
        ret+=min_path(v.back().first,v.back().second,gi,gj);
        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){
        vector<pair<int,int>> juwel_v;
        vector<vector<bool>> visited=play(first_root).visited;
        rep(i,input.n){
            rep(j,input.n){
                if(!visited[i][j]&&input.s[i][j]=='J'){
                    juwel_v.emplace_back(i,j);
                }
            }
        }
        vector<pair<int,int>> pre_visit;
        vector<pair<int,int>> pre_juwel_v=juwel_v;
        int pre_score=0;
        while(true){
            vector<pair<int,int>> new_visit=pre_visit;
            vector<pair<int,int>> new_juwel_v=pre_juwel_v;
            int r=mt()%10;
            if(r<=3){
                int x=0;
                if((int)new_visit.size()!=0) x=mt()%(int)new_visit.size();
                if((int)new_juwel_v.size()==0) continue;
                int y=mt()%(int)new_juwel_v.size();
                new_visit.insert(new_visit.begin()+x,new_juwel_v[y]);
                juwel_v.erase(new_juwel_v.begin()+y);
            }else if(r<=6){
                if((int)new_visit.size()==0||(int)new_juwel_v.size()==0) continue;
                int x=mt()%(int)new_visit.size();
                int y=mt()%(int)new_juwel_v.size();
                swap(new_visit[x],new_juwel_v[y]);
            }else if(r<=8){
                /*if((int)new_visit.size()==0) continue;
                int a=mt()%(int)new_visit.size();
                int b=mt()%(int)new_visit.size();
                if(a==b) continue;
                if(b<a) swap(a,b);
                reverse(new_visit.begin()+a,new_visit.begin()+b+1);*/
            }else{
                int x=mt()%(int)new_visit.size();
                if(x==0||x==(int)new_visit.size()-1) continue;
                int y=mt()%(int)new_juwel_v.size();
                new_juwel_v.insert(new_juwel_v.begin()+y,new_visit[x]);
                new_visit.erase(new_visit.begin()+x);
            }
            string new_root=first_root+min_path_v(si,sj,gi,gj,new_visit);
            int new_score=max(0,play(new_root).score*play(new_root).score-(int)new_root.size()*(int)new_root.size());
            auto now=chrono::system_clock::now();
            int msec=chrono::duration_cast<chrono::milliseconds>(now-start).count();
            double temp=1000+(0.1-1000)*(double)msec/2800;
            double prob=exp((new_score-pre_score)/temp);
            if(2800<=msec) break;
            if(mt19937::max()<prob){
                /*while(true){
                    bool reversed=false;
                    rep(i,(int)new_visit.size()-1){
                        for(int j=i+2;j<(int)new_visit.size()-1;j++){
                            int x=dist_juwel[new_visit[i].first][new_visit[i].second][new_visit[i+1].first][new_visit[i+1].second];
                            int y=dist_juwel[new_visit[j].first][new_visit[j].second][new_visit[j+1].first][new_visit[j+1].second];
                            int a=dist_juwel[new_visit[i].first][new_visit[i].second][new_visit[j].first][new_visit[j].second];
                            int b=dist_juwel[new_visit[i+1].first][new_visit[i+1].second][new_visit[j+1].first][new_visit[j+1].second];
                            if(a+b<x+y){
                                reverse(new_visit.begin()+i+1,new_visit.begin()+j+1);
                                reversed=true;
                                break;
                            }
                        }
                        if(reversed) break;
                    }
                    if(!reversed) break;
                }*/
                pre_visit=new_visit;
                pre_juwel_v=new_juwel_v;
                pre_score=new_score;
            }
        }
        return first_root+min_path_v(si,sj,gi,gj,pre_visit);
    }
    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);
            }
        }
        string root;
        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);
        for(auto &i:root){
            cout << "M " << i << '\n';
        }
    }
}
solver;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    input.input_cin();
    solver.solve();
}

yukicoder

結果

テストケース

ソースコード