#771295 (C++17) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	siman
提出日時	2022-06-16 00:02:55
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	3,793 bytes
コンパイル時間	1,141 ms
実行使用メモリ	41,280 KB
スコア	38,548
平均クエリ数	104.95
最終ジャッジ日時	2022-06-16 00:03:08
合計ジャッジ時間	12,141 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	66 ms 22,004 KB
testcase_01	AC	30 ms 22,636 KB
testcase_02	AC	91 ms 22,264 KB
testcase_03	AC	27 ms 22,576 KB
testcase_04	AC	40 ms 22,600 KB
testcase_05	AC	123 ms 21,952 KB
testcase_06	AC	26 ms 21,940 KB
testcase_07	AC	299 ms 21,768 KB
testcase_08	AC	389 ms 22,600 KB
testcase_09	AC	30 ms 21,916 KB
testcase_10	AC	40 ms 21,940 KB
testcase_11	AC	56 ms 21,808 KB
testcase_12	AC	52 ms 22,716 KB
testcase_13	AC	51 ms 22,004 KB
testcase_14	AC	88 ms 21,892 KB
testcase_15	AC	39 ms 22,264 KB
testcase_16	AC	33 ms 21,916 KB
testcase_17	AC	30 ms 21,940 KB
testcase_18	AC	129 ms 21,904 KB
testcase_19	AC	85 ms 22,444 KB
testcase_20	AC	30 ms 21,780 KB
testcase_21	AC	41 ms 21,908 KB
testcase_22	AC	30 ms 21,892 KB
testcase_23	AC	43 ms 21,992 KB
testcase_24	AC	87 ms 21,892 KB
testcase_25	AC	69 ms 21,892 KB
testcase_26	AC	300 ms 21,928 KB
testcase_27	AC	160 ms 22,728 KB
testcase_28	AC	23 ms 22,004 KB
testcase_29	AC	82 ms 21,928 KB
testcase_30	AC	29 ms 21,940 KB
testcase_31	AC	28 ms 22,432 KB
testcase_32	AC	88 ms 21,892 KB
testcase_33	AC	43 ms 21,940 KB
testcase_34	AC	31 ms 21,904 KB
testcase_35	AC	23 ms 22,488 KB
testcase_36	AC	22 ms 22,612 KB
testcase_37	AC	372 ms 22,564 KB
testcase_38	AC	364 ms 22,004 KB
testcase_39	AC	128 ms 21,768 KB
testcase_40	AC	25 ms 22,228 KB
testcase_41	AC	32 ms 22,468 KB
testcase_42	AC	27 ms 22,576 KB
testcase_43	AC	155 ms 22,588 KB
testcase_44	AC	27 ms 21,992 KB
testcase_45	AC	43 ms 21,756 KB
testcase_46	AC	388 ms 21,780 KB
testcase_47	AC	23 ms 21,780 KB
testcase_48	AC	22 ms 21,904 KB
testcase_49	TLE	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
testcase_64	--	-
testcase_65	--	-
testcase_66	--	-
testcase_67	--	-
testcase_68	--	-
testcase_69	--	-
testcase_70	--	-
testcase_71	--	-
testcase_72	--	-
testcase_73	--	-
testcase_74	--	-
testcase_75	--	-
testcase_76	--	-
testcase_77	--	-
testcase_78	--	-
testcase_79	--	-
testcase_80	--	-
testcase_81	--	-
testcase_82	--	-
testcase_83	--	-
testcase_84	--	-
testcase_85	--	-
testcase_86	--	-
testcase_87	--	-
testcase_88	--	-
testcase_89	--	-
testcase_90	--	-
testcase_91	--	-
testcase_92	--	-
testcase_93	--	-
testcase_94	--	-
testcase_95	--	-
testcase_96	--	-
testcase_97	--	-
testcase_98	--	-
testcase_99	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>

using namespace std;
typedef long long ll;

unsigned long long xor128() {
  static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
  unsigned long long rt = (rx ^ (rx << 11));
  rx = ry;
  ry = rz;
  rz = rw;
  return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}

const int H = 20;
const int W = 20;
const int DY[4] = {-1, 0, 1, 0};
const int DX[4] = {0, 1, 0, -1};
const string DS[4] = {"U", "R", "D", "L"};
const int MAX_TURN = 1000;
int p;

int ng_counter[H * W][H * W];
int ok_counter[H * W][H * W];

bool is_inside(int y, int x) {
  return 0 <= y && y < H && 0 <= x && x < W;
}

int calc_z(int y, int x) {
  return y * W + x;
}

struct Node {
  int y;
  int x;
  double value;
  vector<int> path;

  Node(int y = -1, int x = -1, double value = 0.0) {
    this->y = y;
    this->x = x;
    this->value = value;
    this->path.clear();
  }

  bool operator>(const Node &n) const {
    return value > n.value;
  }
};

class HiddenMaze {
public:
  void init() {
    memset(ng_counter, 0, sizeof(ng_counter));
    memset(ok_counter, 0, sizeof(ok_counter));
  }

  void run() {
    for (int t = 0; t < MAX_TURN; ++t) {
      vector<int> path = find_path();
      string query = path2str(path);
      int res = send_query(query);

      if (res == -1) break;

      update_maze_data(res, path);
    }
  }

  int send_query(string query) {
    cout << query << endl;
    int res;
    cin >> res;

    return res;
  }

  string path2str(vector<int> &path) {
    string res = "";

    for (int dir : path) {
      res += DS[dir];
    }

    return res;
  }

  void update_maze_data(int res, vector<int> &path) {
    int cy = 0;
    int cx = 0;

    for (int i = 0; i <= res; ++i) {
      int dir = path[i];
      int ny = cy + DY[dir];
      int nx = cx + DX[dir];
      int z = calc_z(cy, cx);
      int nz = calc_z(ny, nx);

      if (i == res) {
        ng_counter[z][nz]++;
      } else {
        ok_counter[z][nz]++;
      }

      cy = ny;
      cx = nx;
    }
  }

  double calc_wall_rate(int z, int nz) {
    int ok_cnt = ok_counter[z][nz];
    int ng_cnt = ng_counter[z][nz];
    int try_count = (ok_cnt + ng_cnt);

    if (try_count == 0) {
      return 0.5;
    } else {
      return ng_cnt * 1.0 / try_count;
    }
  }

  vector<int> find_path() {
    priority_queue <Node, vector<Node>, greater<Node>> pque;
    pque.push(Node(0, 0, 0));
    bool visited[H][W];
    memset(visited, false, sizeof(visited));

    while (not pque.empty()) {
      Node node = pque.top();
      int z = calc_z(node.y, node.x);
      pque.pop();

      if (visited[node.y][node.x]) continue;
      visited[node.y][node.x] = true;

      if (node.y == H - 1 && node.x == W - 1) {
        return node.path;
      }

      for (int dir = 0; dir < 4; ++dir) {
        int ny = node.y + DY[dir];
        int nx = node.x + DX[dir];
        int nz = calc_z(ny, nx);
        if (not is_inside(ny, nx)) continue;
        int ok_cnt = ok_counter[z][nz];
        int ng_cnt = ng_counter[z][nz];
        int try_count = ok_cnt + ng_cnt;
        double wall_rate = calc_wall_rate(z, nz);
        if (try_count > 5 && wall_rate > 0.5) continue;

        double value = node.value + 1000 * calc_wall_rate(z, nz) + 1.0;
        value += 0.0001 * (xor128() % 100);
        Node next(ny, nx, value);
        next.path = node.path;
        next.path.push_back(dir);
        pque.push(next);
      }
    }

    return vector<int>();
  }
};

int main() {
  int _H, _W;
  cin >> _H >> _W >> p;
  fprintf(stderr, "H: %d, W: %d, p: %d\n", H, W, p);

  HiddenMaze hm;
  hm.run();

  return 0;
}

yukicoder

結果

テストケース

ソースコード