結果
| 問題 | No.5006 Hidden Maze |
| コンテスト | |
| ユーザー |
 t33f
|
| 提出日時 | 2022-06-12 16:04:17 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 87 ms / 2,000 ms |
| コード長 | 7,573 bytes |
| コンパイル時間 | 1,165 ms |
| 実行使用メモリ | 22,864 KB |
| スコア | 58,621 |
| 平均クエリ数 | 414.79 |
| 最終ジャッジ日時 | 2022-06-12 16:07:13 |
| 合計ジャッジ時間 | 10,488 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <numeric>
#include <algorithm>
#include <tuple>
#include <queue>
#include <cmath>
#include <chrono>
#include <cassert>
#include <iostream>
using namespace std;
unsigned int xor128() {
static unsigned int x=123456789, y=362436069, z=521288629, w=88675123;
unsigned int t;
t=(x^(x<<11)); x=y; y=z; z=w;
return (w=(w^(w>>19))^(t^(t>>8)));
}
inline bool rand_bool(double prob) {
constexpr double x = 1LL<<32; // uint_max+1
return xor128() < prob * x;
}
inline bool rand_bool() {
return xor128() < 1u<<31;
}
inline double rand(double lb, double ub) {
assert(lb < ub);
unsigned int x = xor128();
return lb + (ub - lb) * x / double(1LL<<32);
}
inline int rand_int(int n) { return xor128()%n; }
int timelimit = 2 * 1000, margin = 50;
class Timer {
chrono::system_clock::time_point start_time = chrono::system_clock::now();
public:
Timer() {}
int get_elapsed_time() {
auto diff = chrono::system_clock::now() - start_time;
return chrono::duration_cast<chrono::milliseconds>(diff).count();
}
} timer;
constexpr int H = 20, W = 20;
bool is_valid(int x, int y) {
return 0 <= x && x < H && 0 <= y && y < W;
}
const char dirs[] = {'D', 'R', 'U', 'L'};
const pair<int, int> dxdy[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool is_opposite(char a, char b) {
if (a == 'D') return b == 'U';
if (a == 'U') return b == 'D';
if (a == 'L') return b == 'R';
assert(a == 'R');
return b == 'L';
}
pair<int, int> make_move(int i, int j, char c) {
if (c == 'D') return {i + 1, j};
if (c == 'U') return {i - 1, j};
if (c == 'L') return {i, j - 1};
assert(c == 'R');
return {i, j + 1};
}
class ReactiveWrapper {
bool write_log = false;
public:
void enable_logging() { write_log = true; }
void disable_logging() { write_log = true; }
int write(const string &s) {
cout << s << endl;
int n; cin >> n;
if (write_log) { cerr << s << '\n' << n << endl; }
return n;
}
};
constexpr int OUTPUT_MAX = 400;
class Solver {
double wall_rate = 150.0 / 760;
double fail_prob;
double wall_prob[2][H][W];
int fail_count[2][H][W];
bool passed[2][H][W];
public:
Solver(int p) : fail_prob(p * 0.01) {
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) {
fail_count[0][i][j] = 0;
fail_count[1][i][j] = 0;
passed[0][i][j] = false;
passed[1][i][j] = false;
}
update_prob();
}
void update_prob() {
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
update_prob(i, j);
}
void update_prob(int i, int j) {
wall_prob[0][i][j] = (passed[0][i][j] ? 0.0 :
wall_rate / (wall_rate + pow(fail_prob, fail_count[0][i][j]) * (1 - wall_rate)));
wall_prob[1][i][j] = (passed[1][i][j] ? 0.0 :
wall_rate / (wall_rate + pow(fail_prob, fail_count[1][i][j]) * (1 - wall_rate)));
}
string create_path(int turn) {
int priority[H][W][4];
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++) {
iota(priority[i][j], priority[i][j] + 4, 0);
for (int k = 1; k < 4; k++) {
const int l = rand_int(k);
if (l != k) swap(priority[i][j][k], priority[i][j][l]);
}
}
double dist[H][W];
tuple<char, int, int> from[H][W];
priority_queue<tuple<double, int, int> > pq;
for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) dist[i][j] = 100;
dist[0][0] = 0;
pq.emplace(0, 0, 0);
while (!pq.empty()) {
const auto [d, x, y] = pq.top();
pq.pop();
if (dist[x][y] < d) continue;
for (int k = 0; k < 4; k++) {
const char c = dirs[k];
const auto [dx, dy] = dxdy[k];
const int x1 = x + dx, y1 = y + dy;
if (!is_valid(x1, y1)) continue;
const double wp = [this, c, x1, y1, x = x, y = y] {
switch (c) {
case 'L':
return wall_prob[0][x1][y1];
case 'R':
return wall_prob[0][x][y];
case 'D':
return wall_prob[1][x][y];
default:
assert(c == 'U');
return wall_prob[1][x1][y1];
}
}();
const double d1 = -d + wp;
if (dist[x1][y1] > d1) {
dist[x1][y1] = d1;
pq.emplace(-d1, x1, y1);
from[x1][y1] = {c, x, y};
}
}
}
string out;
for (int x = H - 1, y = W - 1; x != 0 || y != 0; ) {
// cerr << x << ' ' << y << ' ' << dist[x][y] << endl;
assert(is_valid(x, y));
const auto [c, x1, y1] = from[x][y];
out.push_back(c);
x = x1;
y = y1;
}
reverse(out.begin(), out.end());
return out;
}
void run(ReactiveWrapper wrapper) {
// wrapper.enable_logging();
for (int turn = 1; ; turn++) {
string out = create_path(turn);
const int r = wrapper.write(out);
if (r == -1) break;
int x = 0, y = 0;
for (int i = 0; i < r; i++) {
switch (out[i]) {
case 'U':
assert(x > 0);
x--;
passed[1][x][y] = true;
wall_prob[1][x][y] = 0;
break;
case 'D':
assert(x + 1 < H);
passed[1][x][y] = true;
wall_prob[1][x][y] = 0;
x++;
break;
case 'L':
assert(y > 0);
y--;
passed[0][x][y] = true;
wall_prob[0][x][y] = 0;
break;
default:
assert(out[i] == 'R');
assert(y + 1 < W);
passed[0][x][y] = true;
wall_prob[0][x][y] = 0;
y++;
}
}
if (r < out.size()) {
switch(out[r]) {
case 'U':
if (x > 0) {
fail_count[1][x - 1][y]++;
update_prob(x - 1, y);
}
break;
case 'D':
if (x + 1 < H) {
fail_count[1][x][y]++;
update_prob(x, y);
}
break;
case 'L':
if (y > 0) {
fail_count[0][x][y - 1]++;
update_prob(x, y - 1);
}
break;
default:
assert(out[r] == 'R');
if (y + 1 < W) {
fail_count[0][x][y]++;
update_prob(x, y);
}
}
}
}
}
};
int main() {
{ int h, w; cin >> h >> w; assert(h == H && w == W); }
int p;
cin >> p;
assert(6 <= p && p <= 15);
ReactiveWrapper rw;
Solver s(p);
s.run(rw);
}