結果

問題 No.5006 Hidden Maze
ユーザー square1001
提出日時 2022-06-12 17:39:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 103 ms / 2,000 ms
コード長 4,009 bytes
コンパイル時間 1,226 ms
実行使用メモリ 22,868 KB
スコア 87,842
平均クエリ数 122.58
最終ジャッジ日時 2022-06-12 17:39:18
合計ジャッジ時間 8,360 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

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

/*
    yukicoder score contest (2022.6.12)
    author: square1001
    
    << solution outline >>
    - repeat outputting the track with "the highest probability"
      - probability estimation = bayesian
      - assume that the probability to be walls are "independent"
    - highest probability track: search by dijkstra's algorithm
*/
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
uint64_t seed = 2ULL;
uint64_t xorshift64() {
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}
int rand_int(int l, int r) {
    return l + int(xorshift64() % (r - l));
}
double randouble() {
    return double(xorshift64()) / double(uint64_t(-1));
}
class state {
public:
    int x, y; double prob;
    state() : x(-1), y(-1), prob(0.0) {};
    state(int x_, int y_, double prob_) : x(x_), y(y_), prob(prob_) {};
    bool operator<(const state& s) const {
        return prob < s.prob;
    }
};
int solve(int H, int W, double p) {
    // ---------- INITIAL CONFIGURATION ---------- //
    const vector<int> dx = { 1, 0, -1, 0 };
    const vector<int> dy = { 0, 1, 0, -1 };
    const string ds = "DRUL";
    const int T = 1000;
    const double wallp = 150.0 / 760.0; // (= ~19.7%)
    vector<double> wallprob(T + 1);
    for (int i = 0; i <= T; i++) {
        wallprob[i] = wallp / (wallp + (1.0 - wallp) * pow(p, i));
    }
    vector<vector<int> > wallx(H - 1, vector<int>(W, 0)); // wall between (x, y) and (x+1, y)
    vector<vector<int> > wally(H, vector<int>(W - 1, 0)); // wall between (x, y) and (x, y+1)
    
    // ---------- GAME LOOP ---------- //
    int iteration = 1;
    while (true) {
        // step #1. pre-process
        vector<vector<double> > maxprob(H, vector<double>(W, 0.0));
        maxprob[0][0] = 1.0;
        priority_queue<state> que;
        que.push(state(0, 0, 1.0));
        vector<vector<bool> > vis(H, vector<bool>(W, false));
        vector<vector<pair<int, int> > > precoord(H, vector<pair<int, int> >(W, make_pair(-1, -1)));
        while (!que.empty()) {
            state u = que.top();
            que.pop();
            if (vis[u.x][u.y]) {
                continue;
            }
            vis[u.x][u.y] = true;
            for (int i = 0; i < 4; i++) {
                int nx = u.x + dx[i], wx = (dx[i] == -1 ? u.x - 1 : u.x);
                int ny = u.y + dy[i], wy = (dy[i] == -1 ? u.y - 1 : u.y);
                if (0 <= nx && nx < H && 0 <= ny && ny < W) {
                    int wallstate = (dx[i] != 0 ? wallx[wx][wy] : wally[wx][wy]);
                    double nprob = u.prob * (1.0 - (wallstate == -1 ? 0.0 : wallprob[wallstate])) * (1.0 - p * 2.7);
                    nprob *= 1.0 - randouble() * 1.0e-7;
                    if (maxprob[nx][ny] < nprob) {
                        maxprob[nx][ny] = nprob;
                        precoord[nx][ny] = make_pair(u.x, u.y);
                        que.push(state(nx, ny, maxprob[nx][ny]));
                    }
                }
            }
        }
        
        // step #2. calculate & output the track
        pair<int, int> cur = make_pair(H - 1, W - 1);
        string str;
        while (cur != make_pair(0, 0)) {
            pair<int, int> nxt = precoord[cur.first][cur.second];
            for (int i = 0; i < 4; i++) {
                if (nxt.first + dx[i] == cur.first && nxt.second + dy[i] == cur.second) {
                    str += ds[i];
                    break;
                }
            }
            cur = nxt;
        }
        reverse(str.begin(), str.end());
        cout << str << endl;
        cerr << "#" << iteration << ": prob = " << maxprob[H - 1][W - 1] << endl;
        
        // step #3. read input
        int res;
        cin >> res;
        if (res == -1) {
            return iteration;
        }
        
        // step #4. after-process
        int curx = 0, cury = 0;
        for (int i = 0; i <= res; i++) {
            int dir = ds.find(str[i]);
            int nx = curx + dx[dir], wx = (dx[dir] == -1 ? curx - 1 : curx);
            int ny = cury + dy[dir], wy = (dy[dir] == -1 ? cury - 1 : cury);
            if (dx[dir] != 0 && wallx[wx][wy] != -1) {
                wallx[wx][wy] = (i != res ? -1 : wallx[wx][wy] + 1);
            }
            if (dy[dir] != 0 && wally[wx][wy] != -1) {
                wally[wx][wy] = (i != res ? -1 : wally[wx][wy] + 1);
            }
            curx = nx;
            cury = ny;
        }
        iteration += 1;
    }
    return -1;
}
int main() {
    int H, W, PN;
    cin >> H >> W >> PN;
    int ops = solve(H, W, double(PN) / 100);
    cerr << "# of operations: " << ops << endl;
    cerr << "Score: " << (ops != -1 ? 1001 - ops : -1) << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0