結果
問題 |
No.5006 Hidden Maze
|
ユーザー |
![]() |
提出日時 | 2025-03-06 19:09:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 7,791 bytes |
コンパイル時間 | 6,927 ms |
コンパイル使用メモリ | 370,044 KB |
実行使用メモリ | 26,260 KB |
スコア | 65,799 |
平均クエリ数 | 323.73 |
最終ジャッジ日時 | 2025-03-06 19:09:40 |
合計ジャッジ時間 | 20,048 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 98 RE * 2 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace atcoder; using namespace __gnu_pbds; using mint = modint998244353; #define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl #define print(var) std::cout<<#var<<"="<<(var)<<std::endl #define all(a) (a).begin(), (a).end() #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define ll long long #define vll vector<ll> #define vvll vector<vll> #define vvvll vector<vvll> #define vvvvll vector<vvvll> #define vmi vector<mint> #define vvmi vector<vmi> #define vvvmi vector<vvmi> #define vvvvmi vector<vvvmi> #define vvvvvmi vector<vvvvmi> #define vs vector<string> #define pii pair<int,int> #define vpii vector<pii> #define vvpii vector<vpii> #define bit(x,i)(((x)>>(i))&1) #define inf (1<<30) #define INF (1ll<<60) #define X first #define Y second template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } template<class T, class F> T nibutan(T ok, T ng, const F &f){while(abs(ok-ng)>1){T mid = (ok+ng)/2;(f(mid)?ok:ng) = mid;}return ok;} template<class T> vector<T> digit(T x){vector<T> res; while(x>0){res.push_back(x%10); x/=10;} return res;} ostream& operator<<(ostream& os, const mint& x){ os << x.val(); return os; } template<class T> istream &operator>>(istream &is, vector<T> &vec){ for(auto &v:vec) is >> v; return is; } template<class T> void coutvector(vector<T> x){ for(int i=0;i<(int)x.size();i++){if(i>0) cout<<" ";cout<<x[i];}cout<<endl;} using Set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; template<class S, class T> using Unordered_Map = gp_hash_table<S,T>; #ifdef LOCAL #include<dump.hpp> CPP_DUMP_DEFINE_EXPORT_OBJECT(mint,val()); #else #define cpp_dump #endif inline double get_time() { #ifdef ONLINE_JUDGE timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec * 1e3 + tv.tv_usec * 1e-3; #else using namespace std::chrono; return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count(); #endif } double start_time = get_time(); inline double elapsed(){ return get_time() - start_time; } static uint32_t xor128(void){ static uint32_t x=123456789,y=362436069,z=521288629,w=88675123; uint32_t t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } inline int randrange(int a){return (uint64_t(xor128()) * a >> 32); } inline int randrange(int a, int b){ return randrange(b-a)+a; } inline double randDouble(double a,double b){return a+(b-a)*xor128()/(double)ULONG_MAX;} const int H = 20, W = 20; int P; enum Dir{ U,D,L,R }; vpii around{{0,1},{1,0},{-1,0},{0,-1}}; vector<Dir> route2dir(const vpii &route){ vector<Dir> res; for(int i=1;i<(int)route.size();i++){ if(route[i-1].X==route[i].X){ if(route[i-1].Y+1==route[i].Y) res.push_back(R); else if(route[i-1].Y-1==route[i].Y) res.push_back(L); else assert(false); } else if(route[i-1].Y==route[i].Y){ if(route[i-1].X+1==route[i].X) res.push_back(D); else if(route[i-1].X-1==route[i].X) res.push_back(U); else assert(false); } else assert(false); } return res; } using Cost = double; #define INF_COST std::numeric_limits<Cost>::max() using Edge = pair<int,Cost>; using Graph = vector<std::vector<Edge>>; // 頂点 start からダイクストラ法使って各頂点までの最短路長を求める std::vector<Cost> dijkstra(const Graph& graph, int start) { std::vector<Cost> dist(graph.size(), INF_COST); dist[start] = 0; std::priority_queue<pair<Cost,int>, vector<pair<Cost,int>>, greater<pair<Cost,int>>> pque; pque.emplace(0, start); while (!pque.empty()) { auto [now_cost, now] = pque.top(); pque.pop(); if (dist[now] < now_cost) continue; for (auto [to, cost] : graph[now]) { if (chmin(dist[to], now_cost + cost)) { pque.emplace(now_cost + cost, to); } } } return dist; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int hoge1,hoge2; cin>>hoge1>>hoge2; cin >> P; double init_no_wall_prob = 1 - (double)150/760; vector<vector<double>> h(H-1,vector<double>(W,init_no_wall_prob)); vector<vector<double>> v(H,vector<double>(W-1,init_no_wall_prob)); auto update_no_wall_prob = [&](double &nw){ nw = nw/(nw + (double)100/P*(1-nw)); return; }; while(true){ // h,vの-logを使ってdijkstraをする vector<vector<pair<int,double>>> graph(H*W); auto to_idx = [&](int x, int y){ return x*W+y; }; auto to_pos = [&](int idx){ return make_pair(idx/W,idx%W); }; for(int i=0;i<H-1;i++)for(int j=0;j<W;j++){ double weight; if(h[i][j]==1) weight = 0; else if(h[i][j]==0) continue; else weight = -log(h[i][j]); graph[to_idx(i,j)].push_back({to_idx(i+1,j),weight}); graph[to_idx(i+1,j)].push_back({to_idx(i,j),weight}); } for(int i=0;i<H;i++)for(int j=0;j<W-1;j++){ double weight; if(v[i][j]==1) weight = 0; else if(v[i][j]==0) continue; else weight = -log(v[i][j]); graph[to_idx(i,j)].push_back({to_idx(i,j+1),weight}); graph[to_idx(i,j+1)].push_back({to_idx(i,j),weight}); } auto dist = dijkstra(graph,0); // 復元の時に上か左方向を優先して選ぶようにする for(int i=0;i<H*W;i++) sort(all(graph[i]),[&](auto a, auto b){ return a.first < b.first; }); // 経路復元 vector<pair<int,int>> route; int now = H*W-1; vector<vector<bool>> visited(H,vector<bool>(W,false)); visited[to_pos(now).X][to_pos(now).Y] = true; while(now!=0){ route.push_back(to_pos(now)); int mn_to = -1; double mn_cost = INF_COST; for(auto [to,cost]:graph[now]){ if(visited[to_pos(to).X][to_pos(to).Y]) continue; if(chmin(mn_cost,cost+dist[to])){ mn_to = to; } } assert(mn_to!=-1); now = mn_to; visited[to_pos(now).X][to_pos(now).Y] = true; } route.push_back(to_pos(0)); reverse(all(route)); // 経路出力 auto dir = route2dir(route); string outstr; for(auto d:dir){ if(d==U) outstr.push_back('U'); else if(d==D) outstr.push_back('D'); else if(d==L) outstr.push_back('L'); else if(d==R) outstr.push_back('R'); else assert(false); } cout << outstr << endl; // 結果の受け取り int cnt; cin >> cnt; if(cnt==-1) exit(0); // 通れたところは壁じゃない for(int i=0;i<cnt;i++){ auto [x,y] = route[i]; auto [nx,ny] = route[i+1]; if(x==nx){ v[x][min(y,ny)] = 1; } else if(y==ny){ h[min(x,nx)][y] = 1; } else assert(false); } // 通れなかったところは壁の確率を更新 { auto [x,y] = route[cnt]; auto [nx,ny] = route[cnt+1]; if(x==nx){ update_no_wall_prob(v[x][min(y,ny)]); } else if(y==ny){ update_no_wall_prob(h[min(x,nx)][y]); } else assert(false); } } }