結果

問題 No.5006 Hidden Maze
ユーザー shamioshamio
提出日時 2022-06-12 16:51:48
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 111 ms / 2,000 ms
コード長 5,454 bytes
コンパイル時間 1,898 ms
実行使用メモリ 22,856 KB
スコア 0
平均クエリ数 1000.00
最終ジャッジ日時 2022-06-12 16:52:06
合計ジャッジ時間 16,539 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
void debug() {
std::cerr << std::endl;
std::cerr << "↑ [line:" << __LINE__ << "]" << std::endl;
}
template<class Head, class... Tail>
void debug(Head&& head, Tail&&... tail) {
std::cerr << head << ", ";
debug(std::forward<Tail>(tail)...);
}
class XorShift128 {
private:
uint32_t x, y, z, w;
public:
XorShift128() : x(123456789), y(362436069), z(521288629), w(88675123) { }
uint32_t rnd() {
uint32_t t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
uint32_t rnd(const int n) {
return rnd() % n;
}
uint32_t rnd(const int l, const int r) { // [l, r]
return rnd() % (r - l + 1) + l;
}
};
long long get_time() {
struct timeval tv;
gettimeofday(&tv, NULL);
long long result = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
return result;
}
template<class T>
ostream& operator<<(ostream& ostr, const vector<T>& vec) {
ostr << "(";
for (const T& val : vec) {
ostr << val << ", ";
}
ostr << ")";
return ostr;
}
mt19937 engine(890482);
XorShift128 xor_shift_128;
long long start;
const int N = 20;
const int MAX_TURNS = 1000;
const int MAX_MOVES = 400;
const int SH = 0, SW = 0, GH = N - 1, GW = N - 1;
const double NO_WALL_PROB_INIT = 0.9999;
const double NO_WALL = 1.0;
const int NIL = -1;
const int DH[4] = { -1, 0, 1, 0};
const int DW[4] = { 0, -1, 0, 1};
const char D_CHAR[4] = {'U', 'L', 'D', 'R'};
int H, W, P;
double prob = (double)P / 100.0;
array<array<double, N>, N-1> no_wall_prob_ver;
array<array<double, N-1>, N> no_wall_prob_hor;
void init() {
// input
cin >> H >> W >> P;
// others
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N - 1; ++j) {
no_wall_prob_hor[i][j] = NO_WALL_PROB_INIT;
no_wall_prob_ver[j][i] = NO_WALL_PROB_INIT;
}
}
}
bool in_grid(int h, int w) {
return 0 <= h && h < N && 0 <= w && w < N;
}
void print_output(const vector<int>& output) {
for (const int di: output) {
cout << D_CHAR[di];
}
cout << endl;
}
double& get_no_wall_prob(int hi, int wi, int hj, int wj) {
if (hi == hj) {
// horizontal wall
int mn = min(wi, wj);
int mx = max(wi, wj);
assert(mn + 1 == mx);
return no_wall_prob_hor[hi][mn];
} else if (wi == wj) {
// vertical wall
int mn = min(hi, hj);
int mx = max(hi, hj);
assert(mn + 1 == mx);
return no_wall_prob_ver[mn][wi];
} else {
assert(false);
}
}
void update_no_wall_prob(const vector<int>& output, const int end_turn) {
int h = SH, w = SW;
for (int ti = 0; ti < end_turn - 1; ++ti) {
int di = output[ti];
int nh = h + DH[di];
int nw = w + DW[di];
double& no_wall_prob = get_no_wall_prob(h, w, nh, nw);
no_wall_prob = NO_WALL;
h = nh;
w = nw;
}
int di = output[end_turn - 1];
int nh = h + DH[di];
int nw = w + DW[di];
double& no_wall_prob = get_no_wall_prob(h, w, nh, nw);
if (no_wall_prob < NO_WALL) {
no_wall_prob *= 1.0 - prob;
}
}
int get_opposite_dir(int di) {
return (di + 2) % 4;
}
const double INF = 1000000.0;
array<int, 4> dir = {0, 1, 2, 3};
vector<int> find_shortest_path() {
array<array<double, N>, N> dists;
array<array<int, N>, N> prev;
for (int hi = 0; hi < N; ++hi) {
for (int wi = 0; wi < N; ++wi) {
dists[hi][wi] = INF;
prev[hi][wi] = NIL;
}
}
dists[SH][SW] = 0.0;
priority_queue<tuple<double, int, int>> pq;
pq.emplace(make_tuple(-0.0, SH, SW));
while (!pq.empty()) {
tuple<double, int, int> tpl = pq.top(); pq.pop();
double d = -get<0>(tpl);
int h = get<1>(tpl);
int w = get<2>(tpl);
if (dists[h][w] != d) {
continue;
}
if (h == GH && w == GW) {
break;
}
shuffle(dir.begin(), dir.end(), engine);
for (const int di : dir) {
int nh = h + DH[di];
int nw = w + DW[di];
if (!in_grid(nh, nw)) {
continue;
}
const double no_wall_prob = get_no_wall_prob(h, w, nh, nw);
double nd = d + (1.0 - no_wall_prob);
if (nd < dists[nh][nw]) {
dists[nh][nw] = nd;
prev[nh][nw] = di;
pq.emplace(make_tuple(-nd, nh, nw));
}
}
}
// restore
vector<int> route;
int h = GH;
int w = GW;
while (!(h == SH && w == SW)) {
int di = prev[h][w];
route.emplace_back(di);
int opp_di = get_opposite_dir(di);
h += DH[opp_di];
w += DW[opp_di];
}
reverse(route.begin(), route.end());
return route;
}
void solve() {
for (int turn = 0; turn < MAX_TURNS; ++turn) {
vector<int> output = find_shortest_path();
assert(output.size() <= MAX_MOVES);
print_output(output);
int end_turn;
cin >> end_turn;
if (end_turn == -1) {
break;
}
update_no_wall_prob(output, end_turn);
}
}
int main() {
start = get_time();
init();
solve();
long long end = get_time();
cerr << "time elapsed: " << end - start << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0