#929501 (C++14) No.5019 Hakai Project

• 問題: No.5019 Hakai Project
• ユーザー: Shun_PI
• 提出日時: 2023-11-19 02:18:44
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2,786 ms / 3,000 ms
• コード長: 11,842 bytes
• コンパイル時間: 4,226 ms
• コンパイル使用メモリ: 237,992 KB
• 実行使用メモリ: 6,676 KB
• スコア: 2,330,851,455
• 最終ジャッジ日時: 2023-11-19 02:21:13
• 合計ジャッジ時間: 147,741 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2,706 ms; 6,676 KB
testcase_01	AC	2,704 ms; 6,676 KB
testcase_02	AC	2,724 ms; 6,676 KB
testcase_03	AC	2,703 ms; 6,676 KB
testcase_04	AC	2,679 ms; 6,676 KB
testcase_05	AC	2,670 ms; 6,676 KB
testcase_06	AC	2,682 ms; 6,676 KB
testcase_07	AC	2,710 ms; 6,676 KB
testcase_08	AC	2,739 ms; 6,676 KB
testcase_09	AC	2,673 ms; 6,676 KB
testcase_10	AC	2,786 ms; 6,676 KB
testcase_11	AC	2,730 ms; 6,676 KB
testcase_12	AC	2,715 ms; 6,676 KB
testcase_13	AC	2,678 ms; 6,676 KB
testcase_14	AC	2,691 ms; 6,676 KB
testcase_15	AC	2,738 ms; 6,676 KB
testcase_16	AC	2,758 ms; 6,676 KB
testcase_17	AC	2,708 ms; 6,676 KB
testcase_18	AC	2,669 ms; 6,676 KB
testcase_19	AC	2,672 ms; 6,676 KB
testcase_20	AC	2,684 ms; 6,676 KB
testcase_21	AC	2,714 ms; 6,676 KB
testcase_22	AC	2,727 ms; 6,676 KB
testcase_23	AC	2,681 ms; 6,676 KB
testcase_24	AC	2,727 ms; 6,676 KB
testcase_25	AC	2,693 ms; 6,676 KB
testcase_26	AC	2,653 ms; 6,676 KB
testcase_27	AC	2,699 ms; 6,676 KB
testcase_28	AC	2,720 ms; 6,676 KB
testcase_29	AC	2,667 ms; 6,676 KB
testcase_30	AC	2,703 ms; 6,676 KB
testcase_31	AC	2,729 ms; 6,676 KB
testcase_32	AC	2,699 ms; 6,676 KB
testcase_33	AC	2,693 ms; 6,676 KB
testcase_34	AC	2,677 ms; 6,676 KB
testcase_35	AC	2,668 ms; 6,676 KB
testcase_36	AC	2,678 ms; 6,676 KB
testcase_37	AC	2,676 ms; 6,676 KB
testcase_38	AC	2,666 ms; 6,676 KB
testcase_39	AC	2,684 ms; 6,676 KB
testcase_40	AC	2,694 ms; 6,676 KB
testcase_41	AC	2,672 ms; 6,676 KB
testcase_42	AC	2,750 ms; 6,676 KB
testcase_43	AC	2,743 ms; 6,676 KB
testcase_44	AC	2,730 ms; 6,676 KB
testcase_45	AC	2,683 ms; 6,676 KB
testcase_46	AC	2,719 ms; 6,676 KB
testcase_47	AC	2,707 ms; 6,676 KB
testcase_48	AC	2,762 ms; 6,676 KB
testcase_49	AC	2,697 ms; 6,676 KB

ソースコード

#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 = 2500;
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};
vector<vector<int>> move_idx = {
  {0, 1, 2, 3, 4, 5, 6, 7, 8},
  {0, 1, 8, 7, 6, 5, 4, 3, 2},
  {0, 3, 4, 5, 6, 7, 8, 1, 2},
  {0, 3, 2, 1, 8, 7, 6, 5, 4},
  {0, 5, 6, 7, 8, 1, 2, 3, 4},
  {0, 5, 4, 3, 2, 1, 8, 7, 6},
  {0, 7, 8, 1, 2, 3, 4, 5, 6},
  {0, 7, 6, 5, 4, 3, 2, 1, 8},
};
vector<vector<int>> move_dir = {
  {0, 2, 1, 1, 3, 3, 0, 0},
  {0, 3, 1, 1, 2, 2, 0, 0},
  {2, 1, 3, 3, 0, 0, 2, 2},
  {2, 0, 3, 3, 1, 1, 2, 2},
  {1, 3, 0, 0, 2, 2, 1, 1},
  {1, 2, 0, 0, 3, 3, 1, 1},
  {3, 0, 2, 2, 1, 1, 3, 3},
  {3, 1, 2, 2, 0, 0, 3, 3},
};

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;
    //if(mt() % 5 == 0) shopcnt = 5;
    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) <= 21 && abs(y1 - y2) <= 21) 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.3 + 1);
    }

    if(value > best_value) {
      best_value = value;
      best_shop = shop;
      best_shop_area = shop_area;
    }
  }

  int S = best_shop.size();
  cerr << S << "\n";

  //爆破計画の決定
  //今いるマスから最も近い爆弾屋に移動
  //その爆弾屋の爆破領域にある建物を全て破壊できるような爆破計画を決める
  //爆弾屋のマスと周囲1マスの計9マスにおける爆弾の集合を焼く
  //爆弾は最初に必ず全て買う必要がある（爆弾屋はすぐに吹っ飛ぶので）
  //周囲1マスの移動経路は8通りあるので最もコストの低い方法を使う

  //爆破計画を焼く
  //全ての爆弾屋の周囲9マスの起爆を同時に焼く
  int best_cost = 1e9;
  vector<int> best_move_id(S, -1);
  vector<vector<int>> best_bomb_set(S, vector<int>(9));
  vector<vector<int>> best_bomb_cnt(N, vector<int>(N, 0));
  int best_cost_sub = 1e9;
  vector<vector<int>> best_bomb_set_sub(S, vector<int>(9));
  vector<vector<int>> best_bomb_cnt_sub(N, vector<int>(N, 0));
  int rest = 0;
  REP(i, N) REP(j, N) if(A[i][j] != '.') rest++;
  //計画済みの爆弾をいくつか消す→全ての建物を破壊できるようになるまでランダムに爆弾を追加　を繰り返す
  auto start_time = chrono::system_clock::now();
  double start_temp = 2.0;
  double end_temp = 1.0;
  double temp = start_temp;
  int loop = 0;
  while(true) {
    if(loop%500 == 0) {
      double time = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start_time).count();
      cerr << loop << " " << best_cost_sub << " " << best_cost << " " << time << "\n";
      if(time > TIME_LIMIT) break;
      temp = start_temp + (end_temp - start_temp) * time / TIME_LIMIT;
    }
    loop++;

    vector<vector<int>> bomb_set(best_bomb_set_sub);
    vector<vector<int>> bomb_cnt(best_bomb_cnt_sub);
    //ランダムに爆弾を消す
    if(loop > 1) {
      int remove_cnt = 1;
      REP(z, remove_cnt) {
        while(true) {
          int sh = mt() % S;
          int r = mt() % 9;
          int s = mt() % M;
          if(bomb_set[sh][r] >> s & 1) {
            bomb_set[sh][r] ^= 1 << s;
            REP(i, L[s]) {
              int nx = shopx[best_shop[sh]] + a[s][i] + dx9[r];
              int ny = shopy[best_shop[sh]] + b[s][i] + dy9[r];
              if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
              bomb_cnt[nx][ny]--;
              if(A[nx][ny] != '.' && bomb_cnt[nx][ny] == 0) rest++;
            }
            break;
          }
        }
      }
    }

    //restが0になるまで爆弾を追加する
    //restが減らないような追加は許さない
    while(rest > 0) {
      int sh = mt() % S;
      int r = mt() % 9;
      int s = mt() % M;
      if(bomb_set[sh][r] >> s & 1) continue;
      bool ok = false;
      REP(i, L[s]) {
        int nx = shopx[best_shop[sh]] + a[s][i] + dx9[r];
        int ny = shopy[best_shop[sh]] + b[s][i] + dy9[r];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if(A[nx][ny] != '.' && bomb_cnt[nx][ny] == 0) {
          ok = true;
          break;
        }
      }
      if(!ok) continue;
      bomb_set[sh][r] ^= 1 << s;
      REP(i, L[s]) {
        int nx = shopx[best_shop[sh]] + a[s][i] + dx9[r];
        int ny = shopy[best_shop[sh]] + b[s][i] + dy9[r];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if(A[nx][ny] != '.' && bomb_cnt[nx][ny] == 0) rest--;
        bomb_cnt[nx][ny]++;
      }
    }

    //コストの計算(8種類の移動方法に関して計算し最も小さい値)
    int cost_sum = 0;
    vector<int> move_id(S, -1);
    REP(sh, S) {
      int cost = 1e9;
      REP(move_id_sub, 8) {
        int cost_sub = 0;
        int have_bombs = 0;
        REP(i, 9) REP(j, M) if(bomb_set[sh][i] >> j & 1) have_bombs++;
        for(int i : move_idx[move_id_sub]) {
          if(have_bombs == 0) break;
          REP(j, M) if(bomb_set[sh][i] >> j & 1) {
            cost_sub += C[j];
            have_bombs--;
          }
          cost_sub += 1 * (have_bombs + 1) * (have_bombs + 1);
        }
        if(cost_sub < cost) {
          cost = cost_sub;
          move_id[sh] = move_id_sub;
        }
      }
      cost_sum += cost;
    }

    double prob = exp(((double)best_cost_sub - cost_sum)*pow(0.1, temp));
    if(cost_sum <= best_cost_sub || prob > (mt()%INF)/(double)INF) {
      best_cost_sub = cost_sum;
      best_bomb_set_sub = bomb_set;
      best_bomb_cnt_sub = bomb_cnt;
      if(cost_sum < best_cost) {
        best_cost = cost_sum;
        best_bomb_set = bomb_set;
        best_bomb_cnt = bomb_cnt;
        best_move_id = move_id;
      }
    }
  }

  vector<P> ans;
  int ans_cost = 0;
  int x = 0;
  int y = 0;
  int rest_shop = S;
  vector<bool> done_shop(S);
  while(rest_shop > 0) {
    rest_shop--;
    int min_dist = INF;
    int min_sh = -1;
    REP(sh, S) if(!done_shop[sh]) {
      int shopid = best_shop[sh];
      int dist = abs(shopx[shopid] - x) + abs(shopy[shopid] - y);
      if(dist < min_dist) {
        min_dist = dist;
        min_sh = sh;
      }
    }
    done_shop[min_sh] = true;
    int min_shop = best_shop[min_sh];

    //移動
    //TODO: ちゃんと建物のコストを考慮してダイクストラ？
    bool can_cost_2 = false;
    while(x != shopx[min_shop] || y != shopy[min_shop]) {
      bool moved = false;
      REP(dir, 4) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if(!can_cost_2 && A[nx][ny] != '.') continue;
        if(abs(x - shopx[min_shop]) + abs(y - shopy[min_shop]) > abs(nx - shopx[min_shop]) + abs(ny - shopy[min_shop])) {
          ans.push_back({1, dir});
          x = nx;
          y = ny;
          if(A[x][y] == '.') ans_cost += 1;
          else ans_cost += 2;
          can_cost_2 = false;
          moved = true;
        }
      }
      if(!moved) can_cost_2 = true;
    }

    //爆弾を購入
    int have_bombs = 0;
    REP(i, 9) REP(j, M) if(best_bomb_set[min_sh][i] >> j & 1) {
      assert(A[x][y] == '@');
      ans.push_back({2, j+1});
      ans_cost += C[j];
      have_bombs++;
    }

    //爆破計画に従って行動する
    //とりあえず単一の移動経路だけ考える
    REP(k, 9) {
      int i = move_idx[best_move_id[min_sh]][k];
      REP(j, M) if(best_bomb_set[min_sh][i] >> j & 1) {
        ans.push_back({3, j+1});
        have_bombs--;
        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(have_bombs == 0) break;
      int dir = move_dir[best_move_id[min_sh]][k];
      ans.push_back({1, dir});
      x += dx[dir];
      y += dy[dir];
      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";
}