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

• 問題: No.5015 Escape from Labyrinth
• ユーザー: FplusFplusF
• 提出日時: 2026-05-11 08:25:13
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2,958 ms / 3,000 ms
• コード長: 14,482 bytes
• コンパイル時間: 5,301 ms
• コンパイル使用メモリ: 360,500 KB
• 実行使用メモリ: 109,184 KB
• スコア: 210,170
• 最終ジャッジ日時: 2026-05-11 08:29:19
• 合計ジャッジ時間: 245,274 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
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;
    }
}
//参考：https://ei1333.github.io/library/other/xor-shift.hpp.html

namespace Random{
    uint64_t x=88172645463325252;
    constexpr uint32_t mask=numeric_limits<uint32_t>::max();
    constexpr double k=1.0/(double)(numeric_limits<uint64_t>::max());
    inline uint64_t xorshift64(){
        x^=x<<7;
        x^=x>>9;
        return x;
    }
    inline uint32_t rand_int(uint32_t r){  //[0,r)
        assert(r!=0);
        return (xorshift64()&mask)*r>>32;
    }
    inline int rand_int(int l,int r){  //[l,r)
        assert(l<=r);
        return l+rand_int(r-l);
    }
    inline double rand_double(){  // [0.0,1.0]
        return xorshift64()*k;
    }
}
using Random::rand_int,Random::rand_double;

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

template<class SA_State,int limit_ms,double start_temp,double end_temp=0.0> SA_State SA(const SA_State &first_state){

    SA_State state=first_state,best_state=state;
    

    
    int loop_cnt=0,accept_cnt=0,update_cnt=0;
    
    int ms=0;
    
    double temp=start_temp;
    
    Timer::snap();
    
    
    constexpr int b=16,sz=1<<b;
    
    array<double,sz> log_rd;
    
    rep(i,sz) log_rd[i]=log(rand_double());
    
    
    while(true){

        if((loop_cnt&1023)==1023){
            
            ms=Timer::get_ms();
            
            if(limit_ms<=ms) break;
            
            temp=start_temp-(start_temp-end_temp)/limit_ms*ms;
        }
        
        loop_cnt++;
        
        double accept_diff=log_rd[loop_cnt&(sz-1)]*temp;

        bool accepted=state.modify(accept_diff);
        
        
        if(accepted){
            
            accept_cnt++;
        
            if(state.score<best_state.score){
                best_state=state;
                //cerr << "score:" << (int)best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
                update_cnt++;
            }
        }
    }

    
    cerr << "[result] " << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << endl;
    
    return best_state;
};


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;
    
    
    
    pair<vector<int>,vector<int>> dijkstra_cost(int s,int start_turn,bool goal_ng,const vector<int> &gs){
        
        static array<int,N*N> cost;
        static array<int,N*N> turn;
        static array<int,N*N> last_vis;
    
        static int vis_cnt=0;
        
        if(vis_cnt==0){
            rep(i,N*N){
            }
            cost.fill(INF);
            turn.fill(-1);
            last_vis.fill(-1);
        }
        
        vis_cnt++;
        
        int ts=start_turn%L;
        
        cost[s]=0;
        last_vis[s]=vis_cnt;
        turn[s]=0;
        
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        pq.push({0,s});
        
        unordered_set<int> st(all(gs));
        
        while(!pq.empty()){
            
            auto [d,x]=pq.top();
            pq.pop();
            
            if(cost[x]!=d) continue;
            
            if(st.contains(x)){
                st.erase(x);
                if(st.empty()) break;
            }
            
            if(goal_ng&&x==Goal) continue;
            
            int ty=(ts+turn[x]+1)%L;
            
            for(auto y:G[x]){
                if(y==-1) continue;
                if(last_vis[y]!=vis_cnt||cost[x]+grid_damage[y][ty]<cost[y]){
                    cost[y]=cost[x]+grid_damage[y][ty];
                    pq.push({cost[y],y});
                    turn[y]=turn[x]+1;
                    last_vis[y]=vis_cnt;
                }
            }
        }
        
        vector<int> ret_cost,ret_turn;
        
        for(auto g:gs){
            assert(last_vis[g]==vis_cnt);
            ret_cost.push_back(cost[g]);
            ret_turn.push_back(turn[g]);
        }
        return {ret_cost,ret_turn};
    }
    
    vector<int> dijkstra_route(int s,int start_turn,bool goal_ng,int g){
        
        static array<int,N*N> cost;
        static array<int,N*N> turn;
        static array<int,N*N> last_vis;
        static array<int,N*N> pre;
    
        static int vis_cnt=0;
        
        if(vis_cnt==0){
            rep(i,N*N){
            }
            cost.fill(INF);
            turn.fill(-1);
            last_vis.fill(-1);
            pre.fill(-1);
        }
        
        vis_cnt++;
        
        int ts=start_turn%L;
        
        cost[s]=0;
        last_vis[s]=vis_cnt;
        turn[s]=0;
        
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        pq.push({0,s});
        
        
        while(!pq.empty()){
            
            auto [d,x]=pq.top();
            pq.pop();
            
            if(cost[x]!=d) continue;
            
            if(x==g) break;
            
            if(goal_ng&&x==Goal) continue;
            
            int ty=(ts+turn[x]+1)%L;
            
            for(auto y:G[x]){
                if(y==-1) continue;
                if(last_vis[y]!=vis_cnt||cost[x]+grid_damage[y][ty]<cost[y]){
                    cost[y]=cost[x]+grid_damage[y][ty];
                    pq.push({cost[y],y});
                    turn[y]=turn[x]+1;
                    last_vis[y]=vis_cnt;
                    pre[y]=x;
                }
            }
        }
        
        
        vector<int> ret;
        
        int x=g;
            
        while(!(x==s)){
            
            ret.push_back(x);
            int y=pre[x];
            assert(y!=-1);
            x=y;
        }
        
        reverse(all(ret));
        
        return ret;
    }
    
    array<array<int,N*N>,N*N> two_dist;
    array<array<int,N*N>,N*N> two_dist_pre;
    
    struct SA_State{
        vector<int> pos;
        int sz=0;
        int score=INF;
        
        SA_State(){
            pos.push_back(Start);
            rep(i,N*N){
                if((S[i]=='J'||i==Key)&&two_dist[Start][i]!=INF) pos.push_back(i);
            }
            pos.push_back(Goal);
            
            sz=len(pos);
            
            score=calc_score();
        }
        
        int calc_score() const{
            int ret=0;
            rep(i,sz-1){
                ret+=two_dist[pos[i]][pos[i+1]];
            }
            return ret;
        }
        
        bool modify(double accept_diff){
            
            int l=rand_int(1,sz-1),r=rand_int(1,sz-1);
            if(l==r) return false;
            if(r<l) swap(l,r);
            
            
            int new_score=score;
            
            new_score-=two_dist[pos[l-1]][pos[l]];
            new_score+=two_dist[pos[l-1]][pos[r]];
            new_score-=two_dist[pos[r]][pos[r+1]];
            new_score+=two_dist[pos[l]][pos[r+1]];
            
            if(accept_diff<=score-new_score){
                reverse(pos.begin()+l,pos.begin()+r+1);
                score=new_score;
                return true;
            }else{
                return false;
            }
        }
    };
    
    void output_ans(vector<int> ans){
        
        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;
        }
    }
    
    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(s,N*N){
            
            
            two_dist[s].fill(INF);
            two_dist[s][s]=0;
            two_dist_pre[s].fill(-1);
            
            queue<int> q;
            q.push(s);
            
            while(!q.empty()){
                int x=q.front();
                q.pop();
                
                if(x==Goal) continue;  //Goalを閉じて途中で終了しないようにごまかしている
                
                for(auto y:G[x]){
                    if(y==-1) continue;
                    if(chmin(two_dist[s][y],two_dist[s][x]+1)){
                        two_dist_pre[s][y]=x;
                        q.push(y);
                    }
                }
            }
        }
        
        SA_State sa_state;
        
        sa_state=SA<SA_State,500,10.0>(sa_state);
        
        vector<int> pos=sa_state.pos;
        
        int sz=len(pos);
        
        vector<vector<pii>> dp(sz,vector<pii>(sz+1,{INF,INF}));  //[pos_index][cnt]={damage,turn}
        vector<vector<pii>> pre(sz,vector<pii>(sz+1,{-1,-1}));
        
        dp[0][0]={0,0};
        
        bool have_key=false;
        
        constexpr int W=100;
        
        int key_idx=-1;
        
        rep(i,sz){
            if(pos[i]==Key) key_idx=i;
        }
        
        assert(key_idx!=-1);
        
        rep(i,sz-1){
            
            if(pos[i]==Key) have_key=true;
            //cerr << i << " " << sz << " " << Timer::get_ms_all_program() << endl;
            
            vector<int> gs;
            replr(j,i+1,min({sz,i+W,i<key_idx?key_idx+1:INF})){
                gs.push_back(pos[j]);
            }
            
            array<bool,L> in_turn;
            in_turn.fill(false);
            
            rep(c,sz){
                auto [damage,turn]=dp[i][c];
                if(H<damage) continue;
                in_turn[turn%L]=true;
            }
            
            array<vector<int>,L> turn_diff_damages;
            array<vector<int>,L> turn_diff_turns;
            
            rep(l,L){
                if(!in_turn[l]) continue;
                auto [diff_damages,diff_turns]=dijkstra_cost(pos[i],l,have_key,gs);
                turn_diff_damages[l]=diff_damages;
                turn_diff_turns[l]=diff_turns;
            }
            rep(c,sz){
                auto [damage,turn]=dp[i][c];
                if(H<damage) continue;
                
                rep(k,len(gs)){
                    int j=i+1+k;
                    if(chmin(dp[j][c+1],{damage+turn_diff_damages[turn%L][j-(i+1)],turn+turn_diff_turns[turn%L][j-(i+1)]})){
                        pre[j][c+1]={i,c};
                    }
                }
            }
        }
        
        int xi=sz-1,xc=-1;
        
        for(int c=sz;0<=c;c--){
            auto [damage,turn]=dp[sz-1][c];
            if(damage<=H){
                xc=c;
                break;
            }
        }
        
        cerr << (xc-1)*10 << " " << Timer::get_ms_all_program() << endl;
        
        assert(xc!=-1);
        
        vector<int> dp_route;
        
        
        while(!(xi==0&&xc==0)){
            dp_route.push_back(xi);
            auto [pi,pc]=pre[xi][xc];
            xi=pi;
            xc=pc;
        }
        
        reverse(all(dp_route));
        
        
        vector<int> ans;
        int pos_idx=0;
        have_key=false;
        
        for(auto e_idx:dp_route){
            if(pos[e_idx]==Key) have_key=true;
            vector<int> now=dijkstra_route(pos[pos_idx],len(ans),have_key,pos[e_idx]);
            pos_idx=e_idx;
            add(ans,now);
        }
        
        output_ans(ans);
    }
}

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