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

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	wanui
提出日時	2023-04-15 16:01:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	14,823 bytes
コンパイル時間	2,665 ms
コンパイル使用メモリ	221,536 KB
実行使用メモリ	4,504 KB
スコア	30,730
最終ジャッジ日時	2023-04-15 16:03:58
合計ジャッジ時間	138,991 ms
ジャッジサーバーID （参考情報）	judge16 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	1,141 ms 4,372 KB
testcase_04	WA	-
testcase_05	AC	1,391 ms 4,368 KB
testcase_06	AC	882 ms 4,368 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	676 ms 4,368 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	1,854 ms 4,372 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	782 ms 4,372 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	1,030 ms 4,372 KB
testcase_28	WA	-
testcase_29	AC	1,091 ms 4,368 KB
testcase_30	AC	962 ms 4,372 KB
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	AC	776 ms 4,372 KB
testcase_36	AC	946 ms 4,372 KB
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	AC	1,346 ms 4,368 KB
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	AC	1,201 ms 4,372 KB
testcase_47	AC	1,180 ms 4,372 KB
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	AC	1,247 ms 4,372 KB
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	AC	524 ms 4,372 KB
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	AC	1,159 ms 4,372 KB
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	AC	1,417 ms 4,368 KB
testcase_70	WA	-
testcase_71	AC	535 ms 4,368 KB
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	WA	-
testcase_83	WA	-
testcase_84	AC	1,309 ms 4,372 KB
testcase_85	WA	-
testcase_86	WA	-
testcase_87	AC	939 ms 4,368 KB
testcase_88	WA	-
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-
testcase_92	WA	-
testcase_93	WA	-
testcase_94	AC	1,439 ms 4,372 KB
testcase_95	AC	945 ms 4,368 KB
testcase_96	AC	1,257 ms 4,368 KB
testcase_97	AC	1,344 ms 4,372 KB
testcase_98	WA	-
testcase_99	WA	-

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

ソースコード

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_KEY_DISTANCE = 0;
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};
        }
    }

    vector<vector<int>> costs(N, vector<int>(N, inf));
    costs[key.i][key.j] = 0;
    queue<point> que;
    que.push(key);
    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);
        }
    }
    GOAL_KEY_DISTANCE = costs[goal.i][goal.j];
    GOAL = goal;
    KEY = key;
}

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 evaluate(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 own_key = (1 + GOAL_KEY_DISTANCE) * goal;
    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 (!state.key) {
        double ratio = param_sigmoid(state.hp - costs[KEY.i][KEY.j] * (D * 2 + 1), -100, 0, 0, 1000, 2.0);
        own_jewel *= ratio;
        own_fuel *= ratio;
    }
    if (state.key) {
        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;
    }
    if (state.hp < 50) {
        own_jewel = 0;
        own_fuel = 0;
    }
    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 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(nstate);
            if (best_score < score) {
                best_score = score;
                best_nstate = nstate;
                found = true;
            }
            // debug2(state.hp, state.key);
        }
        if (!found) {
            state.output();
            return;
            break;
        }

        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

結果

テストケース

ソースコード