#1164243 (C++23) No.5015 Escape from Labyrinth

• 問題: No.5015 Escape from Labyrinth
• ユーザー: FplusFplusF
• 提出日時: 2026-05-10 15:28:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,397 ms / 3,000 ms
• コード長: 9,400 bytes
• コンパイル時間: 2,879 ms
• コンパイル使用メモリ: 357,652 KB
• 実行使用メモリ: 8,548 KB
• スコア: 177,320
• 最終ジャッジ日時: 2026-05-10 15:28:49
• 合計ジャッジ時間: 42,601 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
other	AC * 100

ソースコード

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin_ref(T &a,const T &b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax_ref(T &a,const T &b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

namespace Timer{
    chrono::steady_clock::time_point program_start,start;
    void program_start_snap(){
        program_start=start=chrono::steady_clock::now();
    }
    void snap(){
        start=chrono::steady_clock::now();
    }
    int get_ms(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
        return ms;
    }
    int get_ms_all_program(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
        return ms;
    }
}

mt19937 mt;
uint32_t rand_int(uint32_t r){  //[0,r)
    assert(r!=0);
    return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){  //[l,r)
    assert(l<r);
    return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){  //[0.0,1.0]
    return mt()*one_div_mt_max;
}
double rand_double(double l,double r){  //[l,r]
    return l+rand_double()*(r-l);
}
template<class T> T get_random_element(const vector<T> &v){
    assert(!v.empty());
    return v[rand_int(len(v))];
}

template<class T> void add(vector<T> &a,vector<T> b){
    for(auto i:b) a.push_back(i);
}

constexpr int N=60,H=1500,L=60;

int D,M;

string S;

constexpr string UDLR="UDLR";

vector<int> P,K;

array<array<int,5>,N*N> G;

int Start,Key,Goal;

int one(int i,int j){
    return i*N+j;
}
pii two(int x){
    return {x/N,x%N};
}

namespace Solver{
    array<array<int,L>,N*N> grid_damage;
    
    array<array<int,L>,N*N> dijkstra_cost;
    array<array<pii,L>,N*N> dijkstra_pre;
    array<array<int,L>,N*N> last_vis;
    
    int vis_cnt=0;
    
    void dijkstra(int s,int start_turn,const array<bool,N*N> &vis,bool goal_ng,int g=-1){
        
        vis_cnt++;
        
        dijkstra_cost[s][start_turn%L]=0;
        last_vis[s][start_turn%L]=vis_cnt;
        priority_queue<tii,vector<tii>,greater<tii>> pq;
        pq.push({0,s,start_turn%L});
        
        while(!pq.empty()){
            
            auto [d,x,tx]=pq.top();
            pq.pop();
            if(dijkstra_cost[x][tx]!=d) continue;
            
            if(g==-1&&!vis[x]&&S[x]=='J') break;
            if(g!=-1&&x==g) break;
            
            if(goal_ng&&x==Goal) break;
            
            int ty=(tx+1)%L;
            
            for(auto y:G[x]){
                if(y==-1) continue;
                if(last_vis[y][ty]!=vis_cnt||dijkstra_cost[x][tx]+grid_damage[y][ty]<dijkstra_cost[y][ty]){
                    dijkstra_cost[y][ty]=dijkstra_cost[x][tx]+grid_damage[y][ty];
                    pq.push({dijkstra_cost[y][ty],y,ty});
                    dijkstra_pre[y][ty]={x,tx};
                    last_vis[y][ty]=vis_cnt;
                }
            }
        }
        
    }
    
    vector<int> get_tour(int s,int ts,int g,int tg){
        
        vector<int> ret;
        
        int x=g,tx=tg;
            
        while(!(x==s&&tx==ts)){
            
            ret.push_back(x);
            auto [y,ty]=dijkstra_pre[x][tx];
            assert(y!=-1);
            assert(ty!=-1);
            x=y;
            tx=ty;
        }
        
        reverse(all(ret));
        
        return ret;
    }
    
    vector<int> get_ans(const vector<vector<int>> &tours){
        
        vector<int> ans;
        
        for(const auto &tour:tours){
            
            int s=tour.back();
            
            array<bool,N*N> vis;
            vis.fill(false);
            
            bool have_key=false;
            
            int cost_sum=0;
            
            rep(i,len(tour)){
                vis[tour[i]]=true;
                if(tour[i]==Key) have_key=true;
                cost_sum+=grid_damage[tour[i]][(i+1)%L];
            }
            
            vector<int> now_ans=tour;
            
            int ans_start=s,ans_cost=cost_sum;
            
            if(!have_key){
                dijkstra(s,len(tour),vis,false,Key);
                const auto &key_cost=dijkstra_cost;
                int min_key_cost=INF,tk=-1;
                rep(i,L){
                    if(last_vis[Key][i]==vis_cnt&&chmin(min_key_cost,key_cost[Key][i])) tk=i;
                }
                
                assert(tk!=-1);
                
                add(now_ans,get_tour(s,len(tour)%L,Key,tk));
                ans_start=Key;
                ans_cost+=key_cost[Key][tk];
            }
            
            
            dijkstra(ans_start,len(now_ans),vis,false,Goal);
            
            const auto &goal_cost=dijkstra_cost;
            
            int min_goal_cost=INF,tg=-1;
            rep(i,L){
                if(last_vis[Goal][i]==vis_cnt&&chmin(min_goal_cost,goal_cost[Goal][i])) tg=i;
            }
            assert(tg!=-1);
            
            add(now_ans,get_tour(ans_start,len(now_ans)%L,Goal,tg));
            ans_cost+=goal_cost[Goal][tg];
            if(ans_cost<H){
                return now_ans;
            }
        }
        assert(0);
    }
    
    void solve(){
        
        rep(i,N*N) grid_damage[i].fill(1);
        
        rep(m,M){
            rep(k,4){
                int p=P[m];
                while(p!=-1){
                    p=G[p][k];
                    if(p!=-1){
                        for(int t=0;t<L;t+=K[m]){
                            grid_damage[p][t]+=D;
                        }
                    }
                }
            }
        }
        
        rep(i,N*N){
            dijkstra_cost[i].fill(INF);
            dijkstra_pre[i].fill({-1,-1});
            last_vis[i].fill(-1);
        }
        
        
        int s=Start;
        
        int cost_sum=0;
        
        vector<int> tour;
        
        array<bool,N*N> vis;
        
        vis.fill(false);
        
        bool have_key=false;
        
        
        vector<vector<int>> tours;
        
        while(true){
            
            //cerr << s << " " << len(tours) <<" " <<  cost_sum << endl;
            
            dijkstra(s,len(tour)%L,vis,have_key);
            
            const auto &cost=dijkstra_cost;
            
            int x=-1,tx=-1;
            
            int min_cost=INF;
            
            rep(i,N*N){
                if(vis[i]) continue;
                if(S[i]!='J') continue;
                rep(j,L){
                    if(last_vis[i][j]==vis_cnt&&chmin(min_cost,cost[i][j])){
                        x=i;
                        tx=j;
                    }
                }
            }
            
            if(H<cost_sum+min_cost) break;
            
            vector<int> now_tour=get_tour(s,len(tour)%L,x,tx);
            
            for(auto e:now_tour){
                vis[e]=true;
                tour.push_back(e);
                if(e==Key) have_key=true;
            }
            
            cost_sum+=min_cost;
            
            s=tour.back();
            
            tours.push_back(tour);
            
        }
        
        reverse(all(tours));
        
        
        auto ans=get_ans(tours);
        
        cerr << Timer::get_ms() << endl;
        
        
        int x=Start;
        
        
        for(auto p:ans){
            int t=-1;
            rep(k,5){
                if(G[x][k]==p) t=k;
            }
            assert(t!=-1);
            if(t==4) cout << "S\n";
            else cout << "M " << UDLR[t] << '\n';
            
            x=p;
        }
        
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Timer::program_start_snap();
    
    int n,h;
    
    cin >> n >> D >> h;
    
    rep(i,N){
        string s;
        cin >> s;
        S+=s;
    }
    
    cin >> M;
    
    P.resize(M);
    K.resize(M);
    
    rep(i,M){
        int y,x;
        cin >> y >> x >> K[i];
        P[i]=one(y,x);
    }
    
    vector<int> pi={-1,1,0,0,0},pj={0,0,-1,1,0};
    
    rep(i,N){
        rep(j,N){
            G[one(i,j)].fill(-1);
            
            //if(S[one(i,j)]=='#'||S[one(i,j)]=='E') continue;
            
            rep(k,5){
                int ti=i+pi[k],tj=j+pj[k];
                if(ti<0||N<=ti||tj<0||N<=tj) continue;
                if(S[one(ti,tj)]=='#'||S[one(ti,tj)]=='E') continue;
                G[one(i,j)][k]=one(ti,tj);
            }
        }
    }
    
    rep(i,N*N){
        if(S[i]=='S') Start=i;
        if(S[i]=='K') Key=i;
        if(S[i]=='G') Goal=i;
    }

    Solver::solve();
    exit(0);
}