結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
|
提出日時 | 2023-04-15 17:01:27 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,783 ms / 3,000 ms |
コード長 | 17,070 bytes |
コンパイル時間 | 3,058 ms |
コンパイル使用メモリ | 225,104 KB |
実行使用メモリ | 4,376 KB |
スコア | 110,170 |
最終ジャッジ日時 | 2023-04-15 17:03:18 |
合計ジャッジ時間 | 111,003 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <bits/stdc++.h>// clang-format offusing namespace std;#define debug1(a) { cerr<<#a<<":"<<a<<endl; }#define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }#define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }#define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }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.j<rhs.j;}return lhs.i<rhs.i;}point operator-(const point &self){return {-self.i, -self.j};}point operator+(const point &lhs, const point &rhs){return {lhs.i+rhs.i, lhs.j+rhs.j};}point operator-(const point &lhs, const point &rhs){return lhs + (-rhs);}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;};using pii = pair<int, int>;const int inf = 1e9;// clang-format onnamespace marathon {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());}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);}} // namespace marathonconst int N = 60;const int H = 1500;int D, M;char INIT_BOARD[N][N];point START;int ENEMY_INTERVAL[N][N];const int _D_ = 0;const int _R_ = 1;const int _U_ = 2;const int _L_ = 3;vector<point> mvs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};const int OP_STOP = 0;const int OP_MOVE = 1;const int OP_BLOCK = 2;const int OP_FIRE = 3;struct operation_t {int8_t kind;int8_t dir;};const char CELL_KEY = 'K';const char CELL_WALL = '#';const char CELL_EMPTY = '.';const char CELL_GOAL = 'G';const char CELL_JEWEL = 'J';const char CELL_FUEL = 'F';const char CELL_ENEMY = 'E';const char CELL_BLOCK = 'B';struct state_t {int turn;int hp;bool key;bool goal;int fuel;int jewel;int enemies;point player;char board[N][N];vector<operation_t> ops;state_t() {turn = 1;hp = H;key = false;goal = false;fuel = 0;jewel = 0;player = START;enemies = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (INIT_BOARD[i][j] == 'S') {// スタート地点は空board[i][j] = CELL_EMPTY;} else {board[i][j] = INIT_BOARD[i][j];}if (board[i][j] == CELL_ENEMY) {enemies++;}}}}void output() {for (auto op : ops) {if (op.kind == OP_STOP) {cout << "S\n";} else {char kind = '0';if (op.kind == OP_MOVE) kind = 'M';if (op.kind == OP_BLOCK) kind = 'B';if (op.kind == OP_FIRE) kind = 'F';char dir = '0';if (op.dir == _D_) dir = 'D';if (op.dir == _R_) dir = 'R';if (op.dir == _U_) dir = 'U';if (op.dir == _L_) dir = 'L';cout << kind << ' ' << dir << '\n';}}cout.flush();cerr << "score==" << jewel * 10 << " time==" << marathon::now() << " goal==" << goal << " hp==" << hp << " turn==" << turn << " D==" << D <<endl;}};bool in_board(point p) {return 0 <= p.i && p.i < N && 0 <= p.j && p.j < N;}bool in_board(int i, int j) {return 0 <= i && i < N && 0 <= j && j < N;}bool obstacle_cell(char c) {return (c == CELL_BLOCK || c == CELL_ENEMY || c == CELL_WALL);}namespace solver {/*point hit_enemies[N][N][4]; // マスごとに影響を受ける探知機を列挙しておく // 火炎魔法・ブロックのときは、向きを逆にする必要ありvoid reset_hit_enemies(state_t &state) {// ブロックを作ったとき、火炎魔法を放ったときに再度リセットする // TODO 差分計算// 鍵・宝石・火薬・扉では停止しないことに注意for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {for (int d = 0; d < 4; d++) {hit_enemies[i][j][d] = {-1, -1};}}}for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (state.board[i][j] != CELL_ENEMY) continue;for (int d = 0; d < 4; d++) {auto mv = mvs[d];point cur = {i, j};while (true) {point nxt = cur + mv;if (!in_board(nxt) || obstacle_cell(state.board[nxt.i][nxt.j])) break;hit_enemies[nxt.i][nxt.j][d] = {i, j};cur = nxt;}}}}}*/point attack_terminal(state_t &state, point src, int dir) {point cur = src;auto mv = mvs[dir];while (true) {point nxt = cur + mv;if (!in_board(nxt) || obstacle_cell(state.board[nxt.i][nxt.j])) return nxt;cur = nxt;}assert(false);return {-1, -1};}bool executable(state_t &state, operation_t op) {if (op.kind == OP_STOP) {return true;} else if (op.kind == OP_FIRE) {if (state.fuel == 0) return false;return true;} else if (op.kind == OP_BLOCK) {point nxt = state.player + mvs[op.dir];if (!in_board(nxt)) return false;char nxt_cell = state.board[nxt.i][nxt.j];return (nxt_cell == CELL_BLOCK || nxt_cell == CELL_EMPTY);} else if (op.kind == OP_MOVE) {point nxt = state.player + mvs[op.dir];if (!in_board(nxt)) return false;return !obstacle_cell(state.board[nxt.i][nxt.j]);} else {assert(false);}}void update(state_t &state, operation_t op) {state.ops.push_back(op);if (op.kind == OP_STOP) {;} else if (op.kind == OP_FIRE) {state.fuel--;point terminal = attack_terminal(state, state.player, op.dir);if (in_board(terminal) && state.board[terminal.i][terminal.j] == CELL_ENEMY) {state.board[terminal.i][terminal.j] = CELL_EMPTY;state.enemies--;}} else if (op.kind == OP_BLOCK) {point nxt = state.player + mvs[op.dir];if (state.board[nxt.i][nxt.j] == CELL_EMPTY) {state.board[nxt.i][nxt.j] = CELL_BLOCK;} else {state.board[nxt.i][nxt.j] = CELL_EMPTY;}} else if (op.kind == OP_MOVE) {point nxt = state.player + mvs[op.dir];if (state.board[nxt.i][nxt.j] == CELL_JEWEL) {state.jewel++;state.board[nxt.i][nxt.j] = CELL_EMPTY;}if (state.board[nxt.i][nxt.j] == CELL_FUEL) {state.fuel++;state.board[nxt.i][nxt.j] = CELL_EMPTY;}if (state.board[nxt.i][nxt.j] == CELL_KEY) {state.key = true;state.board[nxt.i][nxt.j] = CELL_EMPTY;}if (state.board[nxt.i][nxt.j] == CELL_GOAL && state.key) {state.goal = true;}state.player = nxt;} else {assert(false);}if (state.goal) return;state.hp--;for (int d = 0; d < 4; d++) {// TODO たぶんキャッシュできるpoint terminal = attack_terminal(state, state.player, d);if (in_board(terminal) && state.board[terminal.i][terminal.j] == CELL_ENEMY && state.turn % ENEMY_INTERVAL[terminal.i][terminal.j] == 0) {state.hp -= D;}}}int GOAL_DISTANCE[N][N];int KEY_DISTANCE[N][N];point GOAL;point KEY;void set_goal_key_distance() {point key = {-1, -1};point goal = {-1, -1};for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (INIT_BOARD[i][j] == CELL_KEY) key = {i, j};if (INIT_BOARD[i][j] == CELL_GOAL) goal = {i, j};}}KEY = key;GOAL = goal;for (int it = 0; it < 2; it++) {point init = it == 0 ? key : goal;vector<vector<int>> costs(N, vector<int>(N, inf));costs[init.i][init.j] = 0;queue<point> que;que.push(init);while (que.size()) {point cur = que.front();que.pop();for (auto mv : mvs) {point nxt = cur + mv;if (!in_board(nxt)) continue;char nxt_cell = INIT_BOARD[nxt.i][nxt.j];if (nxt_cell == CELL_WALL) continue;if (nxt_cell == CELL_ENEMY) continue;int nc = costs[cur.i][cur.j] + 1;if (costs[nxt.i][nxt.j] <= nc) continue;costs[nxt.i][nxt.j] = nc;que.push(nxt);}}if (it == 0) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {KEY_DISTANCE[i][j] = costs[i][j];}}} else {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {GOAL_DISTANCE[i][j] = costs[i][j];}}}}}double param_sigmoid(double n, double nmin, double nmax, double pleft, double pright, double arg) {double nmid = (nmax + nmin) / 2.0;double sigmoid = 1.0 / (1.0 + exp(-arg * (n - nmid) / (nmax - nmid)));return sigmoid * (pright - pleft) + pleft;}double evaluate2(state_t &old_state, state_t &state) {double neardec = 1.0 / 20;if (!old_state.key) {return 1e12 * (KEY_DISTANCE[old_state.player.i][old_state.player.j] - KEY_DISTANCE[state.player.i][state.player.j]) + marathon::uniform(0, 0.1);} else {return 1e12 * (GOAL_DISTANCE[old_state.player.i][old_state.player.j] - GOAL_DISTANCE[state.player.i][state.player.j]) + marathon::uniform(0,0.1);}}double evaluate(state_t &old_state, state_t &state) {double hp = 1000;double own_jewel = 100;double own_fuel = 10;double distance_pow = 1.0;double far_decay = 0.9;double goal = 1000;double enemies = 100;double score = 0;queue<point> que;que.push(state.player);vector<vector<int>> costs(N, vector<int>(N, inf));costs[state.player.i][state.player.j] = 0;while (que.size()) {point cur = que.front();que.pop();for (auto mv : mvs) {point nxt = cur + mv;if (!in_board(nxt)) continue;char nxt_cell = state.board[nxt.i][nxt.j];if (nxt_cell == CELL_WALL) continue;if (nxt_cell == CELL_ENEMY) continue; // TODO 巨大コストを与える?ダイクストラ?int nc = costs[cur.i][cur.j] + 1;if (nxt_cell == CELL_BLOCK) {nc += 1; // ブロックの時はコストを1増やす}if (costs[nxt.i][nxt.j] <= nc) continue;costs[nxt.i][nxt.j] = nc;que.push(nxt);}}double neardec = 1.0 / 20;if (!old_state.key && old_state.hp < 600) {score += 1e12 * (KEY_DISTANCE[old_state.player.i][old_state.player.j] - KEY_DISTANCE[state.player.i][state.player.j]);}if (old_state.key && old_state.hp < 100) {score += 1e12 * (GOAL_DISTANCE[old_state.player.i][old_state.player.j] - GOAL_DISTANCE[state.player.i][state.player.j]);}if (!old_state.key) {if (state.key) {score += 1e18;}double ratio = param_sigmoid(old_state.hp - costs[KEY.i][KEY.j] * (D * 3.0 + 1), -100, 0, 0, 1000, 2.0);hp *= ratio / 1000.0;own_jewel *= ratio;own_fuel *= ratio;}if (old_state.key) {double ratio = param_sigmoid(old_state.hp - costs[GOAL.i][GOAL.j] * (D * 1.5 + 1), -100, 0, 0, 1000, 2.0);hp *= ratio / 1000.0;own_jewel *= ratio;own_fuel *= ratio;}double own_key = (1 + KEY_DISTANCE[GOAL.i][GOAL.j]) * goal;score += state.hp * hp;score += int(state.key) * own_key;score += state.jewel * own_jewel;score += state.fuel * own_fuel;score += (-state.enemies * enemies);int nearjewel = inf;int nearfuel = inf;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {int cost = costs[i][j];if (cost == 0) continue;if (cost == inf) continue;char cell = state.board[i][j];if (cell == CELL_KEY) {score += -cost * goal;} else if (state.key && cell == CELL_GOAL) {score += -cost * goal;} else {if (cell == CELL_JEWEL) {nearjewel = min(cost, nearjewel);} else if (cell == CELL_FUEL) {nearfuel = min(cost, nearfuel);}// double value = 0;// if (cell == CELL_JEWEL) {// value = own_jewel;// minjewel = min(cost, minjewel);// } else if (cell == CELL_FUEL) {// value = own_fuel;// minfuel = min(cost, minfuel);// }// if (value > 0) {// // score += value / pow(cost, distance_pow);// }}}}score -= nearjewel * own_jewel * neardec;score -= nearfuel * own_fuel * neardec;// score *= marathon::uniform(1.0, 1.5);// debug2(score, kc);return score;}void fallback() {auto state = state_t();while (true) {double best_score = -1e18;state_t best_nstate;vector<operation_t> ops = {{OP_MOVE, _D_},{OP_MOVE, _R_},{OP_MOVE, _U_},{OP_MOVE, _L_},};for (auto op : ops) {if (!executable(state, op)) continue;auto nstate = state;update(nstate, op);if (nstate.hp <= 0) continue;if (nstate.goal) {nstate.output();return;}double score = evaluate2(state, nstate);if (best_score < score) {best_score = score;best_nstate = nstate;}}state = best_nstate;state.turn++;}}void solve() {// 行動が13種類// それぞれの結果を適当に評価関数で評価// ビームサーチするか、評価関数を乱択して貪欲(3手読みくらいの貪欲?)set_goal_key_distance();auto state = state_t();state_t bestgoal = state_t();bestgoal.jewel = -1;while (true) {double best_score = -1e18;state_t best_nstate;vector<operation_t> ops = {{OP_STOP, 0},{OP_MOVE, _D_},{OP_MOVE, _R_},{OP_MOVE, _U_},{OP_MOVE, _L_},{OP_BLOCK, _D_},{OP_BLOCK, _R_},{OP_BLOCK, _U_},{OP_BLOCK, _L_},{OP_FIRE, _D_},{OP_FIRE, _R_},{OP_FIRE, _U_},{OP_FIRE, _L_},};bool found = false;for (auto op : ops) {if (!executable(state, op)) continue;auto nstate = state;update(nstate, op);if (nstate.hp <= 0) continue;if (nstate.goal) {if (bestgoal.jewel < nstate.jewel) {bestgoal = nstate;}bestgoal.output();return;}double score = evaluate(state, nstate);if (best_score < score) {best_score = score;best_nstate = nstate;found = true;}// debug2(state.hp, state.key);}if (!found) {fallback();return;}state = best_nstate;state.turn++;}bestgoal.output();}} // namespace solverint main() {marathon::marathon_init();int n_, h_;cin >> n_ >> D >> h_;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {cin >> INIT_BOARD[i][j];if (INIT_BOARD[i][j] == 'S') {START = {i, j};}}}cin >> M;for (int k = 0; k < M; k++) {int i, j, d;cin >> i >> j >> d;ENEMY_INTERVAL[i][j] = d;}solver::solve();return 0;}