結果

問題 No.5006 Hidden Maze
ユーザー simansiman
提出日時 2022-06-16 17:13:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 5,132 bytes
コンパイル時間 1,152 ms
実行使用メモリ 22,876 KB
スコア 84,727
平均クエリ数 153.73
最終ジャッジ日時 2022-06-16 17:13:46
合計ジャッジ時間 10,513 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
21,940 KB
testcase_01 AC 72 ms
21,892 KB
testcase_02 AC 26 ms
22,612 KB
testcase_03 AC 28 ms
21,940 KB
testcase_04 AC 25 ms
21,992 KB
testcase_05 AC 29 ms
22,576 KB
testcase_06 AC 32 ms
22,204 KB
testcase_07 AC 26 ms
21,780 KB
testcase_08 AC 34 ms
22,588 KB
testcase_09 AC 29 ms
22,612 KB
testcase_10 AC 25 ms
22,576 KB
testcase_11 AC 30 ms
22,620 KB
testcase_12 AC 35 ms
21,980 KB
testcase_13 AC 26 ms
21,904 KB
testcase_14 AC 55 ms
21,928 KB
testcase_15 AC 24 ms
21,928 KB
testcase_16 AC 31 ms
22,216 KB
testcase_17 AC 28 ms
22,456 KB
testcase_18 AC 48 ms
22,004 KB
testcase_19 AC 38 ms
21,868 KB
testcase_20 AC 37 ms
21,916 KB
testcase_21 AC 36 ms
22,868 KB
testcase_22 AC 23 ms
22,844 KB
testcase_23 AC 32 ms
22,564 KB
testcase_24 AC 40 ms
21,980 KB
testcase_25 AC 30 ms
22,620 KB
testcase_26 AC 55 ms
22,216 KB
testcase_27 AC 62 ms
22,612 KB
testcase_28 AC 26 ms
21,928 KB
testcase_29 AC 87 ms
21,904 KB
testcase_30 AC 24 ms
21,904 KB
testcase_31 AC 30 ms
22,844 KB
testcase_32 AC 31 ms
21,892 KB
testcase_33 AC 41 ms
22,876 KB
testcase_34 AC 24 ms
21,916 KB
testcase_35 AC 22 ms
21,916 KB
testcase_36 AC 39 ms
22,444 KB
testcase_37 AC 61 ms
21,768 KB
testcase_38 AC 95 ms
21,928 KB
testcase_39 AC 26 ms
22,444 KB
testcase_40 AC 22 ms
22,588 KB
testcase_41 AC 26 ms
21,892 KB
testcase_42 AC 38 ms
21,892 KB
testcase_43 AC 30 ms
22,216 KB
testcase_44 AC 23 ms
21,928 KB
testcase_45 AC 45 ms
21,928 KB
testcase_46 AC 147 ms
22,464 KB
testcase_47 AC 27 ms
22,444 KB
testcase_48 AC 31 ms
22,444 KB
testcase_49 AC 144 ms
22,252 KB
testcase_50 AC 22 ms
21,980 KB
testcase_51 AC 62 ms
21,892 KB
testcase_52 AC 35 ms
22,120 KB
testcase_53 AC 25 ms
21,940 KB
testcase_54 AC 25 ms
21,892 KB
testcase_55 AC 31 ms
22,588 KB
testcase_56 AC 26 ms
21,952 KB
testcase_57 AC 74 ms
21,892 KB
testcase_58 AC 26 ms
21,880 KB
testcase_59 AC 36 ms
21,756 KB
testcase_60 AC 23 ms
22,564 KB
testcase_61 AC 22 ms
22,216 KB
testcase_62 AC 31 ms
22,276 KB
testcase_63 AC 32 ms
22,204 KB
testcase_64 AC 48 ms
22,276 KB
testcase_65 AC 23 ms
21,768 KB
testcase_66 AC 32 ms
22,588 KB
testcase_67 AC 30 ms
21,892 KB
testcase_68 AC 76 ms
22,004 KB
testcase_69 AC 30 ms
22,216 KB
testcase_70 AC 22 ms
21,756 KB
testcase_71 AC 28 ms
21,904 KB
testcase_72 AC 23 ms
22,576 KB
testcase_73 AC 29 ms
22,004 KB
testcase_74 AC 25 ms
21,892 KB
testcase_75 AC 31 ms
21,892 KB
testcase_76 AC 64 ms
21,952 KB
testcase_77 AC 48 ms
21,940 KB
testcase_78 AC 36 ms
21,768 KB
testcase_79 AC 138 ms
21,940 KB
testcase_80 AC 24 ms
21,756 KB
testcase_81 AC 29 ms
21,928 KB
testcase_82 AC 29 ms
22,588 KB
testcase_83 AC 29 ms
21,892 KB
testcase_84 AC 26 ms
21,904 KB
testcase_85 AC 30 ms
21,992 KB
testcase_86 AC 22 ms
21,756 KB
testcase_87 AC 65 ms
22,004 KB
testcase_88 AC 58 ms
21,904 KB
testcase_89 AC 75 ms
21,892 KB
testcase_90 AC 32 ms
21,904 KB
testcase_91 AC 25 ms
21,928 KB
testcase_92 AC 27 ms
21,892 KB
testcase_93 AC 24 ms
21,992 KB
testcase_94 AC 42 ms
22,264 KB
testcase_95 AC 24 ms
21,928 KB
testcase_96 AC 22 ms
21,892 KB
testcase_97 AC 110 ms
22,600 KB
testcase_98 AC 58 ms
21,756 KB
testcase_99 AC 26 ms
21,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;

const ll CYCLE_PER_SEC = 2400000000;
double TIME_LIMIT = 1.8;

unsigned long long int get_cycle() {
  unsigned int low, high;
  __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
  return ((unsigned long long int) low) | ((unsigned long long int) high << 32);
}

double get_time(unsigned long long int begin_cycle) {
  return (double) (get_cycle() - begin_cycle) / CYCLE_PER_SEC;
}

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 = 1001;
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;
  int last_dir;

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

  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() {
    ll start_cycle = get_cycle();

    for (int t = 0; t < MAX_TURN; ++t) {
      double cur_time = get_time(start_cycle);
      // fprintf(stderr, "t: %d, cur_time: %f\n", t, cur_time);

      if (t % 500 == 0) {
        init();
      }

      if (cur_time < TIME_LIMIT) {
        vector<int> path = find_path();
        string query = path2str(path);
        int res = send_query(query);
        if (res == -1) break;

        update_maze_data(res, path);
      } else {
        string query = "";
        for (int i = 0; i < 400; ++i) {
          query += "R";
        }
        int res = send_query(query);
      }
    }
  }

  int send_query(string query) {
    cout << query << endl;
    // fprintf(stderr, "send: %s\n", query.c_str());
    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 if (ok_cnt > 0) {
      return 0.0;
    } 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];
    int history[H][W];
    memset(history, -1, sizeof(history));
    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;
      history[node.y][node.x] = node.last_dir;

      if (node.y == H - 1 && node.x == W - 1) {
        vector<int> path;
        int cy = node.y;
        int cx = node.x;

        while (cy != 0 || cx != 0) {
          int dir = history[cy][cx];
          path.push_back(dir);
          cy += DY[dir ^ 2];
          cx += DX[dir ^ 2];
        }

        reverse(path.begin(), path.end());
        return 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);

        double value = node.value + 1000 * calc_wall_rate(z, nz) + 1.0;
        if (try_count == 0) value -= 1.0;
        if (ok_cnt == 0 && try_count > 1 && wall_rate > 0.5) {
          value += INT_MAX;
        }
        value += 0.0001 * (xor128() % 100);
        Node next(ny, nx, value, 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;
}
0