結果
| 問題 | No.5019 Hakai Project |
| コンテスト | |
| ユーザー |
👑  wanui
|
| 提出日時 | 2023-11-17 21:00:01 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,793 ms / 3,000 ms |
| コード長 | 15,827 bytes |
| 記録 | |
| コンパイル時間 | 3,860 ms |
| コンパイル使用メモリ | 252,960 KB |
| 実行使用メモリ | 19,592 KB |
| スコア | 2,686,365,695 |
| 最終ジャッジ日時 | 2023-11-17 21:01:13 |
| 合計ジャッジ時間 | 71,548 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
main.cpp: In function 'int getmove(point, point)':
main.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
103 | }
| ^
ソースコード
#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];
}
}
vector<operation_t> ops;
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;
// ある爆弾をある位置まで1個だけ運んで爆発させる操作を繰り返す。操作は(爆発させる場所、爆弾) の組で表現できる。
// 最も良い操作として、(移動コスト+爆弾コスト)/破壊する建物数 が一番小さい操作を選ぶ
// 再計算をさぼるため、爆弾を買う場所も記録しておく。
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();
/*
int break_building = 0;
int break_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++;
}
}
*/
// 店の残り数に余裕があるときは店を破壊してもよい。
// 余裕があるとは： 盤面を4分割した区画それぞれで、1個以上店が残れば十分とする。
// 店の残り数に余裕がないときは、店の破壊を可能な限り避ける。//TODO 理想的には「もうここでは爆弾を買わない店」を破壊することにしたい
// 建物がなくなったら店を破壊すべき。
int shop_quarter_cnt = 0;
{
// ※最初から1個も店がない区画があるときには悪いスコアがでる
array<int, 4> quarter = {0, 0, 0, 0};
for (auto shop : shops) {
if (!break_shop_bs[_p(shop.r, shop.c)]) {
if (shop.r < N / 2 && shop.c < N / 2) {
quarter[0]++;
} else if (shop.r < N / 2 && shop.c >= N / 2) {
quarter[1]++;
} else if (shop.r >= N / 2 && shop.c < N / 2) {
quarter[2]++;
} else {
quarter[3]++;
}
}
}
shop_quarter_cnt += quarter[0] > 0;
shop_quarter_cnt += quarter[1] > 0;
shop_quarter_cnt += quarter[2] > 0;
shop_quarter_cnt += quarter[3] > 0;
}
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 (shop_quarter_cnt == 4) {
if (break_building == 0) continue;
score = 1.0 * (-cost) / break_building;
} else {
if (break_building == 0) continue;
score = 1.0 * (-cost - 10000 * break_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();
}