結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 wanui
|
| 提出日時 | 2023-11-19 14:30:54 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,862 ms / 3,000 ms |
| コード長 | 28,344 bytes |
| コンパイル時間 | 4,902 ms |
| コンパイル使用メモリ | 274,012 KB |
| 実行使用メモリ | 452,100 KB |
| スコア | 2,822,145,750 |
| 最終ジャッジ日時 | 2023-11-19 14:33:21 |
| 合計ジャッジ時間 | 146,724 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,666 ms
433,824 KB |
| testcase_01 | AC | 2,550 ms
436,068 KB |
| testcase_02 | AC | 2,629 ms
436,196 KB |
| testcase_03 | AC | 2,646 ms
433,280 KB |
| testcase_04 | AC | 2,556 ms
435,976 KB |
| testcase_05 | AC | 2,721 ms
432,704 KB |
| testcase_06 | AC | 2,640 ms
433,184 KB |
| testcase_07 | AC | 2,754 ms
436,128 KB |
| testcase_08 | AC | 2,493 ms
434,960 KB |
| testcase_09 | AC | 2,692 ms
435,644 KB |
| testcase_10 | AC | 2,552 ms
430,816 KB |
| testcase_11 | AC | 2,681 ms
439,452 KB |
| testcase_12 | AC | 2,640 ms
443,528 KB |
| testcase_13 | AC | 2,585 ms
443,268 KB |
| testcase_14 | AC | 2,616 ms
443,544 KB |
| testcase_15 | AC | 2,579 ms
441,836 KB |
| testcase_16 | AC | 2,581 ms
441,972 KB |
| testcase_17 | AC | 2,633 ms
442,020 KB |
| testcase_18 | AC | 2,673 ms
441,456 KB |
| testcase_19 | AC | 2,621 ms
443,676 KB |
| testcase_20 | AC | 2,665 ms
443,872 KB |
| testcase_21 | AC | 2,675 ms
444,004 KB |
| testcase_22 | AC | 2,535 ms
440,972 KB |
| testcase_23 | AC | 2,682 ms
447,860 KB |
| testcase_24 | AC | 2,637 ms
449,000 KB |
| testcase_25 | AC | 2,662 ms
446,408 KB |
| testcase_26 | AC | 2,608 ms
449,132 KB |
| testcase_27 | AC | 2,608 ms
449,200 KB |
| testcase_28 | AC | 2,591 ms
447,368 KB |
| testcase_29 | AC | 2,607 ms
445,488 KB |
| testcase_30 | AC | 2,531 ms
445,580 KB |
| testcase_31 | AC | 2,686 ms
444,844 KB |
| testcase_32 | AC | 2,713 ms
445,368 KB |
| testcase_33 | AC | 2,585 ms
447,620 KB |
| testcase_34 | AC | 2,701 ms
448,260 KB |
| testcase_35 | AC | 2,642 ms
447,540 KB |
| testcase_36 | AC | 2,568 ms
449,840 KB |
| testcase_37 | AC | 2,641 ms
448,680 KB |
| testcase_38 | AC | 2,719 ms
446,472 KB |
| testcase_39 | AC | 2,623 ms
450,456 KB |
| testcase_40 | AC | 2,698 ms
451,340 KB |
| testcase_41 | AC | 2,613 ms
449,936 KB |
| testcase_42 | AC | 2,543 ms
447,792 KB |
| testcase_43 | AC | 2,619 ms
452,100 KB |
| testcase_44 | AC | 2,862 ms
448,132 KB |
| testcase_45 | AC | 2,680 ms
447,148 KB |
| testcase_46 | AC | 2,761 ms
450,780 KB |
| testcase_47 | AC | 2,622 ms
451,288 KB |
| testcase_48 | AC | 2,625 ms
450,624 KB |
| testcase_49 | AC | 2,755 ms
451,208 KB |
コンパイルメッセージ
main.cpp: In function 'int getmove(point, point)':
main.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
113 | }
| ^
ソースコード
#include <bits/stdc++.h>
// clang-format off
using namespace std;
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;
using pii = pair<int, int>;
// 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) {
static int called = 0;
static double temp = 0;
if ((called & 127) == 0) {
double ratio = (cur_time - begin_time) / (end_time - begin_time);
ratio = min(ratio, 1.0);
temp = pow(begin_temp, 1.0 - ratio) * pow(end_temp, ratio);
}
called++;
const int ANNEAL_RND = 1e8;
const double ANNEAL_EPS = 1e-6;
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;
const int NNM = 50000;
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) {
// コスト上限が400くらいなのでpriority_queue不要
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];
}
}
vector<bool> done(N2);
vector<int> costs(N2, inf);
vector<vector<int>> cost_points(N * 4);
cost_points[0].push_back(_p(ini));
costs[_p(ini)] = 0;
for (int cost = 0; cost < N * 4; cost++) {
for (auto u : cost_points[cost]) {
if (done[u]) continue;
done[u] = true;
for (auto v : mvtbl[u]) {
int nc = cost + 1;
if (tbl_[v] != '.') {
nc = cost + 2;
}
if (done[v]) continue;
if (costs[v] <= nc) continue;
costs[v] = nc;
cost_points[nc].push_back(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)];
}
}
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;
}
pii 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};
}
int bomb_place_id(point p, int b) {
return b * N * N + p.r * N + p.c;
}
int bpid2bombid(int bpid) {
return bpid / N2;
}
point bpid2point(int bpid) {
return point{(bpid / N) % N, bpid % N};
}
namespace bomb_place_ns {
// buildingと書くのがタイプ数多いのでwallとしておく
uint16_t bpid2walls[NNM][N2];
uint16_t bpid2wall_size[NNM];
uint16_t wall2bpids[N2][NNM];
uint16_t wall2bpid_size[N2];
uint16_t good_bpids[NNM];
uint16_t good_bpid_size;
void push_bpid2walls(uint16_t bpid, uint16_t wall) {
bpid2walls[bpid][bpid2wall_size[bpid]] = wall;
bpid2wall_size[bpid]++;
}
void push_wall2bpids(uint16_t wall, uint16_t bpid) {
wall2bpids[wall][wall2bpid_size[wall]] = bpid;
wall2bpid_size[wall]++;
}
void push_goodbpids(uint16_t bpid) {
good_bpids[good_bpid_size] = bpid;
good_bpid_size++;
}
vector<int> hc_bomb_places(vector<int> init_bomb_places, vector<int> init_fillcnt) {
// 破壊再構築系の山登り
vector<int> bpid2cost(NNM);
for (int bpid = 0; bpid < NNM; bpid++) {
bpid2cost[bpid] = BOMBS[bpid2bombid(bpid)].cost;
}
int old_score = 0;
auto bomb_places = init_bomb_places;
auto fillcnt = init_fillcnt;
for (auto bpid : bomb_places) {
old_score += -bpid2cost[bpid];
}
debug1(old_score);
double begin_time = marathon::now();
double end_time = min(1500.0, begin_time + 1000);
int hc_iter = 0;
int hc_accept = 0;
static uint16_t bpid_cnt[NNM];
while (marathon::now() < end_time) {
hc_iter++;
vector<int> new_bomb_places = bomb_places;
auto new_fillcnt = fillcnt;
vector<int> notfilled;
int new_score = old_score;
int rmnum = marathon::randint(4, 6);
for (int r = 0; r < rmnum; r++) {
int remove_bpid = marathon::random_choice(new_bomb_places);
new_bomb_places.erase(std::remove(new_bomb_places.begin(), new_bomb_places.end(), remove_bpid), new_bomb_places.end());
new_score += bpid2cost[remove_bpid];
for (int _wid = 0; _wid < bpid2wall_size[remove_bpid]; _wid++) {
int pt = bpid2walls[remove_bpid][_wid];
new_fillcnt[pt]--;
if (new_fillcnt[pt] == 0) notfilled.push_back(pt);
}
}
while (notfilled.size()) { // この中の処理が非常に重い
for (int _gid = 0; _gid < good_bpid_size; _gid++) {
int bpid = good_bpids[_gid];
bpid_cnt[bpid] = 0;
}
for (auto wall : notfilled) {
for (int _bid = 0; _bid < wall2bpid_size[wall]; _bid++) {
int bpid = wall2bpids[wall][_bid];
bpid_cnt[bpid]++;
}
}
int bestbpid = 0;
int bestscore = -inf;
for (int _gid = 0; _gid < good_bpid_size; _gid++) {
int bpid = good_bpids[_gid];
if (bpid_cnt[bpid] > 0) {
// int score = -1000 * marathon::uniform(1.0, 2.0) * bpid2cost[bpid] / bpid_cnt[bpid];
int score = -1000 * bpid2cost[bpid] / bpid_cnt[bpid];
if (bestscore < score) {
bestscore = score;
bestbpid = bpid;
}
}
}
for (int _wid = 0; _wid < bpid2wall_size[bestbpid]; _wid++) {
int wall = bpid2walls[bestbpid][_wid];
new_fillcnt[wall]++;
if (new_fillcnt[wall] == 1) {
notfilled.erase(std::remove(notfilled.begin(), notfilled.end(), wall), notfilled.end());
}
}
new_score -= bpid2cost[bestbpid];
new_bomb_places.push_back(bestbpid);
}
if (new_score > old_score) {
old_score = new_score;
bomb_places = new_bomb_places;
fillcnt = new_fillcnt;
hc_accept++;
}
}
debug3(hc_iter, hc_accept, old_score);
return bomb_places;
}
vector<int> make_bomb_places() {
// 詰み防止のため建物がなくなるまで破壊してはいけない店舗を１個だけ決めておく
vector<bool> is_hub_shop(N2);
if (0) {
point center = {12, 12};
pair<int, point> minshop = {inf, {-1, -1}};
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (TBL_INIT[r][c] == '@') {
point now = {r, c};
int distance = abs(center.r - now.r) + abs(center.c - now.c);
minshop = min(minshop, {distance, now});
}
}
}
is_hub_shop[_p(minshop.second)] = true;
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
for (int b = 0; b < M; b++) {
point place = point{r, c};
int bpid = bomb_place_id(place, b);
// ハブ店を破壊する爆弾配置は除外する
bool valid = true;
for (auto drc : BOMBS[b].ranges) {
point pt = place + drc;
if (!ingrid(pt)) continue;
if (is_hub_shop[_p(pt)]) valid = false;
}
if (!valid) continue;
for (auto drc : BOMBS[b].ranges) {
point pt = place + drc;
if (!ingrid(pt)) continue;
if (TBL_INIT[pt.r][pt.c] != '#') continue;
push_bpid2walls(bpid, _p(pt));
push_wall2bpids(_p(pt), bpid);
}
}
}
}
// 初期解を作る
// 破壊できる確率が低い建物を破壊できたときのスコアを高く見積もる
vector<int> wall_score(N2);
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int u = _p(r, c);
if (wall2bpid_size[u]) {
wall_score[u] = 2e5 / wall2bpid_size[u];
}
}
}
int all_walls = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (TBL_INIT[r][c] == '#') all_walls++;
}
}
{
vector<pair<double, int>> cand;
for (int bpid = 0; bpid < NNM; bpid++) {
int ws = 0;
for (int _wid = 0; _wid < bpid2wall_size[bpid]; _wid++) {
int wall = bpid2walls[bpid][_wid];
ws += wall_score[wall];
}
double score = -1.0 * BOMBS[bpid2bombid(bpid)].cost / ws;
cand.push_back({score, bpid});
}
sort(cand.rbegin(), cand.rend());
const int usenum = NNM / 2;
for (int i = 0; i < usenum; i++) {
push_goodbpids(cand[i].second);
}
}
vector<int> bomb_places;
vector<int> fillcnt(N2);
{
bsn2 filled = 0;
while (filled.count() < all_walls) {
double bestscore = -1e18;
int bestbpid = -1;
vector<pair<double, int>> topbpids;
for (int _gid = 0; _gid < good_bpid_size; _gid++) {
int bpid = good_bpids[_gid];
int ws = 0;
for (int _wid = 0; _wid < bpid2wall_size[bpid]; _wid++) {
int wall = bpid2walls[bpid][_wid];
if (!filled[wall]) {
ws += wall_score[wall];
}
}
if (ws > 0) {
double score = -1.0 * BOMBS[bpid2bombid(bpid)].cost / ws;
if (bestscore < score) {
bestscore = score;
bestbpid = bpid;
}
}
}
bomb_places.push_back(bestbpid);
for (int _wid = 0; _wid < bpid2wall_size[bestbpid]; _wid++) {
int wall = bpid2walls[bestbpid][_wid];
fillcnt[wall]++;
filled[wall] = 1;
}
}
}
debug2("greedy_end", marathon::now());
return hc_bomb_places(bomb_places, fillcnt);
}
} // namespace bomb_place_ns
void dprestore(vector<int> route, vector<int> bomb_places, vector<vector<pii>> frm, vector<vector<point>> &midshops,
vector<operation_t> &ops, vector<vector<char>> &ops_tbl, point &ops_hulk) {
vector<pii> dpstates;
{
int hasbomb = 0;
int r = int(route.size()) - 2;
dpstates.push_back({hasbomb, r});
while (r > 0) {
dpstates.push_back(frm[hasbomb][r]);
tie(hasbomb, r) = frm[hasbomb][r];
}
}
reverse(dpstates.begin(), dpstates.end());
int m = dpstates.size();
for (int i = 1; i < m; i++) {
int hasbomb, r;
tie(hasbomb, r) = dpstates[i];
int bpid = bomb_places[route[r]];
point bombpt = bpid2point(bpid);
int pre_bombs = dpstates[i - 1].first;
if (pre_bombs == 0) {
point shop = midshops[hasbomb][r];
int mind = inf;
dij_goto_ops(ops_hulk, shop, ops, ops_tbl);
int buynum = hasbomb + 1;
for (int future = i; future < i + buynum; future++) {
int fr = dpstates[future].second;
int fbombid = bpid2bombid(bomb_places[route[fr]]);
ops.push_back({2, fbombid});
}
dij_goto_ops(ops_hulk, bombpt, ops, ops_tbl);
} else {
dij_goto_ops(ops_hulk, bombpt, ops, ops_tbl);
}
int bombid = bpid2bombid(bomb_places[route[r]]);
ops.push_back({3, bombid});
for (auto drc : BOMBS[bombid].ranges) {
point pt = ops_hulk + drc;
if (!ingrid(pt)) continue;
ops_tbl[pt.r][pt.c] = '.';
}
}
}
double route_move(vector<int> &route, vector<int> &bomb_places, bool do_restore, vector<operation_t> &ops, vector<vector<char>> &ops_tbl, point &ops_hulk) {
// ABCの典型っぽい。 中間点を通る最短経路問題 + 爆弾を買う個数をDP
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];
}
}
int cost = 0;
int m = route.size();
const int BUYMAX = 5;
vector<vector<int>> dp(BUYMAX, vector<int>(route.size(), inf));
vector<vector<pii>> frm(BUYMAX, vector<pii>(route.size()));
vector<vector<point>> midshops(BUYMAX, vector<point>(route.size()));
dp[0][0] = 0;
for (int r = 1; r < int(route.size()) - 1; r++) {
int bpid = bomb_places[route[r]];
point bombpt = bpid2point(bpid);
auto cost_hulk = dij_cost(hulk, tbl);
auto cost_bomb = dij_cost(bombpt, tbl);
{
// 爆弾持ってないので、途中で店に寄る
for (int buy = 1; buy <= BUYMAX; buy++) {
int now_mincost = inf;
point bestshop = {-1, -1};
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (tbl[r][c] == '@') {
int curcost = cost_hulk[r][c] + cost_bomb[r][c] * (buy + 1) * (buy + 1);
if (now_mincost > curcost) {
now_mincost = curcost;
bestshop = {r, c};
}
}
}
}
midshops[buy - 1][r] = bestshop;
int dptrans = dp[0][r - 1] + now_mincost;
if (dp[buy - 1][r] > dptrans) {
dp[buy - 1][r] = dptrans;
frm[buy - 1][r] = {0, r - 1};
}
}
}
{
// 爆弾持ってるので直接移動
for (int hasbomb = 1; hasbomb <= BUYMAX - 1; hasbomb++) {
int dptrans = dp[hasbomb][r - 1] + cost_hulk[bombpt.r][bombpt.c] * (hasbomb + 1) * (hasbomb + 1);
if (dp[hasbomb - 1][r] > dptrans) {
dp[hasbomb - 1][r] = dptrans;
frm[hasbomb - 1][r] = {hasbomb, r - 1};
}
}
}
for (auto drc : BOMBS[bpid2bombid(bpid)].ranges) {
point pt = bombpt + drc;
if (!ingrid(pt)) continue;
tbl[pt.r][pt.c] = '.';
}
hulk = bombpt;
}
if (do_restore) {
// 復元を実施する
dprestore(route, bomb_places, frm, midshops, ops, ops_tbl, ops_hulk);
}
return dp[0][int(route.size()) - 2];
}
vector<int> bomb_places_tsp(vector<int> bomb_places) {
vector<operation_t> dummy_ops;
vector<vector<char>> dummy_ops_tbl;
point dummy_ops_hulk = {0, 0};
int m = bomb_places.size() + 2;
int start = m - 2;
int goal = m - 1;
vector<int> best_route;
double best_score = -1e18;
int route_search_iter = 0;
while (marathon::now() < 2400) {
route_search_iter++;
// コスト固定のTSP
vector<int> route;
route.push_back(start);
{
vector<int> perm(m - 2);
iota(perm.begin(), perm.end(), 0);
shuffle(perm.begin(), perm.end(), marathon::engine);
for (auto r : perm) {
route.push_back(r);
}
}
route.push_back(goal);
point ini = {0, 0};
vector<vector<int>> costtbl(m, vector<int>(m));
for (int i = 0; i < m - 1; i++) {
for (int j = 0; j < m - 1; j++) {
point src = i == start ? ini : bpid2point(bomb_places[i]);
point dest = i == start ? ini : bpid2point(bomb_places[j]);
costtbl[i][j] = abs(src.r - dest.r) + abs(src.c - dest.c);
}
}
double begin_temp = 5;
double end_temp = 0.5;
double old_score = 0;
for (int r = 1; r < int(route.size()); r++) {
old_score -= costtbl[route[r - 1]][route[r]];
}
int anneal_accepted = 0;
int anneal_iter = 0;
while (anneal_iter < 100000) {
anneal_iter++;
vector<int> new_route = route;
int x = 0;
int y = 0;
while (x == y) {
x = 1 + marathon::engine() % (int(new_route.size()) - 2);
y = 1 + marathon::engine() % (int(new_route.size()) - 2);
}
if (x > y) {
swap(x, y);
}
for (int i = x + 1; i <= y - 1; i++) {
int j = y - 1 - (i - (x + 1));
if (i > j) break;
swap(new_route[i], new_route[j]);
}
double new_score = 0;
for (int r = 1; r < int(new_route.size()); r++) {
new_score -= costtbl[new_route[r - 1]][new_route[r]];
}
if (marathon::anneal_accept(new_score, old_score, anneal_iter, 0, 50000, begin_temp, end_temp)) {
route = new_route;
old_score = new_score;
anneal_accepted++;
}
}
// 正しいコストで評価
double now_score = -route_move(route, bomb_places, false, dummy_ops, dummy_ops_tbl, dummy_ops_hulk);
if (best_score < now_score) {
best_route = route;
best_score = now_score;
debug1(best_score);
}
}
debug2(route_search_iter, best_score);
return best_route;
}
void solve() {
// 爆弾位置と爆弾IDからなる「爆弾配置」 の集合を山登りにより作る。
// 爆弾配置は N*N*M 種類存在し、そこから全ての建物を破壊しつつ爆弾コストが小さい集合を選ぶ。
vector<int> bomb_places = bomb_place_ns::make_bomb_places();
vector<operation_t> ops;
{
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];
}
}
{
// 爆弾配置が決まったら、コストが動的に変化するTSP的な問題を解く。
vector<int> route = bomb_places_tsp(bomb_places);
route_move(route, bomb_places, true, ops, tbl, hulk);
}
// 残った店を貪欲に破壊
while (true) {
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});
}
}
if (shops.size() == 0) break;
pair<double, int> bestop = {1e18, -1};
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;
}
}
}
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
point place = {r, c};
for (int bid = 0; bid < M; bid++) {
int break_shop = 0;
int break_hub_shop = 0;
for (auto drc : BOMBS[bid].ranges) {
point pt = place + drc;
if (!ingrid(pt)) continue;
if (tbl[pt.r][pt.c] == '@') break_shop++;
}
// (移動コスト+爆弾コスト)/破壊する店数 が最小の爆弾配置を選ぶ
double score = 1.0 * (move_cost[r][c] + BOMBS[bid].cost) / break_shop;
bestop = min(bestop, {score, bomb_place_id(place, bid)});
}
}
}
{
int bpid = bestop.second;
int bombid = bpid / N2;
point bombpt = bpid2point(bpid);
dij_goto_ops(hulk, midshop[bombpt.r][bombpt.c], 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();
}