結果

問題 No.5015 Escape from Labyrinth
ユーザー wanuiwanui
提出日時 2023-04-15 16:41:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,753 ms / 3,000 ms
コード長 16,995 bytes
コンパイル時間 2,838 ms
コンパイル使用メモリ 225,132 KB
実行使用メモリ 4,372 KB
スコア 100,810
最終ジャッジ日時 2023-04-15 16:43:29
合計ジャッジ時間 115,061 ms
ジャッジサーバーID
(参考情報)
judge14 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,076 ms
4,368 KB
testcase_01 AC 1,195 ms
4,368 KB
testcase_02 AC 1,227 ms
4,372 KB
testcase_03 AC 946 ms
4,368 KB
testcase_04 AC 998 ms
4,372 KB
testcase_05 AC 882 ms
4,368 KB
testcase_06 AC 846 ms
4,368 KB
testcase_07 AC 1,753 ms
4,372 KB
testcase_08 AC 942 ms
4,368 KB
testcase_09 AC 836 ms
4,368 KB
testcase_10 AC 669 ms
4,368 KB
testcase_11 AC 1,231 ms
4,372 KB
testcase_12 AC 1,110 ms
4,368 KB
testcase_13 AC 910 ms
4,368 KB
testcase_14 AC 1,449 ms
4,368 KB
testcase_15 AC 1,296 ms
4,372 KB
testcase_16 AC 914 ms
4,368 KB
testcase_17 AC 892 ms
4,372 KB
testcase_18 AC 1,385 ms
4,372 KB
testcase_19 AC 866 ms
4,368 KB
testcase_20 AC 1,220 ms
4,368 KB
testcase_21 AC 1,029 ms
4,368 KB
testcase_22 AC 1,068 ms
4,368 KB
testcase_23 AC 741 ms
4,368 KB
testcase_24 AC 1,290 ms
4,368 KB
testcase_25 AC 1,186 ms
4,368 KB
testcase_26 AC 861 ms
4,372 KB
testcase_27 AC 786 ms
4,372 KB
testcase_28 AC 855 ms
4,372 KB
testcase_29 AC 1,234 ms
4,372 KB
testcase_30 AC 838 ms
4,372 KB
testcase_31 AC 1,145 ms
4,368 KB
testcase_32 AC 819 ms
4,372 KB
testcase_33 AC 920 ms
4,372 KB
testcase_34 AC 879 ms
4,368 KB
testcase_35 AC 975 ms
4,368 KB
testcase_36 AC 904 ms
4,368 KB
testcase_37 AC 995 ms
4,372 KB
testcase_38 AC 1,440 ms
4,372 KB
testcase_39 AC 1,453 ms
4,372 KB
testcase_40 AC 1,174 ms
4,372 KB
testcase_41 AC 929 ms
4,368 KB
testcase_42 AC 1,036 ms
4,368 KB
testcase_43 AC 843 ms
4,372 KB
testcase_44 AC 1,471 ms
4,368 KB
testcase_45 AC 1,118 ms
4,368 KB
testcase_46 AC 1,194 ms
4,368 KB
testcase_47 AC 708 ms
4,372 KB
testcase_48 AC 903 ms
4,372 KB
testcase_49 AC 1,211 ms
4,368 KB
testcase_50 AC 1,158 ms
4,372 KB
testcase_51 AC 1,171 ms
4,368 KB
testcase_52 AC 1,130 ms
4,372 KB
testcase_53 AC 1,249 ms
4,372 KB
testcase_54 AC 1,210 ms
4,368 KB
testcase_55 AC 1,348 ms
4,368 KB
testcase_56 AC 1,071 ms
4,368 KB
testcase_57 AC 945 ms
4,372 KB
testcase_58 AC 1,038 ms
4,372 KB
testcase_59 AC 752 ms
4,372 KB
testcase_60 AC 1,086 ms
4,368 KB
testcase_61 AC 1,151 ms
4,372 KB
testcase_62 AC 1,113 ms
4,368 KB
testcase_63 AC 878 ms
4,368 KB
testcase_64 AC 1,336 ms
4,368 KB
testcase_65 AC 1,149 ms
4,372 KB
testcase_66 AC 893 ms
4,368 KB
testcase_67 AC 1,278 ms
4,372 KB
testcase_68 AC 938 ms
4,372 KB
testcase_69 AC 952 ms
4,368 KB
testcase_70 AC 1,120 ms
4,368 KB
testcase_71 AC 712 ms
4,368 KB
testcase_72 AC 931 ms
4,368 KB
testcase_73 AC 1,335 ms
4,368 KB
testcase_74 AC 1,222 ms
4,368 KB
testcase_75 AC 526 ms
4,372 KB
testcase_76 AC 1,074 ms
4,368 KB
testcase_77 AC 1,032 ms
4,372 KB
testcase_78 AC 932 ms
4,368 KB
testcase_79 AC 787 ms
4,372 KB
testcase_80 AC 1,082 ms
4,368 KB
testcase_81 AC 1,269 ms
4,372 KB
testcase_82 AC 1,236 ms
4,372 KB
testcase_83 AC 393 ms
4,372 KB
testcase_84 AC 915 ms
4,372 KB
testcase_85 AC 1,060 ms
4,368 KB
testcase_86 AC 897 ms
4,372 KB
testcase_87 AC 854 ms
4,368 KB
testcase_88 AC 1,364 ms
4,372 KB
testcase_89 AC 1,047 ms
4,372 KB
testcase_90 AC 1,135 ms
4,368 KB
testcase_91 AC 1,133 ms
4,368 KB
testcase_92 AC 985 ms
4,368 KB
testcase_93 AC 1,095 ms
4,368 KB
testcase_94 AC 1,316 ms
4,368 KB
testcase_95 AC 896 ms
4,372 KB
testcase_96 AC 1,247 ms
4,372 KB
testcase_97 AC 1,050 ms
4,372 KB
testcase_98 AC 1,085 ms
4,368 KB
testcase_99 AC 1,041 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

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 (!state.key) {
        double ratio = param_sigmoid(state.hp - costs[KEY.i][KEY.j] * (D * 4 + 1), -100, 0, 0, 1000, 2.0);
        own_jewel *= ratio;
        own_fuel *= ratio;
    }
    if (state.key) {
        if (!old_state.key) {
            score += 1e18;
        }
        double ratio = param_sigmoid(state.hp - costs[GOAL.i][GOAL.j] * (D * 2 + 1), -100, 0, 0, 1000, 2.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;
}
0