/* 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 #include #include #include #include #include using namespace std; uint64_t seed = 1ULL; 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 dx = { 1, 0, -1, 0 }; const vector dy = { 0, 1, 0, -1 }; const string ds = "DRUL"; const int T = 1000; const double wallp = 150.0 / 760.0; // (= ~19.7%) vector wallprob(T + 1); for (int i = 0; i <= T; i++) { wallprob[i] = wallp / (wallp + (1.0 - wallp) * pow(p, i)); } vector > wallx(H - 1, vector(W, 0)); // wall between (x, y) and (x+1, y) vector > wally(H, vector(W - 1, 0)); // wall between (x, y) and (x, y+1) // ---------- GAME LOOP ---------- // int iteration = 1; while (true) { // step #1. pre-process vector > maxprob(H, vector(W, 0.0)); maxprob[0][0] = 1.0; priority_queue que; que.push(state(0, 0, 1.0)); vector > vis(H, vector(W, false)); vector > > precoord(H, vector >(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 cur = make_pair(H - 1, W - 1); string str; while (cur != make_pair(0, 0)) { pair 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; }