結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 Shun_PI
|
| 提出日時 | 2023-11-19 00:50:06 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,307 ms / 3,000 ms |
| コード長 | 9,717 bytes |
| コンパイル時間 | 4,482 ms |
| コンパイル使用メモリ | 231,112 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 1,928,784,906 |
| 最終ジャッジ日時 | 2023-11-19 00:52:00 |
| 合計ジャッジ時間 | 111,299 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;using lint = long long int;using P = pair<int, int>;using PL = pair<lint, lint>;#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)#define ALL(a) (a).begin(),(a).end()constexpr int MOD = 1000000007;constexpr lint B1 = 1532834020;constexpr lint M1 = 2147482409;constexpr lint B2 = 1388622299;constexpr lint M2 = 2147478017;constexpr int INF = 2147483647;void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";}template<class T>void chmax(T &a, const T &b) { if (a<b) a=b; }template<class T>void chmin(T &a, const T &b) { if (b<a) a=b; }constexpr int TIME_LIMIT = 400;vector<int> dx = {0, 0, -1, 1};vector<int> dy = {-1, 1, 0, 0};vector<char> dc = {'L', 'R', 'U', 'D'};vector<int> dx9 = {0, 0, -1, -1, -1, 0, 1, 1, 1};vector<int> dy9 = {0, -1, -1, 0, 1, 1, 1, 0, -1};int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int N, M;cin >> N >> M;vector<string> A(N);REP(i, N) cin >> A[i];vector<int> C(M), L(M);vector<vector<int>> a(M), b(M);REP(i, M) {cin >> C[i] >> L[i];REP(j, L[i]) {int x, y;cin >> x >> y;a[i].push_back(x);b[i].push_back(y);}}vector<int> shopx, shopy;REP(i, N) REP(j, N) {if(A[i][j] == '@') {shopx.push_back(i);shopy.push_back(j);}}int K = shopx.size();mt19937 mt(0);//爆弾屋の選択//要件1. 2つの爆弾屋で爆破領域が被ってはいけない//要件2. 全ての爆弾屋の爆破領域の和集合が全てのマスに到達//評価関数：各爆弾屋から最も近いマスをその爆弾屋の領域として、爆破しやすさの和を計算することで決めたい//爆弾屋の個数は4つが良いが5つのケースも考える？double best_value = 0;vector<int> best_shop;vector<vector<int>> best_shop_area;REP(z, 5000) {//爆弾屋の個数int shopcnt = 4 + mt() % 3;set<int> shopset;REP(zz, 1000) {if (shopset.size() == shopcnt) break;int r = mt() % K;bool ok = true;if(shopx[r] == 0 || shopx[r] == N-1 || shopy[r] == 0 || shopy[r] == N-1) ok = false;for(int shopid : shopset) {//要件1のチェックint x1 = shopx[shopid], y1 = shopy[shopid];int x2 = shopx[r], y2 = shopy[r];//移動分も考慮して余裕を持たせるif(abs(x1 - x2) <= 22 && abs(y1 - y2) <= 22) ok = false;//マップ端の爆弾屋は使用しない}if(!ok) continue;shopset.insert(r);}if(shopset.size() != shopcnt) continue;vector<int> shop(shopset.begin(), shopset.end());bool ok = true;//要件2のチェックvector<vector<bool>> can_bomb(N, vector<bool>(N, false));REP(i, shop.size()) {int x = shopx[shop[i]], y = shopy[shop[i]];FOR(dx, -20, 21) FOR(dy, -20, 21) {int nx = x + dx, ny = y + dy;if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;can_bomb[nx][ny] = true;}}int cnt = 0;REP(i, N) REP(j, N) if(can_bomb[i][j]) cnt++;if(cnt != N*N) ok = false;if(!ok) continue;//爆弾屋領域の決定と評価値の計算（最も近い爆弾屋を割り当てる）double value = 0;vector<vector<int>> shop_area(N, vector<int>(N, -1));REP(i, N) REP(j, N) {int min_dist = INF;REP(k, shop.size()) {int x = shopx[shop[k]], y = shopy[shop[k]];int dist = max(abs(x - i), abs(y - j));if(dist < min_dist) {min_dist = dist;shop_area[i][j] = shop[k];}}assert(min_dist <= 20);//評価値value += 1.0 / (min_dist * 0.2 + 1);}if(value > best_value) {best_value = value;best_shop = shop;best_shop_area = shop_area;}}//爆破計画の決定//今いるマスから最も近い爆弾屋に移動//その爆弾屋の爆破領域にある建物を全て破壊できるような爆破計画を決める//爆弾屋のマスと周囲1マスの計9マスにおける爆弾の集合を焼く//爆弾は最初に必ず全て買う必要がある（爆弾屋はすぐに吹っ飛ぶので）//周囲1マスの移動経路は8通りあるので最もコストの低い方法を使うvector<P> ans;int ans_cost = 0;int x = 0;int y = 0;set<int> rest_shop(best_shop.begin(), best_shop.end());while(!rest_shop.empty()) {int min_dist = INF;int min_shop = -1;for(int shopid : rest_shop) {int dist = abs(shopx[shopid] - x) + abs(shopy[shopid] - y);if(dist < min_dist) {min_dist = dist;min_shop = shopid;}}rest_shop.erase(min_shop);//移動//TODO: ちゃんと建物のコストを考慮してダイクストラするwhile(y > shopy[min_shop]) {ans.push_back({1, 0});y--;if(A[x][y] == '.') ans_cost += 1;else ans_cost += 2;}while(y < shopy[min_shop]) {ans.push_back({1, 1});y++;if(A[x][y] == '.') ans_cost += 1;else ans_cost += 2;}while(x > shopx[min_shop]) {ans.push_back({1, 2});x--;if(A[x][y] == '.') ans_cost += 1;else ans_cost += 2;}while(x < shopx[min_shop]) {ans.push_back({1, 3});x++;if(A[x][y] == '.') ans_cost += 1;else ans_cost += 2;}//爆破計画を焼くvector<int> best_bomb_set(9);vector<vector<int>> best_bomb_cnt(N, vector<int>(N, 0));int rest = 0;REP(i, N) REP(j, N) if(A[i][j] != '.' && best_shop_area[i][j] == min_shop) rest++;//計画済みの爆弾をいくつか消す→全ての建物を破壊できるようになるまでランダムに爆弾を追加 を繰り返すauto start_time = chrono::system_clock::now();int best_cost = 1e9;int loop = 0;while(true) {if(loop%1000 == 0) {cerr << loop << " " << best_cost << "\n";double time = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start_time).count();if(time > TIME_LIMIT) break;}loop++;vector<int> bomb_set(best_bomb_set);vector<vector<int>> bomb_cnt(best_bomb_cnt);//ランダムに爆弾を消すif(loop > 1) {while(true) {int r = mt() % 9;int s = mt() % M;if(bomb_set[r] >> s & 1) {bomb_set[r] ^= 1 << s;REP(i, L[s]) {int nx = x + a[s][i] + dx9[r];int ny = y + b[s][i] + dy9[r];if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;bomb_cnt[nx][ny]--;if(A[nx][ny] != '.' && best_shop_area[nx][ny] == min_shop && bomb_cnt[nx][ny] == 0) rest++;}break;}}}//restが0になるまで爆弾を追加するwhile(rest > 0) {int r = mt() % 9;int s = mt() % M;if(bomb_set[r] >> s & 1) continue;bomb_set[r] ^= 1 << s;REP(i, L[s]) {int nx = x + a[s][i] + dx9[r];int ny = y + b[s][i] + dy9[r];if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;bomb_cnt[nx][ny]++;if(A[nx][ny] != '.' && best_shop_area[nx][ny] == min_shop && bomb_cnt[nx][ny] == 1) rest--;}}//コストの計算int cost = 0;REP(i, 9) REP(j, M) if(bomb_set[i] >> j & 1) cost += C[j];if(cost < best_cost) {best_cost = cost;best_bomb_set = bomb_set;best_bomb_cnt = bomb_cnt;}}//爆弾を購入int have_bombs = 0;REP(i, 9) REP(j, M) if(best_bomb_set[i] >> j & 1) {assert(A[x][y] == '@');ans.push_back({2, j+1});ans_cost += C[j];have_bombs++;}//爆破計画に従って行動する//とりあえず単一の移動経路だけ考えるREP(i, 9) {REP(j, M) if(best_bomb_set[i] >> j & 1) {ans.push_back({3, j+1});REP(k, L[j]) {int nx = x + a[j][k];int ny = y + b[j][k];if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;if(A[nx][ny] != '.') A[nx][ny] = '.';}}if(i == 0 || i == 6 || i == 7) {ans.push_back({1, 0});y--;if(A[x][y] == '.') ans_cost += 1 * (have_bombs + 1) * (have_bombs + 1);else ans_cost += 2 * (have_bombs + 1) * (have_bombs + 1);} else if(i == 2 || i == 3) {ans.push_back({1, 1});y++;if(A[x][y] == '.') ans_cost += 1 * (have_bombs + 1) * (have_bombs + 1);else ans_cost += 2 * (have_bombs + 1) * (have_bombs + 1);} else if(i == 1) {ans.push_back({1, 2});x--;if(A[x][y] == '.') ans_cost += 1 * (have_bombs + 1) * (have_bombs + 1);else ans_cost += 2 * (have_bombs + 1) * (have_bombs + 1);} else if(i == 4 || i == 5) {ans.push_back({1, 3});x++;if(A[x][y] == '.') ans_cost += 1 * (have_bombs + 1) * (have_bombs + 1);else ans_cost += 2 * (have_bombs + 1) * (have_bombs + 1);}}REP(i, N) cerr << A[i] << "\n";}//爆破計画の出力cout << ans.size() << "\n";for(P p : ans) {if(p.first != 1) cout << p.first << " " << p.second << "\n";else cout << p.first << " " << dc[p.second] << "\n";}cerr << ans_cost << "\n";}