結果

問題 No.5015 Escape from Labyrinth
ユーザー wanuiwanui
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
// clang-format off
using 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 on
namespace 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 marathon
const 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 solver
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0