結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 wanui
|
| 提出日時 | 2022-06-14 20:12:47 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,714 bytes |
| コンパイル時間 | 2,972 ms |
| 実行使用メモリ | 41,260 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-06-14 20:12:57 |
| 合計ジャッジ時間 | 10,332 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
ソースコード
#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}
void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}
void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }
// clang-format on
const int LOCAL = 1;
using pii = pair<int, int>;
using tii = tuple<int, int, int>;
struct point {
int i;
int j;
};
bool operator==(const point &lhs, const point &rhs) { return (lhs.i == rhs.i && lhs.j == rhs.j); }
bool operator!=(const point &lhs, const point &rhs) { return !(lhs == rhs); }
bool operator<(const point &lhs, const point &rhs) {
if (lhs.i != rhs.i) {
return lhs.i < rhs.i;
}
return lhs.j < rhs.j;
}
std::ostream &operator<<(std::ostream &os, point &pt) {
string s;
s.push_back('(');
s = s + to_string(pt.i);
s = s + ", ";
s = s + to_string(pt.j);
s.push_back(')');
return os << s;
}
mt19937 engine(0);
clock_t start_time;
double now() {
return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC;
}
void marathon_init() {
start_time = clock();
random_device seed_gen;
engine.seed(seed_gen());
}
int randint(int mn, int mx) {
int rng = mx - mn + 1;
return mn + (engine() % rng);
}
double uniform(double x, double y) {
const int RND = 1e8;
double mean = (x + y) / 2.0;
double dif = y - mean;
double p = double(engine() % RND) / RND;
return mean + dif * (1.0 - 2.0 * p);
}
bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) {
const int ANNEAL_RND = 1e8;
const double ANNEAL_EPS = 1e-6;
double temp = cur_time * (end_temp - begin_temp) / (end_time - begin_time) + (end_time * begin_temp - end_temp * begin_time) / (end_time - begin_time);
return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS);
}
const int N = 20;
double P;
const int R = 0;
const int D = 1;
const int L = 2;
const int U = 3;
vector<point> mvs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int c2d(char c) {
if (c == 'R') return R;
if (c == 'D') return D;
if (c == 'L') return L;
if (c == 'U') return U;
return -1;
}
char d2c(int d) {
if (d == R) return 'R';
if (d == D) return 'D';
if (d == L) return 'L';
if (d == U) return 'U';
return '?';
}
vector<point> l_table[N][N];
int l_btable[N][N];
bool l_check_table() {
queue<point> que;
que.push({0, 0});
vector<vector<bool>> done(N, vector<bool>(N));
while (que.size()) {
point p = que.front();
que.pop();
if (done[p.i][p.j]) continue;
done[p.i][p.j] = true;
for (auto mv : l_table[p.i][p.j]) {
int ni = p.i + mv.i;
int nj = p.j + mv.j;
que.push({ni, nj});
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!done[i][j]) return false;
}
}
return true;
}
void l_maketable(int M) {
if (!LOCAL) return;
while (true) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
l_table[i][j].clear();
l_btable[i][j] = 0;
}
}
set<tii> wallset;
int nwall = 0;
while (nwall < M) {
if (randint(0, 1) == 0) {
// 右
int i = randint(0, N - 1);
int j = randint(0, N - 2);
tii w = {0, i, j};
if (wallset.count(w)) continue;
wallset.insert(w);
} else {
// 下
int i = randint(0, N - 2);
int j = randint(0, N - 1);
tii w = {1, i, j};
if (wallset.count(w)) continue;
wallset.insert(w);
}
nwall++;
}
// RDLU の順
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i + 1 < N && !wallset.count({1, i, j})) {
l_table[i][j].push_back({1, 0}); //下
l_btable[i][j] += (1 << D);
}
if (i - 1 >= 0 && !wallset.count({1, i - 1, j})) {
l_table[i][j].push_back({-1, 0}); //上
l_btable[i][j] += (1 << U);
}
if (j + 1 < N && !wallset.count({0, i, j})) {
l_table[i][j].push_back({0, 1}); //右
l_btable[i][j] += (1 << R);
}
if (j - 1 >= 0 && !wallset.count({0, i, j - 1})) {
l_table[i][j].push_back({0, -1}); //左
l_btable[i][j] += (1 << L);
}
}
}
if (!l_check_table()) continue;
perr("M=", M);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
perr0("・");
if (j + 1 < N && wallset.count({0, i, j})) {
perr0("│");
} else {
perr0(" ");
}
}
perr0("\n");
for (int j = 0; j < N; j++) {
if (i + 1 < N && wallset.count({1, i, j})) {
perr0("─");
} else {
perr0(" ");
}
perr0(" ");
}
perr0("\n");
}
break;
}
}
int request(string ops) {
cout << ops << endl;
if (!LOCAL) {
int res;
cin >> res;
return res;
}
{
bool hitwall = false;
point cur = {0, 0};
point goal = {N - 1, N - 1};
for (auto op : ops) {
int d = 0;
if (op == 'R') {
d = R;
} else if (op == 'D') {
d = D;
} else if (op == 'L') {
d = L;
} else if (op == 'U') {
d = U;
} else {
perr(ops, "!?!?");
assert(false);
}
if (!(l_btable[cur.i][cur.j] & (1 << d))) {
hitwall = true;
break;
}
auto mv = mvs[d];
cur = {cur.i + mv.i, cur.j + mv.j};
}
if (!hitwall && cur == goal) {
return -1;
}
}
{
int opnum = 0;
point cur = {0, 0};
for (auto op : ops) {
int d = c2d(op);
if (!(l_btable[cur.i][cur.j] & (1 << d))) {
return opnum;
}
if (uniform(0.0, 1.0) < P) {
return opnum;
}
auto mv = mvs[d];
cur = {cur.i + mv.i, cur.j + mv.j};
opnum++;
}
return opnum;
}
}
string rand_combination(string s0, int start_ind) {
string s = s0;
int r = 0;
int d = 0;
for (int j = 0; j < start_ind; j++) {
if (s[j] == 'R') r++;
if (s[j] == 'D') d++;
}
for (int i = start_ind; i < int(s.size()); i++) {
if (r < N - 1 && d < N - 1) {
if (randint(0, 1)) {
s[i] = 'R';
r++;
} else {
s[i] = 'D';
d++;
}
} else if (r < N - 1) {
s[i] = 'R';
r++;
} else {
s[i] = 'D';
d++;
}
}
return s;
}
int revd(int d) {
return (d + 2) % 4;
}
int edgecosts[N][N][4];
const int inf = 1000000000;
const int STOPPED = 10000;
const int LU = 1000;
const int RND = 10;
string makeop(int opid) {
vector<vector<int>> costs(N, vector<int>(N, inf));
vector<vector<int>> froms(N, vector<int>(N, -1));
using dij = tuple<int, point, int>;
priority_queue<dij, vector<dij>, greater<dij>> pq;
pq.push({0, {0, 0}, -1});
while (pq.size()) {
point p;
int frm;
int cost;
tie(cost, p, frm) = pq.top();
pq.pop();
if (costs[p.i][p.j] < cost) continue;
costs[p.i][p.j] = cost;
froms[p.i][p.j] = frm;
for (int d = 0; d < 4; d++) {
int ni = p.i + mvs[d].i;
int nj = p.j + mvs[d].j;
if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
int nc = cost + edgecosts[p.i][p.j][d];
pq.push({nc, {ni, nj}, d});
}
}
point cur = {N - 1, N - 1};
point start = {0, 0};
string result;
while (cur != start) {
int d = froms[cur.i][cur.j];
result.push_back(d2c(d));
auto mv = mvs[revd(d)];
cur = {cur.i + mv.i, cur.j + mv.j};
}
reverse(result.begin(), result.end());
return result;
}
void solve() {
int opslimit = 1001;
if (LOCAL) opslimit = 1000;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int d = 0; d < 4; d++) {
edgecosts[i][j][d] = randint(1, RND);
if (d == L || d == U) edgecosts[i][j][d] += LU;
}
}
}
vector<vector<string>> history(N, vector<string>(N, ""));
for (int opid = 1; opid <= opslimit; opid++) {
string s = makeop(opid);
int res = request(s);
if (res < 0) {
perr(opid, "success!");
perr0("score=", 1001 - opid, "\n");
return;
}
{
point cur = {0, 0};
for (int i = 0; i < res; i++) {
char c = s[i];
int d = c2d(c);
edgecosts[cur.i][cur.j][d] = 0;
cur = {cur.i + mvs[d].i, cur.j + mvs[d].j};
}
{
int i = res;
char c = s[i];
int d = c2d(c);
if (edgecosts[cur.i][cur.j][d] != 0) edgecosts[cur.i][cur.j][d] += STOPPED;
}
}
if (LOCAL) {
perr(res);
}
}
perr(opslimit, "failure!");
perr0("score=0\n");
}
int main() {
marathon_init();
ioinit();
int _h, _w;
cin >> _h >> _w >> P;
P *= 0.01;
int M = 200;
if (LOCAL) {
cin >> M;
}
perr("P=", P);
l_maketable(M);
solve();
return 0;
}