#929293 (C++17) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	wanui
提出日時	2023-11-17 22:27:04
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,258 ms / 3,000 ms
コード長	15,724 bytes
コンパイル時間	3,763 ms
コンパイル使用メモリ	253,812 KB
実行使用メモリ	19,592 KB
スコア	2,716,647,339
最終ジャッジ日時	2023-11-17 22:28:34
合計ジャッジ時間	90,253 ms
ジャッジサーバーID （参考情報）	judge14 / judge12
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,484 ms 19,584 KB
testcase_01	AC	1,993 ms 19,584 KB
testcase_02	AC	1,646 ms 19,588 KB
testcase_03	AC	1,545 ms 19,584 KB
testcase_04	AC	1,337 ms 19,584 KB
testcase_05	AC	1,334 ms 19,584 KB
testcase_06	AC	1,518 ms 19,580 KB
testcase_07	AC	1,923 ms 19,584 KB
testcase_08	AC	1,534 ms 19,580 KB
testcase_09	AC	2,258 ms 19,584 KB
testcase_10	AC	1,227 ms 19,584 KB
testcase_11	AC	1,629 ms 19,584 KB
testcase_12	AC	1,652 ms 19,584 KB
testcase_13	AC	1,711 ms 19,580 KB
testcase_14	AC	1,280 ms 19,588 KB
testcase_15	AC	1,511 ms 19,580 KB
testcase_16	AC	1,359 ms 19,580 KB
testcase_17	AC	1,038 ms 19,588 KB
testcase_18	AC	1,720 ms 19,580 KB
testcase_19	AC	1,502 ms 19,584 KB
testcase_20	AC	1,889 ms 19,584 KB
testcase_21	AC	1,776 ms 19,584 KB
testcase_22	AC	1,291 ms 19,588 KB
testcase_23	AC	1,620 ms 19,584 KB
testcase_24	AC	1,722 ms 19,588 KB
testcase_25	AC	1,681 ms 19,584 KB
testcase_26	AC	1,543 ms 19,580 KB
testcase_27	AC	1,221 ms 19,588 KB
testcase_28	AC	1,470 ms 19,584 KB
testcase_29	AC	1,125 ms 19,588 KB
testcase_30	AC	1,670 ms 19,576 KB
testcase_31	AC	1,636 ms 19,580 KB
testcase_32	AC	1,864 ms 19,580 KB
testcase_33	AC	1,368 ms 19,584 KB
testcase_34	AC	1,979 ms 19,580 KB
testcase_35	AC	1,567 ms 19,584 KB
testcase_36	AC	1,480 ms 19,580 KB
testcase_37	AC	1,600 ms 19,580 KB
testcase_38	AC	1,744 ms 19,572 KB
testcase_39	AC	1,471 ms 19,592 KB
testcase_40	AC	1,754 ms 19,580 KB
testcase_41	AC	1,652 ms 19,584 KB
testcase_42	AC	1,421 ms 19,584 KB
testcase_43	AC	1,234 ms 19,588 KB
testcase_44	AC	1,360 ms 19,584 KB
testcase_45	AC	1,091 ms 19,580 KB
testcase_46	AC	1,636 ms 19,588 KB
testcase_47	AC	1,425 ms 19,580 KB
testcase_48	AC	1,851 ms 19,584 KB
testcase_49	AC	2,132 ms 19,588 KB

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

コンパイルメッセージ

main.cpp: In function 'int getmove(point, point)':
main.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

ソースコード

raw source code

#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
#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 r; int c; };
bool operator==(const point &lhs, const point &rhs) { return (lhs.r == rhs.r && lhs.c == rhs.c); }
bool operator!=(const point &lhs, const point &rhs) { return !(lhs == rhs); }
bool operator<(const point &lhs, const point &rhs) {
    if (lhs.r != rhs.r){return lhs.r<rhs.r;}
    return lhs.c<rhs.c;
}
point operator-(const point &self){
    return {-self.r, -self.c};
}
point operator+(const point &lhs, const point &rhs){
    return {lhs.r+rhs.r, lhs.c+rhs.c};
}
point operator-(const point &lhs, const point &rhs){
    return lhs + (-rhs);
}
std::ostream &operator<<(std::ostream &os, point &pt) {
    string s;
    s = "(" + to_string(int(pt.r)) + ", " + to_string(int(pt.c)) + ")";
    return os << s;
};
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());
}
int randint(int mn, int mx) {
    int rng = mx - mn + 1;
    return mn + (engine() % rng);
}
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);
}
template <typename T>
T random_choice(vector<T> &vec) {
    return vec[engine() % vec.size()];
}
bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) {
    const int ANNEAL_RND = 1e8;
    const double ANNEAL_EPS = 1e-6;
    double temp = (begin_temp * (end_time - cur_time) + end_temp * (cur_time - begin_time)) / (end_time - begin_time);
    return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS);
}

}  // namespace marathon
struct operation_t {
    int kind;
    int xyz;
};
struct bomb_t {
    int cost;
    vector<point> ranges;
};
const int _U_ = 0;
const int _R_ = 1;
const int _D_ = 2;
const int _L_ = 3;
const int N = 50;
const int M = 20;
const int N2 = 2500;
vector<point> mvs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
using bsn2 = bitset<N2>;
vector<vector<int>> mvtbl(N2);
bsn2 break_bomb_bs[N][N][M];
char TBL_INIT[N][N];
bomb_t BOMBS[M];
int getmove(point src, point dest) {
    assert(abs(src.r - dest.r) + abs(src.c - dest.c) == 1);
    if (src.r < dest.r) {
        return _D_;
    }
    if (src.r > dest.r) {
        return _U_;
    }
    if (src.c < dest.c) {
        return _R_;
    }
    if (src.c > dest.c) {
        return _L_;
    }
}
bool ingrid(int i, int j) {
    return 0 <= i && i < N && 0 <= j && j < N;
}
bool ingrid(point p) {
    return ingrid(p.r, p.c);
}
int _p(int r, int c) {
    return r * N + c;
}
int _p(point p) {
    return _p(p.r, p.c);
}

void init_data() {
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            point u = {r, c};
            for (auto mv : mvs) {
                auto v = mv + u;
                if (!ingrid(v)) continue;
                mvtbl[_p(u)].push_back(_p(v));
            }
        }
    }
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            for (int bid = 0; bid < M; bid++) {
                break_bomb_bs[r][c][bid] = 0;
                point now = {r, c};
                for (auto drc : BOMBS[bid].ranges) {
                    point pt = now + drc;
                    if (!ingrid(pt)) continue;
                    break_bomb_bs[r][c][bid][_p(pt)] = 1;
                }
            }
        }
    }
}
vector<vector<int>> dij_cost(point ini, vector<vector<char>> &tbl) {
    priority_queue<uint, vector<uint>, greater<uint>> pq;
    vector<char> tbl_(N2);
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            tbl_[_p(r, c)] = tbl[r][c];
        }
    }
    pq.push(_p(ini));
    vector<bool> done(N2);
    vector<int> costs(N2, inf);
    while (pq.size()) {
        uint cu = pq.top();
        pq.pop();
        int cost = cu >> 16;
        int u = cu & 65535;
        if (done[u]) continue;
        done[u] = true;
        costs[u] = cost;
        for (auto v : mvtbl[u]) {
            int nc = cost + 1;
            if (tbl_[v] != '.') {
                nc = cost + 2;
            }
            if (costs[v] <= nc) continue;
            costs[v] = nc;
            pq.push(nc * 65536 + v);
        }
    }
    vector<vector<int>> result(N, vector<int>(N));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            result[r][c] = costs[_p(r, c)];
            // debug4(ini, r, c, result[r][c]);
        }
    }
    return result;
}
void dij_goto_ops(point &hulk, point dest, vector<operation_t> &ops, vector<vector<char>> &tbl) {
    priority_queue<tuple<int, point, point>, vector<tuple<int, point, point>>, greater<tuple<int, point, point>>> pq;
    pq.push({0, hulk, {-1, -1}});
    vector<vector<int>> costs(N, vector<int>(N, inf));
    vector<vector<point>> froms(N, vector<point>(N, {-1, -1}));
    while (pq.size()) {
        int cost;
        point u, frm;
        tie(cost, u, frm) = pq.top();
        pq.pop();
        if (costs[u.r][u.c] <= cost) continue;
        costs[u.r][u.c] = cost;
        froms[u.r][u.c] = frm;
        if (u == dest) break;
        for (auto mv : mvs) {
            point v = mv + u;
            if (!ingrid(v)) continue;
            int nc = cost + 1;
            if (tbl[v.r][v.c] != '.') {
                nc = cost + 2;
            }
            pq.push({nc, v, u});
        }
    }
    {
        point cur = dest;
        vector<point> route;
        while (true) {
            route.push_back(cur);
            if (cur == hulk) break;
            cur = froms[cur.r][cur.c];
        }
        reverse(route.begin(), route.end());
        for (int i = 1; i < int(route.size()); i++) {
            point pre = route[i - 1];
            point nxt = route[i];
            int mvid = getmove(pre, nxt);
            ops.push_back({1, mvid});
        }
    }
    hulk = dest;
}
pair<int, int> evaluate_ops(vector<operation_t> &ops) {
    vector<vector<char>> tbl(N, vector<char>(N));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            tbl[r][c] = TBL_INIT[r][c];
        }
    }
    int move_cost = 0;
    int bomb_cost = 0;
    point hulk = {0, 0};
    int bombs = 0;
    for (auto op : ops) {
        if (op.kind == 1) {
            hulk = hulk + mvs[op.xyz];
            if (tbl[hulk.r][hulk.c] == '.') {
                move_cost += (1 + bombs) * (1 + bombs);
            } else {
                move_cost += 2 * (1 + bombs) * (1 + bombs);
            }
        } else if (op.kind == 2) {
            bombs++;
            int bombid = op.xyz;
            bomb_cost += BOMBS[bombid].cost;
        } else {
            bombs--;  // WAにはならない前提
            int bombid = op.xyz;
            for (auto drc : BOMBS[bombid].ranges) {
                point pt = hulk + drc;
                if (!ingrid(pt)) continue;
                tbl[pt.r][pt.c] = '.';
            }
        }
    }
    return {move_cost, bomb_cost};
}
void solve() {
    point hulk = {0, 0};
    vector<vector<char>> tbl(N, vector<char>(N));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            tbl[r][c] = TBL_INIT[r][c];
        }
    }

    // 1/4区画ごとに中心となる店(ハブ店)を1店舗ずつ定めておく。 ハブ店はなるべく破壊しないようにする。
    bsn2 hub_shop_bs = 0;
    for (int hub_shop_id = 0; hub_shop_id < 4; hub_shop_id++) {
        point center = {-1, -1};
        const int HUB_SHOP_CENTER = 12;
        if (hub_shop_id == 0) center = {HUB_SHOP_CENTER, HUB_SHOP_CENTER};
        if (hub_shop_id == 1) center = {N - 1 - HUB_SHOP_CENTER, HUB_SHOP_CENTER};
        if (hub_shop_id == 2) center = {HUB_SHOP_CENTER, N - 1 - HUB_SHOP_CENTER};
        if (hub_shop_id == 3) center = {N - 1 - HUB_SHOP_CENTER, N - 1 - HUB_SHOP_CENTER};
        pair<int, point> minshop = {inf, {-1, -1}};
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (tbl[r][c] == '@') {
                    point now = {r, c};
                    int distance = abs(center.r - now.r) + abs(center.c - now.c);
                    minshop = min(minshop, {distance, now});
                }
            }
        }
        hub_shop_bs[_p(minshop.second)] = 1;
    }

    vector<operation_t> ops;

    // ある爆弾をある位置まで1個だけ運んで爆発させる操作を繰り返す貪欲。
    // 各回での操作の種類数は N*N*M (爆発させる場所 * 爆弾の種類)。 時間に余裕がないので高速化が重要。
    // 貪欲の評価関数として (移動コスト+爆弾コスト)/破壊する建物数 が一番小さい操作を選ぶ。
    for (int breakloop = 0; true; breakloop++) {
        debug2(breakloop, marathon::now());
        vector<point> shops;
        vector<point> buildings;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (tbl[r][c] == '@') shops.push_back({r, c});
                if (tbl[r][c] == '#') buildings.push_back({r, c});
            }
        }
        if (shops.size() == 0) break;

        // 最も評価関数の値が大きい操作の (爆発する場所, 爆弾を買う場所, 爆弾ID)
        tuple<point, point, int> bestop = {{-1, -1}, {-1, -1}, -1};
        {
            double bestscore = -1e18;
            auto hulk_cost = dij_cost(hulk, tbl);
            vector<vector<point>> midshop(N, vector<point>(N, {-1, -1}));
            vector<vector<int>> move_cost(N, vector<int>(N, inf));
            for (auto shop : shops) {
                auto shop_cost = dij_cost(shop, tbl);
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        int cost = shop_cost[r][c] * 4 + hulk_cost[shop.r][shop.c];
                        if (move_cost[r][c] > cost) {
                            move_cost[r][c] = cost;
                            midshop[r][c] = shop;
                        }
                    }
                }
            }

            // bitset高速化
            bsn2 building_bs = 0;
            bsn2 shop_bs = 0;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    int u = _p(r, c);
                    if (tbl[r][c] == '#') building_bs[u] = 1;
                    if (tbl[r][c] == '@') shop_bs[u] = 1;
                }
            }
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    point now = {r, c};
                    for (int bid = 0; bid < M; bid++) {
                        bsn2 break_building_bs = break_bomb_bs[r][c][bid] & building_bs;
                        int break_building = break_building_bs.count();

                        bsn2 break_shop_bs = break_bomb_bs[r][c][bid] & shop_bs;
                        int break_shop = break_shop_bs.count();

                        bsn2 break_hub_shop_bs = break_bomb_bs[r][c][bid] & hub_shop_bs;
                        int break_hub_shop = break_hub_shop_bs.count();
                        /*
                        int break_building = 0;
                        int break_shop = 0;
                        int break_hub_shop = 0;
                        for (auto drc : BOMBS[bid].ranges) {
                            point pt = now + drc;
                            if (!ingrid(pt)) continue;
                            if (tbl[pt.r][pt.c] == '#') {
                                break_building++;
                            }
                            if (tbl[pt.r][pt.c] == '@') {
                                break_shop++;
                            }
                            if(is_hub_shop(pt)) {
                                break_hub_shop++;
                            }
                        }
                        */
                        // 基本的には -(移動コスト+爆弾コスト)/破壊する建物数 で評価するが、ハブ店を破壊したら巨大なペナルティを与える。
                        // 建物がなくなった場合にはハブ店も含めて破壊すべきであり、-(移動コスト+爆弾コスト)/破壊する店数 で評価する。
                        int cost = move_cost[r][c] + BOMBS[bid].cost;
                        double score = 0;
                        if (buildings.size() == 0) {
                            if (break_shop == 0) continue;
                            score = -1.0 * cost / break_shop;
                        } else {
                            if (break_building == 0) continue;
                            score = -1.0 * (cost + 10000 * break_hub_shop) / break_building;
                        }
                        if (bestscore < score) {
                            bestscore = score;
                            bestop = {now, midshop[now.r][now.c], bid};
                        }
                    }
                }
            }
        }
        {
            point midshop, bombpt;
            int bombid;
            tie(bombpt, midshop, bombid) = bestop;
            dij_goto_ops(hulk, midshop, ops, tbl);
            ops.push_back({2, bombid});
            dij_goto_ops(hulk, bombpt, ops, tbl);
            ops.push_back({3, bombid});
            for (auto drc : BOMBS[bombid].ranges) {
                point pt = hulk + drc;
                if (!ingrid(pt)) continue;
                tbl[pt.r][pt.c] = '.';
            }
        }
    }
    {
        cout << ops.size() << endl;
        for (auto op : ops) {
            if (op.kind == 1) {
                char d = '.';
                if (op.xyz == _L_) d = 'L';
                if (op.xyz == _R_) d = 'R';
                if (op.xyz == _U_) d = 'U';
                if (op.xyz == _D_) d = 'D';
                cout << op.kind << " " << d << endl;
            } else {
                cout << op.kind << " " << op.xyz + 1 << endl;
            }
        }
    }
    {
        int move_cost, bomb_cost;
        tie(move_cost, bomb_cost) = evaluate_ops(ops);
        int totalcost = move_cost + bomb_cost;
        int score = 1e12 / (1e4 + totalcost);
        cerr << "score==" << score << " move_cost==" << move_cost << " bomb_cost==" << bomb_cost << " time==" << marathon::now() << endl;
    }
}
int main() {
    marathon::marathon_init();
    int n, m;
    cin >> n >> m;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> TBL_INIT[r][c];
        }
    }
    for (int b = 0; b < M; b++) {
        int c, l;
        cin >> c >> l;
        bomb_t bomb;
        bomb.cost = c;
        for (int i = 0; i < l; i++) {
            int dr, dc;
            cin >> dr >> dc;
            bomb.ranges.push_back({dr, dc});
        }
        BOMBS[b] = bomb;
    }
    init_data();
    solve();
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード