結果
問題 | No.5006 Hidden Maze |
ユーザー |
|
提出日時 | 2022-06-12 16:06:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,636 ms / 2,000 ms |
コード長 | 5,565 bytes |
コンパイル時間 | 2,186 ms |
実行使用メモリ | 22,856 KB |
スコア | 1,252 |
平均クエリ数 | 988.48 |
最終ジャッジ日時 | 2022-06-12 16:11:53 |
合計ジャッジ時間 | 165,674 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <bits/stdc++.h>using namespace std;//#include<atcoder/all>//using namespace atcoder;using ll = long long int;using ull = unsigned long long int;using ld = long double;constexpr ll MAX = 2000000000000000000;constexpr ld PI = 3.14159265358979;constexpr ll MOD = 0;//2024948111;ld dotorad(ld K){return PI * K / 180.0;}ld radtodo(ld K){return K * 180.0 / PI;}mt19937 mt;void randinit(){srand((unsigned)time(NULL));mt = mt19937(rand());}ll sute,P;ll cnt_h[21][20],cnt_w[20][21];//○方向に移動するとき当たる壁ll k = 0;struct state{bool visited[20][20];ll I,J;ld score;string move;ld kaku;void init(){for(ll i = 0;i < 20;i++) for(ll j = 0;j < 20;j++) visited[i][j] = 0;I = 0;J = 0;visited[0][0] = 1;score = 0;move = "";kaku = 1.0;}};vector<state> next(state now){vector<state> res;{//UPstate s = now;if(cnt_h[s.I][s.J] <= 3){if(cnt_h[s.I][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;for(ll f = 0;f < cnt_h[s.I][s.J];f++){s.kaku *= 1.0 * P / 100.0;}s.I--;s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;s.visited[s.I][s.J] = 1;s.move += 'U';res.emplace_back(s);}}{//DOWNstate s = now;if(cnt_h[s.I + 1][s.J] <= 3){if(cnt_h[s.I + 1][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;for(ll f = 0;f < cnt_h[s.I + 1][s.J];f++){s.kaku *= 1.0 * P / 100.0;}s.I++;s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;s.visited[s.I][s.J] = 1;s.move += 'D';res.emplace_back(s);}}{//LEFTstate s = now;if(cnt_w[s.I][s.J] <= 3){if(cnt_w[s.I][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;for(ll f = 0;f < cnt_w[s.I][s.J];f++){s.kaku *= 1.0 * P / 100.0;}s.J--;s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;s.visited[s.I][s.J] = 1;s.move += 'L';res.emplace_back(s);}}{//RIGHTstate s = now;if(cnt_w[s.I][s.J + 1] <= 3){if(cnt_w[s.I][s.J + 1] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;for(ll f = 0;f < cnt_w[s.I][s.J + 1];f++){s.kaku *= 1.0 * P / 100.0;}s.J++;s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;s.visited[s.I][s.J] = 1;s.move += 'R';res.emplace_back(s);}}return res;}bool operator< (const state &s1, const state &s2){return s1.score < s2.score;};int main(){int ti = clock();cin >> sute >> sute >> P;for(ll i = 0;i < 21;i++){for(ll j = 0;j < 20;j++){cnt_h[i][j] = (i == 0 || i == 20) * 100;cnt_w[j][i] = (i == 0 || i == 20) * 100;}}while(1){//cout<<k<<endl;vector<priority_queue<state,vector<state>>> que(401);state s;s.init();que[0].emplace(s);state a = s,b = s;k++;while(1){for(ll i = 0;i <= 400;i++){if(1.0 * (clock() - ti) / CLOCKS_PER_SEC > 1.5 / 1000 * k) break;if(!que[i].empty()){state s = que[i].top();//\/ if(i%100==0)cout << i << "," << s.score << " " << s.kaku<<" "<<s.move.size()<< endl;que[i].pop();if(s.I == 19 && s.J == 19){if(a.score < s.score){a = s;}}if(b.score < s.score){b = s;}if(i != 400){vector<state> S = next(s);for(ll j = 0;j < (ll)S.size();j++) que[i + 1].emplace(S[j]);while(que[i + 1].size() > 3) que[i + 1].pop();}}}if(1.0 * (clock() - ti) / CLOCKS_PER_SEC > 1.5 / 1000 * k) break;}if(k % 10 != 0 || a.move.size() == 0) a = b;cout << a.move << endl;ll res;cin >> res;if(res == -1) return 0;ll I = 0,J = 0;for(ll i = 0;i < res;i++){if(a.move[i] == 'U'){cnt_h[I][J] = -1;I--;}if(a.move[i] == 'D'){cnt_h[I + 1][J] = -1;I++;}if(a.move[i] == 'L'){cnt_w[I][J] = -1;J--;}if(a.move[i] == 'R'){cnt_w[I][J + 1] = -1;J++;}}if(res != (ll)a.move.size()){ll i = res;if(a.move[i] == 'U'){if(cnt_h[I][J] != -1) cnt_h[I][J]++;}if(a.move[i] == 'D'){if(cnt_h[I + 1][J] != -1) cnt_h[I + 1][J]++;I++;}if(a.move[i] == 'L'){if(cnt_w[I][J] != -1) cnt_w[I][J]++;J--;}if(a.move[i] == 'R'){if(cnt_w[I][J + 1] != -1) cnt_w[I][J + 1]++;J++;}}}}