結果
| 問題 | No.5015 Escape from Labyrinth |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2026-05-12 10:59:38 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,916 ms / 3,000 ms |
| コード長 | 17,994 bytes |
| 記録 | |
| コンパイル時間 | 3,834 ms |
| コンパイル使用メモリ | 368,712 KB |
| 実行使用メモリ | 93,396 KB |
| スコア | 248,040 |
| 最終ジャッジ日時 | 2026-05-12 11:01:08 |
| 合計ジャッジ時間 | 80,143 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_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;
}
}
//参考：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==5e7) break;
if((loop_cnt&1023)==1023){
ms=Timer::get_ms();
if(limit_ms<=ms) break;
temp=start_temp-(start_temp-end_temp)/limit_ms*ms;
//temp=start_temp-(start_temp-end_temp)/5e7*loop_cnt;
}
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:" << 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; //TODO:4にする？
array<int,N*N> Detector_mod;
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<double,N*N>,N*N> two_dist;
array<array<int,N*N>,N*N> two_dist_pre;
array<double,N*N> grid_expected_damage;
struct SA_State{
vector<vector<double>> edge_dist;
int sz=0;
double score=INF;
vector<int> ord;
vector<int> idx_pos;
SA_State(){
idx_pos.push_back(Start);
rep(i,N*N){
if((S[i]=='J'||i==Key)&&two_dist[Start][i]<=H) idx_pos.push_back(i);
}
idx_pos.push_back(Goal);
sz=len(idx_pos);
ord.resize(sz);
rep(i,sz) ord[i]=i;
edge_dist.resize(sz,vector<double>(sz,0));
rep(i,sz){
rep(j,sz){
if(i==j) continue;
if(idx_pos[i]==Goal){
edge_dist[i][j]=min<double>(H,two_dist[idx_pos[j]][idx_pos[i]]-grid_expected_damage[idx_pos[i]]);
}else{
edge_dist[i][j]=min<double>(H,two_dist[idx_pos[i]][idx_pos[j]]-grid_expected_damage[idx_pos[j]]);
}
}
}
score=calc_score();
}
double calc_score() const{
double ret=0;
rep(i,sz-1){
ret+=edge_dist[ord[i]][ord[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);
double new_score=score;
new_score-=edge_dist[ord[l-1]][ord[l]];
new_score+=edge_dist[ord[l-1]][ord[r]];
new_score-=edge_dist[ord[r]][ord[r+1]];
new_score+=edge_dist[ord[l]][ord[r+1]];
if(accept_diff<=score-new_score){
reverse(ord.begin()+l,ord.begin()+r+1);
score=new_score;
return true;
}else{
return false;
}
}
vector<int> get_pos(){
vector<int> ret(sz);
rep(i,sz){
ret[i]=idx_pos[ord[i]];
}
return ret;
}
};
struct DP_State{
bitset<N*N> is_block;
int damage=INF;
int block_cnt=0;
int pos=Start,turn=0;
auto operator<=>(const DP_State &other) const{
return pii{damage,-block_cnt}<=>pii{other.damage,-other.block_cnt};
};
auto operator==(const DP_State &other) const{
return is_block==other.is_block&&damage==other.damage&&pos==other.pos&&turn==other.turn;
};
DP_State(){
}
void init(){
damage=0;
}
int calc_damage() const{
int ret=1;
rep(k,4){
int p=pos;
while(true){
p=G[p][k];
if(p==-1) break;
if(is_block[p]) break;
if(Detector_mod[p]!=-1){
if(turn%Detector_mod[p]==0) ret+=D;
break;
}
}
}
return ret;
}
void advance_move(int new_pos){
turn++;
if(turn==L) turn=0;
pos=new_pos;
damage+=calc_damage();
}
void advance_none(){
turn++;
if(turn==L) turn=0;
damage+=calc_damage();
}
void advance_block(int block_pos){
turn++;
if(turn==L) turn=0;
if(is_block[block_pos]){
block_cnt--;
}else{
block_cnt++;
}
is_block[block_pos].flip();
damage+=calc_damage();
}
};
pair<int,vector<pii>> tour_to_ans(const vector<int> &tour){
int sz=len(tour);
vector<vector<DP_State>> dp(sz,vector<DP_State>(L*2));
vector<vector<pii>> pre(sz,vector<pii>(L*2,{-1,-1}));
dp[0][0].init();
array<int,N*N> last_tour;
last_tour.fill(-1);
rep(i,sz){
last_tour[tour[i]]=i;
}
rep(i,sz-1){
bool ok=false;
rep(a,L*2){
if(H<dp[i][a].damage) continue;
ok=true;
DP_State next_state_move=dp[i][a];
next_state_move.advance_move(tour[i+1]);
if(chmin_ref(dp[i+1][(a+1)%L],next_state_move)){
pre[i+1][(a+1)%L]={i,a};
}
DP_State next_state_none=dp[i][a];
next_state_none.advance_none();
if(a+1==L*2) continue;
if(chmin_ref(dp[i][a+1],next_state_none)){
pre[i][a+1]={i,a};
}
rep(k,4){
int x=G[tour[i]][k];
if(x==-1) continue;
if(i<last_tour[x]) continue;
if(S[x]!='.') continue;
DP_State next_state_block=dp[i][a];
next_state_block.advance_block(x);
if(chmin_ref(dp[i][a+1],next_state_block)){
pre[i][a+1]={i,a};
}
}
}
if(!ok) return {INF,{}};
}
DP_State min_cost_state;
int xi=-1,xj=-1;
rep(i,L){
if(chmin_ref(min_cost_state,dp[sz-1][i])){
xi=sz-1;
xj=i;
}
}
if(H<min_cost_state.damage) return {min_cost_state.damage,{}};
assert(xi!=-1);
vector<pii> ret;
while(!(xi==0&&xj==0)){
auto [pi,pj]=pre[xi][xj];
const DP_State &pre_state=dp[pi][pj];
const DP_State &next_state=dp[xi][xj];
DP_State next_state_move=pre_state;
next_state_move.advance_move(tour[xi]);
DP_State next_state_none=pre_state;
next_state_none.advance_none();
bool ok=false;
if(xi==pi){
rep(k,4){
int x=G[tour[pi]][k];
if(x==-1) continue;
if(pi<last_tour[x]) continue;
if(S[x]!='.') continue;
DP_State next_state_block=pre_state;
next_state_block.advance_block(x);
if(next_state==next_state_block){
ok=true;
ret.emplace_back(tour[pi],k);
break;
}
}
}
if(!ok){
if(xi!=pi&&next_state==next_state_move){
ret.emplace_back(tour[xi],-1);
}else if(next_state==next_state_none){
ret.emplace_back(tour[pi],-1);
}else{
assert(0);
}
}
xi=pi;
xj=pj;
}
reverse(all(ret));
return {min_cost_state.damage,ret};
}
void output_ans(const vector<pii> &ans){
int x=Start;
for(auto p:ans){
int t=-1;
rep(k,5){
if(G[x][k]==p.first) t=k;
}
assert(t!=-1);
if(t==4){
if(p.second==-1){
cout << "S\n";
}else{
assert(0<=p.second&&p.second<4);
cout << "B " << UDLR[p.second] << '\n';
}
}else{
cout << "M " << UDLR[t] << '\n';
}
x=p.first;
}
cerr << Timer::get_ms_all_program() << '\n';
}
void solve(){
rep(i,N*N) grid_damage[i].fill(1);
Detector_mod.fill(-1);
rep(m,M){
Detector_mod[P[m]]=K[m];
}
rep(m,M){
rep(k,4){
int p=P[m];
while(p!=-1){
p=G[p][k];
if(S[p]=='E') break;
if(p!=-1){
for(int t=0;t<L;t+=K[m]){
grid_damage[p][t]+=D;
}
}
}
}
}
grid_expected_damage.fill(0);
rep(i,N*N){
double sum=0;
rep(l,L){
sum+=(grid_damage[i][l]-1);
}
grid_expected_damage[i]=1+sum/L;
}
rep(s,N*N){
if(!(S[s]=='J'||s==Start||s==Key||s==Goal)) continue;
two_dist[s].fill(INF);
two_dist[s][s]=0;
two_dist_pre[s].fill(-1);
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> pq;
pq.push({0,s});
while(!pq.empty()){
auto [d,x]=pq.top();
pq.pop();
if(1e-4<abs(d-two_dist[s][x])) continue;
if(x==Goal) continue; //Goalを閉じて途中で終了しないようにごまかしている
for(auto y:G[x]){
if(y==-1) continue;
if(S[y]=='E') continue;
if(chmin(two_dist[s][y],two_dist[s][x]+grid_expected_damage[y])){
two_dist_pre[s][y]=x;
pq.push({two_dist[s][y],y});
}
}
}
}
SA_State sa_state;
sa_state=SA<SA_State,200,10.0>(sa_state);
vector<int> pos=sa_state.get_pos();
int sz=len(pos);
int P=min(320,sz);
vector<vector<double>> dp(sz,vector<double>(P,INF)); //[pos_index][cnt]={damage,turn}
vector<vector<pii>> pre(sz,vector<pii>(P,{-1,-1}));
dp[0][0]=0;
int key_idx=-1;
rep(i,sz){
if(pos[i]==Key) key_idx=i;
}
assert(key_idx!=-1);
rep(i,sz-1){
rep(c,P-1){
replr(j,i+1,min(sz,i<key_idx?key_idx+1:INF)){
if(chmin(dp[j][c+1],dp[i][c]+two_dist[pos[i]][pos[j]])){
pre[j][c+1]={i,c};
}
}
}
}
for(int c=P-1;0<=c;c--){
if(H*1.5<=dp[sz-1][c]) continue;
//assert(Timer::get_ms_all_program()<=2900);
int xi=sz-1,xc=c;
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> tour;
tour.push_back(Start);
int pos_idx=0;
for(auto e_idx:dp_route){
vector<int> now;
int x=pos[e_idx];
while(x!=pos[pos_idx]){
now.push_back(x);
x=two_dist_pre[pos[pos_idx]][x];
}
reverse(all(now));
pos_idx=e_idx;
add(tour,now);
}
auto [cost_sum,ans]=tour_to_ans(tour);
//cerr << c <<' '<< cost_sum << endl;
if(H<cost_sum) continue;
output_ans(ans);
return;
}
assert(0);
}
}
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)]=='#') 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);
}