#include // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair; const ll INF=4e18; void print0(){}; template void print0(H h,T... t){cout<void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);} #define debug1(a) { cerr<<#a<<":"< T random_choice(vector &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 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 mvs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; using bsn2 = bitset; vector> 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> dij_cost(point ini, vector> &tbl) { priority_queue, greater> pq; vector 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 done(N2); vector 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> result(N, vector(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 &ops, vector> &tbl) { priority_queue, vector>, greater>> pq; pq.push({0, hulk, {-1, -1}}); vector> costs(N, vector(N, inf)); vector> froms(N, vector(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 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 evaluate_ops(vector &ops) { vector> tbl(N, vector(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> tbl(N, vector(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 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 ops; // ある爆弾をある位置まで1個だけ運んで爆発させる操作を繰り返す貪欲。 // 各回での操作の種類数は N*N*M (爆発させる場所 * 爆弾の種類)。 時間に余裕がないので高速化が重要。 // 貪欲の評価関数として (移動コスト+爆弾コスト)/破壊する建物数 が一番小さい操作を選ぶ。 for (int breakloop = 0; true; breakloop++) { debug2(breakloop, marathon::now()); vector shops; vector 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 bestop = {{-1, -1}, {-1, -1}, -1}; { double bestscore = -1e18; auto hulk_cost = dij_cost(hulk, tbl); vector> midshop(N, vector(N, {-1, -1})); vector> move_cost(N, vector(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(); }