結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 wanui
|
| 提出日時 | 2022-06-14 20:19:28 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 303 ms / 2,000 ms |
| コード長 | 10,714 bytes |
| コンパイル時間 | 2,806 ms |
| 実行使用メモリ | 22,880 KB |
| スコア | 72,747 |
| 平均クエリ数 | 273.53 |
| 最終ジャッジ日時 | 2022-06-14 20:19:46 |
| 合計ジャッジ時間 | 17,152 ms |
|
ジャッジサーバーID （参考情報） |
judge16 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>// clang-format offusing namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }// clang-format onconst int LOCAL = 0;using pii = pair<int, int>;using tii = tuple<int, int, int>;struct point {int i;int j;};bool operator==(const point &lhs, const point &rhs) { return (lhs.i == rhs.i && lhs.j == rhs.j); }bool operator!=(const point &lhs, const point &rhs) { return !(lhs == rhs); }bool operator<(const point &lhs, const point &rhs) {if (lhs.i != rhs.i) {return lhs.i < rhs.i;}return lhs.j < rhs.j;}std::ostream &operator<<(std::ostream &os, point &pt) {string s;s.push_back('(');s = s + to_string(pt.i);s = s + ", ";s = s + to_string(pt.j);s.push_back(')');return os << s;}mt19937 engine(0);clock_t start_time;double now() {return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC;}void marathon_init() {start_time = clock();random_device seed_gen;engine.seed(seed_gen());}int randint(int mn, int mx) {int rng = mx - mn + 1;return mn + (engine() % rng);}double uniform(double x, double y) {const int RND = 1e8;double mean = (x + y) / 2.0;double dif = y - mean;double p = double(engine() % RND) / RND;return mean + dif * (1.0 - 2.0 * p);}bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) {const int ANNEAL_RND = 1e8;const double ANNEAL_EPS = 1e-6;double temp = cur_time * (end_temp - begin_temp) / (end_time - begin_time) + (end_time * begin_temp - end_temp * begin_time) / (end_time -begin_time);return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS);}const int N = 20;double P;const int R = 0;const int D = 1;const int L = 2;const int U = 3;vector<point> mvs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int c2d(char c) {if (c == 'R') return R;if (c == 'D') return D;if (c == 'L') return L;if (c == 'U') return U;return -1;}char d2c(int d) {if (d == R) return 'R';if (d == D) return 'D';if (d == L) return 'L';if (d == U) return 'U';return '?';}vector<point> l_table[N][N];int l_btable[N][N];bool l_check_table() {queue<point> que;que.push({0, 0});vector<vector<bool>> done(N, vector<bool>(N));while (que.size()) {point p = que.front();que.pop();if (done[p.i][p.j]) continue;done[p.i][p.j] = true;for (auto mv : l_table[p.i][p.j]) {int ni = p.i + mv.i;int nj = p.j + mv.j;que.push({ni, nj});}}for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (!done[i][j]) return false;}}return true;}void l_maketable(int M) {if (!LOCAL) return;while (true) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {l_table[i][j].clear();l_btable[i][j] = 0;}}set<tii> wallset;int nwall = 0;while (nwall < M) {if (randint(0, 1) == 0) {// 右int i = randint(0, N - 1);int j = randint(0, N - 2);tii w = {0, i, j};if (wallset.count(w)) continue;wallset.insert(w);} else {// 下int i = randint(0, N - 2);int j = randint(0, N - 1);tii w = {1, i, j};if (wallset.count(w)) continue;wallset.insert(w);}nwall++;}// RDLU の順for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (i + 1 < N && !wallset.count({1, i, j})) {l_table[i][j].push_back({1, 0}); //下l_btable[i][j] += (1 << D);}if (i - 1 >= 0 && !wallset.count({1, i - 1, j})) {l_table[i][j].push_back({-1, 0}); //上l_btable[i][j] += (1 << U);}if (j + 1 < N && !wallset.count({0, i, j})) {l_table[i][j].push_back({0, 1}); //右l_btable[i][j] += (1 << R);}if (j - 1 >= 0 && !wallset.count({0, i, j - 1})) {l_table[i][j].push_back({0, -1}); //左l_btable[i][j] += (1 << L);}}}if (!l_check_table()) continue;perr("M=", M);for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {perr0("・");if (j + 1 < N && wallset.count({0, i, j})) {perr0("│");} else {perr0(" ");}}perr0("\n");for (int j = 0; j < N; j++) {if (i + 1 < N && wallset.count({1, i, j})) {perr0("─");} else {perr0(" ");}perr0(" ");}perr0("\n");}break;}}int request(string ops) {cout << ops << endl;if (!LOCAL) {int res;cin >> res;return res;}{bool hitwall = false;point cur = {0, 0};point goal = {N - 1, N - 1};for (auto op : ops) {int d = 0;if (op == 'R') {d = R;} else if (op == 'D') {d = D;} else if (op == 'L') {d = L;} else if (op == 'U') {d = U;} else {perr(ops, "!?!?");assert(false);}if (!(l_btable[cur.i][cur.j] & (1 << d))) {hitwall = true;break;}auto mv = mvs[d];cur = {cur.i + mv.i, cur.j + mv.j};}if (!hitwall && cur == goal) {return -1;}}{int opnum = 0;point cur = {0, 0};for (auto op : ops) {int d = c2d(op);if (!(l_btable[cur.i][cur.j] & (1 << d))) {return opnum;}if (uniform(0.0, 1.0) < P) {return opnum;}auto mv = mvs[d];cur = {cur.i + mv.i, cur.j + mv.j};opnum++;}return opnum;}}string rand_combination(string s0, int start_ind) {string s = s0;int r = 0;int d = 0;for (int j = 0; j < start_ind; j++) {if (s[j] == 'R') r++;if (s[j] == 'D') d++;}for (int i = start_ind; i < int(s.size()); i++) {if (r < N - 1 && d < N - 1) {if (randint(0, 1)) {s[i] = 'R';r++;} else {s[i] = 'D';d++;}} else if (r < N - 1) {s[i] = 'R';r++;} else {s[i] = 'D';d++;}}return s;}int revd(int d) {return (d + 2) % 4;}int edgecosts[N][N][4];const int inf = 1000000000;const int STOPPED = 10000;const int LU = 1000;const int RND = 10;string makeop(int opid) {vector<vector<int>> costs(N, vector<int>(N, inf));vector<vector<int>> froms(N, vector<int>(N, -1));using dij = tuple<int, point, int>;priority_queue<dij, vector<dij>, greater<dij>> pq;pq.push({0, {0, 0}, -1});while (pq.size()) {point p;int frm;int cost;tie(cost, p, frm) = pq.top();pq.pop();if (costs[p.i][p.j] < cost) continue;costs[p.i][p.j] = cost;froms[p.i][p.j] = frm;for (int d = 0; d < 4; d++) {int ni = p.i + mvs[d].i;int nj = p.j + mvs[d].j;if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;int nc = cost + edgecosts[p.i][p.j][d];pq.push({nc, {ni, nj}, d});}}point cur = {N - 1, N - 1};point start = {0, 0};string result;while (cur != start) {int d = froms[cur.i][cur.j];result.push_back(d2c(d));auto mv = mvs[revd(d)];cur = {cur.i + mv.i, cur.j + mv.j};}reverse(result.begin(), result.end());return result;}void solve() {int opslimit = 1001;if (LOCAL) opslimit = 1000;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {for (int d = 0; d < 4; d++) {edgecosts[i][j][d] = randint(1, RND);if (d == L || d == U) edgecosts[i][j][d] += LU;}}}vector<vector<string>> history(N, vector<string>(N, ""));for (int opid = 1; opid <= opslimit; opid++) {string s = makeop(opid);int res = request(s);if (res < 0) {perr(opid, "success!");perr0("score=", 1001 - opid, "\n");return;}{point cur = {0, 0};for (int i = 0; i < res; i++) {char c = s[i];int d = c2d(c);edgecosts[cur.i][cur.j][d] = 0;cur = {cur.i + mvs[d].i, cur.j + mvs[d].j};}{int i = res;char c = s[i];int d = c2d(c);if (edgecosts[cur.i][cur.j][d] != 0) edgecosts[cur.i][cur.j][d] += STOPPED;}}if (LOCAL) {perr(res);}}perr(opslimit, "failure!");perr0("score=0\n");}int main() {marathon_init();ioinit();int _h, _w;cin >> _h >> _w >> P;P *= 0.01;int M = 200;if (LOCAL) {cin >> M;}perr("P=", P);l_maketable(M);solve();return 0;}