結果
問題 | No.5006 Hidden Maze |
ユーザー | hiikunZ |
提出日時 | 2022-06-12 16:13:39 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,644 ms / 2,000 ms |
コード長 | 5,637 bytes |
コンパイル時間 | 2,476 ms |
実行使用メモリ | 22,864 KB |
スコア | 0 |
平均クエリ数 | 1001.00 |
最終ジャッジ日時 | 2022-06-12 16:20:07 |
合計ジャッジ時間 | 169,089 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,587 ms
22,732 KB |
testcase_01 | AC | 1,589 ms
22,704 KB |
testcase_02 | AC | 1,589 ms
21,884 KB |
testcase_03 | AC | 1,585 ms
22,120 KB |
testcase_04 | AC | 1,599 ms
22,576 KB |
testcase_05 | AC | 1,588 ms
22,548 KB |
testcase_06 | AC | 1,590 ms
21,980 KB |
testcase_07 | AC | 1,588 ms
21,992 KB |
testcase_08 | AC | 1,564 ms
21,980 KB |
testcase_09 | AC | 1,613 ms
21,748 KB |
testcase_10 | AC | 1,591 ms
21,952 KB |
testcase_11 | AC | 1,625 ms
22,444 KB |
testcase_12 | AC | 1,617 ms
22,276 KB |
testcase_13 | AC | 1,594 ms
22,072 KB |
testcase_14 | AC | 1,579 ms
22,384 KB |
testcase_15 | AC | 1,571 ms
21,928 KB |
testcase_16 | AC | 1,602 ms
22,704 KB |
testcase_17 | AC | 1,594 ms
21,992 KB |
testcase_18 | AC | 1,593 ms
21,768 KB |
testcase_19 | AC | 1,592 ms
22,204 KB |
testcase_20 | AC | 1,595 ms
21,952 KB |
testcase_21 | AC | 1,595 ms
22,612 KB |
testcase_22 | AC | 1,592 ms
21,904 KB |
testcase_23 | AC | 1,592 ms
21,940 KB |
testcase_24 | AC | 1,595 ms
21,928 KB |
testcase_25 | AC | 1,571 ms
21,980 KB |
testcase_26 | AC | 1,607 ms
21,868 KB |
testcase_27 | AC | 1,590 ms
22,396 KB |
testcase_28 | AC | 1,592 ms
22,576 KB |
testcase_29 | AC | 1,590 ms
21,952 KB |
testcase_30 | AC | 1,607 ms
21,892 KB |
testcase_31 | AC | 1,564 ms
22,540 KB |
testcase_32 | AC | 1,587 ms
21,928 KB |
testcase_33 | AC | 1,593 ms
22,588 KB |
testcase_34 | AC | 1,590 ms
21,940 KB |
testcase_35 | AC | 1,590 ms
21,928 KB |
testcase_36 | AC | 1,562 ms
21,756 KB |
testcase_37 | AC | 1,589 ms
21,768 KB |
testcase_38 | AC | 1,589 ms
22,192 KB |
testcase_39 | AC | 1,590 ms
21,880 KB |
testcase_40 | AC | 1,588 ms
22,704 KB |
testcase_41 | AC | 1,580 ms
22,784 KB |
testcase_42 | AC | 1,576 ms
22,228 KB |
testcase_43 | AC | 1,595 ms
21,928 KB |
testcase_44 | AC | 1,590 ms
21,768 KB |
testcase_45 | AC | 1,616 ms
21,916 KB |
testcase_46 | AC | 1,594 ms
21,892 KB |
testcase_47 | AC | 1,569 ms
21,856 KB |
testcase_48 | AC | 1,592 ms
22,444 KB |
testcase_49 | AC | 1,591 ms
22,716 KB |
testcase_50 | AC | 1,619 ms
21,992 KB |
testcase_51 | AC | 1,589 ms
22,264 KB |
testcase_52 | AC | 1,579 ms
22,548 KB |
testcase_53 | AC | 1,582 ms
21,992 KB |
testcase_54 | AC | 1,596 ms
22,456 KB |
testcase_55 | AC | 1,595 ms
22,216 KB |
testcase_56 | AC | 1,595 ms
21,928 KB |
testcase_57 | AC | 1,620 ms
22,864 KB |
testcase_58 | AC | 1,565 ms
22,420 KB |
testcase_59 | AC | 1,592 ms
21,768 KB |
testcase_60 | AC | 1,593 ms
21,868 KB |
testcase_61 | AC | 1,592 ms
21,892 KB |
testcase_62 | AC | 1,612 ms
21,892 KB |
testcase_63 | AC | 1,599 ms
21,980 KB |
testcase_64 | AC | 1,581 ms
21,880 KB |
testcase_65 | AC | 1,592 ms
22,396 KB |
testcase_66 | AC | 1,611 ms
21,768 KB |
testcase_67 | AC | 1,595 ms
21,916 KB |
testcase_68 | AC | 1,590 ms
22,264 KB |
testcase_69 | AC | 1,565 ms
22,564 KB |
testcase_70 | AC | 1,577 ms
21,892 KB |
testcase_71 | AC | 1,579 ms
22,396 KB |
testcase_72 | AC | 1,598 ms
22,228 KB |
testcase_73 | AC | 1,593 ms
21,916 KB |
testcase_74 | AC | 1,592 ms
21,880 KB |
testcase_75 | AC | 1,589 ms
21,904 KB |
testcase_76 | AC | 1,572 ms
22,560 KB |
testcase_77 | AC | 1,590 ms
21,952 KB |
testcase_78 | AC | 1,588 ms
22,204 KB |
testcase_79 | AC | 1,596 ms
22,228 KB |
testcase_80 | AC | 1,564 ms
21,940 KB |
testcase_81 | AC | 1,579 ms
21,892 KB |
testcase_82 | AC | 1,577 ms
21,896 KB |
testcase_83 | AC | 1,589 ms
21,780 KB |
testcase_84 | AC | 1,595 ms
22,396 KB |
testcase_85 | AC | 1,595 ms
22,216 KB |
testcase_86 | AC | 1,593 ms
22,612 KB |
testcase_87 | AC | 1,613 ms
22,576 KB |
testcase_88 | AC | 1,598 ms
22,396 KB |
testcase_89 | AC | 1,644 ms
21,880 KB |
testcase_90 | AC | 1,627 ms
21,904 KB |
testcase_91 | AC | 1,608 ms
22,192 KB |
testcase_92 | AC | 1,619 ms
22,396 KB |
testcase_93 | AC | 1,616 ms
21,940 KB |
testcase_94 | AC | 1,619 ms
22,560 KB |
testcase_95 | AC | 1,599 ms
21,868 KB |
testcase_96 | AC | 1,603 ms
21,940 KB |
testcase_97 | AC | 1,602 ms
21,868 KB |
testcase_98 | AC | 1,598 ms
22,228 KB |
testcase_99 | AC | 1,601 ms
22,552 KB |
ソースコード
#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; { //UP state 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); } } { //DOWN state 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); } } { //LEFT state 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); } } { //RIGHT state 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; } } vector<priority_queue<state,vector<state>>> que(401); while(1){ //cout<<k<<endl; 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() > 5) que[i + 1].pop(); } } } if(1.0 * (clock() - ti) / CLOCKS_PER_SEC > 1.5 / 1000 * k) break; } for(ll i = 0;i <= 400;i++) while(!que[i].empty()) que[i].pop(); 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++; } } } }