#860009 (C++17) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	wanui
提出日時	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

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード