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

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	wanui
提出日時	2023-11-17 16:55:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,780 ms / 3,000 ms
コード長	17,182 bytes
コンパイル時間	3,777 ms
コンパイル使用メモリ	255,104 KB
実行使用メモリ	6,548 KB
スコア	835,870,871
最終ジャッジ日時	2023-11-17 16:56:54
合計ジャッジ時間	9,402 ms
ジャッジサーバーID （参考情報）	judge15 / judge13
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,018 ms 6,548 KB
testcase_01	AC	1,318 ms 6,548 KB
testcase_02	AC	1,003 ms 6,548 KB
testcase_03	AC	1,192 ms 6,548 KB
testcase_04	AC	1,305 ms 6,548 KB
testcase_05	AC	1,626 ms 6,548 KB
testcase_06	AC	1,118 ms 6,548 KB
testcase_07	AC	1,138 ms 6,548 KB
testcase_08	AC	1,119 ms 6,548 KB
testcase_09	AC	1,259 ms 6,548 KB
testcase_10	AC	1,304 ms 6,548 KB
testcase_11	AC	1,126 ms 6,548 KB
testcase_12	AC	966 ms 6,548 KB
testcase_13	AC	2,572 ms 6,548 KB
testcase_14	AC	1,223 ms 6,548 KB
testcase_15	AC	2,780 ms 6,548 KB
testcase_16	AC	1,381 ms 6,548 KB
testcase_17	AC	1,193 ms 6,548 KB
testcase_18	AC	1,032 ms 6,548 KB
testcase_19	AC	1,172 ms 6,548 KB
testcase_20	AC	1,057 ms 6,548 KB
testcase_21	AC	1,197 ms 6,548 KB
testcase_22	AC	1,124 ms 6,548 KB
testcase_23	AC	1,023 ms 6,548 KB
testcase_24	AC	1,146 ms 6,548 KB
testcase_25	AC	1,290 ms 6,548 KB
testcase_26	AC	1,337 ms 6,548 KB
testcase_27	AC	1,173 ms 6,548 KB
testcase_28	AC	2,725 ms 6,548 KB
testcase_29	AC	2,071 ms 6,548 KB
testcase_30	AC	1,164 ms 6,548 KB
testcase_31	AC	1,205 ms 6,548 KB
testcase_32	AC	962 ms 6,548 KB
testcase_33	AC	1,066 ms 6,548 KB
testcase_34	AC	1,089 ms 6,548 KB
testcase_35	AC	1,239 ms 6,548 KB
testcase_36	AC	1,225 ms 6,548 KB
testcase_37	AC	1,242 ms 6,548 KB
testcase_38	AC	1,228 ms 6,548 KB
testcase_39	AC	1,516 ms 6,548 KB
testcase_40	AC	1,019 ms 6,548 KB
testcase_41	AC	1,214 ms 6,548 KB
testcase_42	AC	1,328 ms 6,548 KB
testcase_43	AC	1,233 ms 6,548 KB
testcase_44	AC	2,463 ms 6,548 KB
testcase_45	AC	956 ms 6,548 KB
testcase_46	AC	1,063 ms 6,548 KB
testcase_47	AC	1,284 ms 6,548 KB
testcase_48	AC	2,035 ms 6,548 KB
testcase_49	AC	1,271 ms 6,548 KB

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

コンパイルメッセージ

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

ソースコード

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;
vector<point> mvs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
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);
}

struct anneal_state_t {
    vector<pair<int, point>> bombs;

    double calc_score(vector<vector<double>> &break_score, vector<point> &breaks, point now_shop) {
        static int hit[N][N];
        for (auto br : breaks) {
            hit[br.r][br.c] = 0;
        }

        // TODO 差分計算
        // TODO かなり嘘な計算ではある
        const double bomb_num_ratio = 1.1;
        double score = 0;
        score -= bomb_num_ratio * bombs.size();
        for (auto b : bombs) {
            int bombid = b.first;
            point center = b.second;
            for (auto nxt : BOMBS[bombid].ranges) {
                point pt = center + nxt;
                if (!ingrid(pt)) continue;
                hit[pt.r][pt.c]++;
                if (hit[pt.r][pt.c] == 1) {
                    score += 1.0 * break_score[pt.r][pt.c];
                }
            }
        }
        if (hit[now_shop.r][now_shop.c] >= 2) {
            score -= 10000;
        }
        return score;
    }
};
vector<pair<int, point>> anneal_bomb_puts(vector<vector<char>> &tbl, vector<vector<double>> &break_score, point now_shop) {
    vector<point> breaks;
    int init_shopcnt = 0;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            point pt = {r, c};
            if (tbl[r][c] != '.') {
                breaks.push_back({r, c});
            }
            if (TBL_INIT[r][c] == '@') init_shopcnt++;
        }
    }

    const double END_TIME = 2900;
    double begin_time = marathon::now();
    double end_time = begin_time + 0.95 * END_TIME / init_shopcnt;
    anneal_state_t state;
    state.bombs.clear();
    double old_score = state.calc_score(break_score, breaks, now_shop);
    while (marathon::now() < end_time) {
        // 10*10マスの中に爆弾を置く
        // TODO 爆弾をなくす遷移(破壊再構築寄り)
        int r = now_shop.r + marathon::randint(-3, 3);
        int c = now_shop.c + marathon::randint(-3, 3);
        if (!ingrid(r, c)) continue;
        int b = marathon::engine() % M;
        state.bombs.push_back({b, {r, c}});
        double new_score = state.calc_score(break_score, breaks, now_shop);
        if (new_score > old_score) {
            old_score = new_score;
        } else {
            state.bombs.pop_back();
        }
    }
    return state.bombs;
}
void solve1(point &now, vector<vector<char>> &tbl, vector<operation_t> &ops) {
    assert(tbl[now.r][now.c] == '@');

    // 必ず破壊すべきtargetと、できれば破壊したいtarget
    const int DISTANCE_LIM = 10;  // TODO

    vector<vector<double>> break_score(N, vector<double>(N));
    {
        vector<point> walls;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                point pt = {r, c};
                if (tbl[r][c] == '#') {
                    walls.push_back({r, c});
                }
            }
        }
        vector<point> shops;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (tbl[r][c] == '@') {
                    point shop = {r, c};
                    shops.push_back(shop);
                    if (shop != now) {
                        if (walls.size() == 0) {
                            int distance = max(abs(shop.r - now.r), abs(shop.c - now.c));  // TODO
                            if (distance <= DISTANCE_LIM) {
                                break_score[shop.r][shop.c] += 2;  // なるべく壊しておきたい
                            } else {
                                break_score[shop.r][shop.c] += 0.01;  // 壊せるとちょっとうれしい
                            }

                        } else {
                            break_score[r][c] += -10000;
                        }
                    }
                }
            }
        }

        break_score[now.r][now.c] += 2;
        for (auto wall : walls) {
            {
                int distance = max(abs(wall.r - now.r), abs(wall.c - now.c));  // TODO
                if (distance <= DISTANCE_LIM) {
                    break_score[wall.r][wall.c] += 2;  // なるべく壊しておきたい
                } else {
                    break_score[wall.r][wall.c] += 0.01;  // 壊せるとちょっとうれしい
                }
            }
            int nearest_distance = inf;
            point nearest_shop = {-1, -1};
            for (auto shop : shops) {
                const int DISTANCE_LIM = 10;                                     // TODO
                int distance = max(abs(wall.r - shop.r), abs(wall.c - shop.c));  // TODO
                if (nearest_distance > distance) {
                    nearest_distance = distance;
                    nearest_shop = shop;
                }
            }
            if (nearest_shop == now) {
                break_score[wall.r][wall.c] += 100;  // ほぼ確実に壊しておきたい
            }
        }
    }
    auto bomb_puts = anneal_bomb_puts(tbl, break_score, now);
    // とりあえず貪欲(TODO 焼きなます)
    {
        for (auto b : bomb_puts) {
            int bombid = b.first;
            ops.push_back({2, bombid});
        }
        pair<int, point> last_bomb_put = {-1, {-1, -1}};  // shopを壊すのは最後にする
        for (auto b : bomb_puts) {
            int bombid = b.first;
            point center = b.second;
            for (auto nxt : BOMBS[bombid].ranges) {
                point pt = center + nxt;
                if (pt == now) {
                    last_bomb_put = b;
                }
            }
        }

        debug1(marathon::now());
        while (bomb_puts.size()) {
            priority_queue<tuple<int, point, point>, vector<tuple<int, point, point>>, greater<tuple<int, point, point>>> pq;
            pq.push({0, now, {-1, -1}});
            vector<vector<int>> costs(N, vector<int>(N, inf));
            vector<vector<point>> froms(N, vector<point>(N, {-1, -1}));
            vector<vector<bool>> destination(N, vector<bool>(N));
            for (auto b : bomb_puts) {
                point p = b.second;
                if (b == last_bomb_put && bomb_puts.size() >= 2) continue;
                destination[p.r][p.c] = true;
            }

            pair<int, point> tgt_bomb_put = {-1, {-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 (destination[u.r][u.c]) {
                    for (auto b : bomb_puts) {
                        if (b == last_bomb_put && bomb_puts.size() >= 2) continue;
                        if (b.second != u) continue;
                        tgt_bomb_put = b;
                        break;
                    }
                    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});
                }
            }
            assert(tgt_bomb_put.first >= 0);
            {
                point cur = tgt_bomb_put.second;
                vector<point> route;
                while (true) {
                    route.push_back(cur);
                    if (cur == now) 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});
                }
                now = tgt_bomb_put.second;
            }
            {
                ops.push_back({3, tgt_bomb_put.first});
                int bombid = tgt_bomb_put.first;
                for (auto nxt : BOMBS[bombid].ranges) {
                    point pt = now + nxt;
                    if (!ingrid(pt)) continue;
                    tbl[pt.r][pt.c] = '.';
                }
            }
            bomb_puts.erase(std::find(bomb_puts.begin(), bomb_puts.end(), tgt_bomb_put));
        }
        debug1(marathon::now());
    }
}

void solve() {
    vector<operation_t> ops;
    // point last_bomb_shop = {-1, -1};  // 念のため最後の爆弾屋は中心近くにする
    {
        int min_centerness = inf;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (TBL_INIT[r][c] == '@') {
                    int centerness = abs(r - N / 2) + abs(c - N / 2);
                    if (min_centerness > centerness) {
                        // last_bomb_shop = {r, c};
                        min_centerness = centerness;
                    }
                }
            }
        }
    }

    //
    point now = {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];
        }
    }
    while (true) {
        // 一番近くにあるshopに移動 //TODO TSP
        vector<point> shops;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (tbl[r][c] == '@') shops.push_back({r, c});
            }
        }
        debug2(marathon::now(), shops.size());
        if (shops.size() == 0) break;
        point mvto_shop = {-1, -1};
        {
            int maxscore = -1;
            for (auto shop : shops) {
                // if (shop == last_bomb_shop && shops.size() >= 2) continue;
                int score = 0;
                for (int r = shop.r - 10; r <= shop.r + 10; r++) {
                    for (int c = shop.c - 10; c <= shop.c + 10; c++) {
                        if (!ingrid(r, c)) continue;
                        if (tbl[r][c] == '#') score++;
                    }
                }
                if (maxscore < score) {
                    maxscore = score;
                    mvto_shop = shop;
                }
            }
            // queue<point> que;
            // vector<vector<bool>> done(N, vector<bool>(N));
            // que.push(now);
            // done[now.r][now.c] = true;
            // while (que.size()) {
            //     point u = que.front();
            //     que.pop();
            //     if (tbl[u.r][u.c] == '@') {
            //         if (u == last_bomb_shop && totalshop >= 2) continue;  // 最後のショップに行くのは残りショップ数が1のときだけ
            //         mvto_shop = u;
            //         break;
            //     }
            //     for (auto mv : mvs) {
            //         point v = u + mv;
            //         if (!ingrid(v)) continue;
            //         if (done[v.r][v.c]) continue;
            //         done[v.r][v.c] = true;
            //         que.push(v);
            //     }
            // }
        }

        // shopに移動
        {
            priority_queue<tuple<int, point, point>, vector<tuple<int, point, point>>, greater<tuple<int, point, point>>> pq;
            pq.push({0, now, {-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 == mvto_shop) 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 = mvto_shop;
                vector<point> route;
                while (true) {
                    route.push_back(cur);
                    if (cur == now) 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});
                }
                now = mvto_shop;
            }
        }
        solve1(now, tbl, ops);
    }
    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 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;
    }
    solve();
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード