結果
| 問題 | No.5015 Escape from Labyrinth |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-05-11 08:16:37 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 2,911 ms / 3,000 ms |
| コード長 | 14,043 bytes |
| 記録 | |
| コンパイル時間 | 3,805 ms |
| コンパイル使用メモリ | 360,492 KB |
| 実行使用メモリ | 108,928 KB |
| スコア | 205,130 |
| 最終ジャッジ日時 | 2026-05-11 08:20:49 |
| 合計ジャッジ時間 | 242,936 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_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);
}
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();
while(true){
if((loop_cnt&63)==63){
ms=Timer::get_ms();
if(limit_ms<=ms) break;
//double t=(double)ms/limit_ms;
temp=start_temp-(start_temp-end_temp)/limit_ms*ms;
//temp=pow(start_temp,1-t)*pow(end_temp,t);
}
loop_cnt++;
double accept_diff=log(rand_double())*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 << " update_cnt:" << update_cnt << '\n';
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);
auto pre_pos=pos;
reverse(pos.begin()+l,pos.begin()+r+1);
int new_score=calc_score();
if(accept_diff<=score-new_score){
score=new_score;
return true;
}else{
pos=pre_pos;
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,0.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);
}