提出 #63336421

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
// input and output of modint
// istream &operator>>(istream &is, modint998244353 &a) {
//     long long v;
//     is >> v;
//     a = v;
//     return is;
// }
// ostream &operator<<(ostream &os, const modint998244353 &a) {
//     return os << a.val();
// }
// istream &operator>>(istream &is, modint1000000007 &a) {
//     long long v;
//     is >> v;
//     a = v;
//     return is;
// }
// ostream &operator<<(ostream &os, const modint1000000007 &a) {
//     return os << a.val();
// }
// istream &operator>>(istream &is, modint &a) {
//     long long v;
//     is >> v;
//     a = v;
//     return is;
// }
// ostream &operator<<(ostream &os, const modint &a) {
//     return os << a.val();
// }
// template <int m> istream &operator>>(istream &is, static_modint<m> &a) {
//     long long v;
//     is >> v;
//     a = v;
//     return is;
// }
// template <int m> ostream &operator<<(ostream &os, const static_modint<m> &a) {
//     return os << a.val();
// }
#define rep_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)  // rep(i, a): [0, a); rep(i, a, b): [a, b)
#define drep_(i, a_, b_, a, b, ...) for (int i = (a) - 1, lim##i = (b); i >= lim##i; --i)
#define drep(i, ...) drep_(i, __VA_ARGS__, __VA_ARGS__, __VA_ARGS__, 0)  // drep(i, a): [0, a); drep(i, a, b): [b, a)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#ifdef LOCAL
void debug_out() {
    cerr << endl;
}
template <class Head, class... Tail> void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}
#define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
using ll = long long;
using ld = long double;
using Vi = V<int>;
using VVi = VV<int>;
using Vl = V<ll>;
using VVl = VV<ll>;
using Vd = V<ld>;
using VVd = VV<ld>;
using Vb = V<bool>;
using VVb = VV<bool>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
template <class T> vector<T> make_vec(size_t n, T a) {
    return vector<T>(n, a);
}
template <class... Ts> auto make_vec(size_t n, Ts... ts) {
    return vector<decltype(make_vec(ts...))>(n, make_vec(ts...));
}
template <class T> inline void fin(const T x) {
    cout << x << '\n';
    exit(0);
}
template <class T> inline void deduplicate(vector<T> &a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}
template <class T> inline bool chmin(T &a, const T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, const T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline int sz(const T &x) {
    return x.size();
}
template <class T> inline int count_between(const vector<T> &a, T l, T r) {
    return lower_bound(all(a), r) - lower_bound(all(a), l);
}  // [l, r)
template <class T1, class T2> istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}
template <class T, size_t n> istream &operator>>(istream &is, array<T, n> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T, size_t n> ostream &operator<<(ostream &os, const array<T, n> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
template <class T> istream &operator>>(istream &is, vector<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
template <class T> istream &operator>>(istream &is, deque<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T> ostream &operator<<(ostream &os, const deque<T> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
inline ll floor_div(ll x, ll y) {
    if (y < 0) x = -x, y = -y;
    return x >= 0 ? x / y : (x - y + 1) / y;
}  // floor(x/y)
inline ll ceil_div(ll x, ll y) {
    if (y < 0) x = -x, y = -y;
    return x >= 0 ? (x + y - 1) / y : x / y;
}  // ceil(x/y)
inline int floor_log2(const ll x) {
    assert(x > 0);
    return 63 - __builtin_clzll(x);
}  // floor(log2(x))
inline int ceil_log2(const ll x) {
    assert(x > 0);
    return (x == 1) ? 0 : 64 - __builtin_clzll(x - 1);
}  // ceil(log2(x))
inline int popcount(const ll x) {
    return __builtin_popcountll(x);
}
struct fast_ios {
    fast_ios() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    };
} fast_ios_;
constexpr int INF = numeric_limits<int>::max() >> 1;
// constexpr ll INFll = numeric_limits<ll>::max() >> 1;
// constexpr ld EPS = 1e-10;
// const ld PI = acos(-1.0);
// using mint = modint998244353;
// using mint = modint1000000007;
// using mint = modint;
// using Vm = V<mint>; using VVm = VV<mint>;

// 時間計測
auto system_now = std::chrono::system_clock::now();
int check_time() {
    auto now = std::chrono::system_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(now - system_now).count();
}

#if DEBUG
constexpr float machine_spec = 0.5;
#elif LOCAL
constexpr float machine_spec = 1.4;
#else
constexpr float machine_spec = 1;
#endif
constexpr ll time_limit = (3000-50);

struct Timer{
    private:
        chrono::system_clock::time_point start = chrono::system_clock::now();
        chrono::system_clock::time_point lap = chrono::system_clock::now();
    public:
        // 実行開始時からの経過時間(ms)を返す
        int elapsed_ms(){
            auto now = chrono::system_clock::now();
            #if DEBUG or LOCAL
                return std::chrono::duration_cast<std::chrono::milliseconds>(now - start).count() * machine_spec;
            #else
                return std::chrono::duration_cast<std::chrono::milliseconds>(now - start).count();
            #endif
        }
        // ラップタイム(ms)を返す
        int lap_ms(){
            auto now = chrono::system_clock::now();
            #if DEBUG or LOCAL
                return std::chrono::duration_cast<std::chrono::milliseconds>(now - lap).count() * machine_spec;
            #else
                return std::chrono::duration_cast<std::chrono::milliseconds>(now - lap).count();
            #endif
        }
        // ラップを刻む
        void mark_lap(){
            lap = chrono::system_clock::now();
        }
} timer;

// 乱数
struct Xorshift {
    uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;

    uint32_t rand_int() {
        uint32_t t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    // 0以上mod未満の整数を乱択
    uint32_t rand_int(uint32_t mod) {
        return rand_int() % mod;
    }

    // l以上r未満の整数を乱択
    uint32_t rand_int(uint32_t l, uint32_t r) {
        assert(l < r);
        return l + rand_int(r - l);
    }

    // 0以上1以下の実数を乱沢
    double rand_double() {
        return (double)rand_int() / UINT32_MAX;
    }
};
Xorshift xor_shift;
int rnd() {
    return xor_shift.rand_int();
}

// 向き
const vector<int> Dx = {0, -1, 0, 1, 0};
const vector<int> Dy = {-1, 0, 1, 0, 0};
const vector<char> Dc = {'L', 'U', 'R', 'D', '.'};

// グローバル変数
constexpr int N = 20;
constexpr int N2 = N * N;
constexpr int MaxT = 2000;
int M;
char B[N][N];
int sx, sy;
int problem_type;


vector<string> C(N);

namespace opt {
using ai2 = array<int, 2>;
using ai400 = array<array<int, N>, N>;
ai2 start_pos;

constexpr array<array<int, 2>, 4> dir{{
    {1, 0},
    {0, 1},
    {-1, 0},
    {0, -1},
}};

// スタート地点から S の方向の岩を全て処理するとした場合の，穴から各マスへの距離
pair<int, vector<vector<int>>> compute_dist(int S) {
  int c = 0;
  auto [si, sj] = start_pos;

  auto dist = make_vec(N, N, INF);
  queue<ai2> que;
  dist[si][sj] = 0;
  que.push({si, sj});

  rep(k, 4) {
    auto [di, dj] = dir[k];
    auto [i, j] = start_pos;
    int d_max = 0;
    int d = 0;
    while (true) {
      i += di;
      j += dj;
      d++;
      if (i < 0 || i >= N || j < 0 || j >= N) break;
      if (C[i][j] == '@') {
        if (!(S >> k & 1))
          break;
        else {
          chmax(d_max, d);
          c++;
        }
      }
      dist[i][j] = 0;
      que.push({i, j});
    }
    c += d;
  }

  while (!que.empty()) {
    auto [i, j] = que.front();
    que.pop();
    for (auto [di, dj] : dir) {
      int i2 = i + di;
      int j2 = j + dj;
      if (i2 < 0 || i2 >= N || j2 < 0 || j2 >= N) continue;
      // if (C[i2][j2] == '@') continue;
      if (chmin(dist[i2][j2], dist[i][j] + 1)) {
        que.push({i2, j2});
      }
    }
  }
  return {c, dist};
}

struct Edge {
  int u, v, w;
};

pair<int, vector<ai2>> compute_cost_rocks(vector<vector<int>> cost) {
  // 岩でないマスは cost を 0 に上書き
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (C[i][j] != '@') cost[i][j] = 0;
    }
  }

  // 岩でないマスのみを対象として連結成分を求める
  vector<vector<int>> compId(N, vector<int>(N, -1));
  vector<vector<ai2>> comps;  // comps[k] : 成分 k に属するマスのリスト
  int compCount = 0;
  int di[4] = {1, 0, -1, 0}, dj[4] = {0, 1, 0, -1};
  // for (int i = 0; i < N; i++) {
  //   for (int j = 0; j < N; j++) {
  //     if (C[i][j] == '@' || compId[i][j] != -1) continue;
  //     comps.push_back({});
  //     queue<ai2> q;
  //     q.push({i, j});
  //     compId[i][j] = compCount;
  //     while (!q.empty()) {
  //       ai2 cur = q.front();
  //       q.pop();
  //       comps[compCount].push_back(cur);
  //       int x = cur[0], y = cur[1];
  //       for (int k = 0; k < 4; k++) {
  //         int nx = x + di[k], ny = y + dj[k];
  //         if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
  //         if (C[nx][ny] == '@' || compId[nx][ny] != -1) continue;
  //         compId[nx][ny] = compCount;
  //         q.push({nx, ny});
  //       }
  //     }
  //     compCount++;
  //   }
  // }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (C[i][j] == '@' || compId[i][j] != -1) continue;
      vector<ai2> curComp;  // 現在の成分のセルを一時格納
      queue<ai2> q;
      q.push({i, j});
      compId[i][j] = -2;  // 一時的なマーカー
      while (!q.empty()) {
        ai2 cur = q.front();
        q.pop();
        curComp.push_back(cur);
        int x = cur[0], y = cur[1];
        for (int k = 0; k < 4; k++) {
          int nx = x + di[k], ny = y + dj[k];
          if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
          if (C[nx][ny] == '@' || compId[nx][ny] != -1) continue;
          compId[nx][ny] = -2;
          q.push({nx, ny});
        }
      }
      // 鉱石（小文字）または穴（大文字）が含まれているかチェック
      bool valid = false;
      for (auto &cell : curComp) {
        char c = C[cell[0]][cell[1]];
        if (isalpha(c)) {
          valid = true;
          break;
        }
      }
      if (valid) {
        for (auto &cell : curComp) {
          compId[cell[0]][cell[1]] = compCount;
        }
        comps.push_back(curComp);
        compCount++;
      } else {
        // 無効な成分は compId を元に戻す
        for (auto &cell : curComp) {
          compId[cell[0]][cell[1]] = -1;
        }
      }
    }
  }

  // 結果格納用
  // distBetween[i][j] : 連結成分 i から成分 j への最短通過コスト
  // pathRocks[i][j]   : その最短経路上の岩('@')のマスのリスト
  vector<vector<int>> distBetween(compCount, vector<int>(compCount, INF));
  vector<vector<vector<ai2>>> pathRocks(compCount, vector<vector<ai2>>(compCount));

  // 各成分を始点として多始点Dijkstra を実施
  for (int comp = 0; comp < compCount; comp++) {
    vector<vector<int>> dist(N, vector<int>(N, INF));
    // 経路復元用：各マスの直前の座標。始点は {-1, -1} とする
    vector<vector<ai2>> prev(N, vector<ai2>(N, {-1, -1}));
    // 優先度付きキュー：(累積コスト, x, y)
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    // 成分 comp の各マスを出発点として登録
    for (auto &cell : comps[comp]) {
      int x = cell[0], y = cell[1];
      dist[x][y] = 0;
      prev[x][y] = {-1, -1};
      pq.push({0, x, y});
    }
    // Dijkstra の実施
    while (!pq.empty()) {
      auto [d, x, y] = pq.top();
      pq.pop();
      if (d > dist[x][y]) continue;
      for (int k = 0; k < 4; k++) {
        int nx = x + di[k], ny = y + dj[k];
        if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
        int nd = d + cost[nx][ny];
        if (nd < dist[nx][ny]) {
          dist[nx][ny] = nd;
          prev[nx][ny] = {x, y};
          pq.push({nd, nx, ny});
        }
      }
    }
    // 各ターゲット成分 j に対して，成分 j 内のマスの中で最短距離となるものを選ぶ
    for (int j = 0; j < compCount; j++) {
      int best = INF;
      ai2 bestCell = {-1, -1};
      for (auto &cell : comps[j]) {
        int x = cell[0], y = cell[1];
        if (dist[x][y] < best) {
          best = dist[x][y];
          bestCell = {x, y};
        }
      }
      distBetween[comp][j] = best;
      if (best == INF) continue;  // 経路が存在しない場合はスキップ

      // bestCell から出発点までの経路を復元
      vector<ai2> path;
      for (ai2 cur = bestCell; cur[0] != -1; cur = prev[cur[0]][cur[1]]) path.push_back(cur);
      reverse(path.begin(), path.end());

      // 経路上の岩('@')のマスのみ抽出
      vector<ai2> rocks;
      for (auto &cell : path) {
        int x = cell[0], y = cell[1];
        if (C[x][y] == '@') rocks.push_back(cell);
      }
      pathRocks[comp][j] = rocks;
    }
  }

  // MST のための辺リスト作成 (距離行列は対称なので distBetween[i][j] をそのまま使用)
  vector<Edge> edges;
  for (int i = 0; i < compCount; i++) {
    for (int j = i + 1; j < compCount; j++) {
      if (distBetween[i][j] < INF) edges.push_back({i, j, distBetween[i][j]});
    }
  }
  sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; });

  dsu uf(compCount);
  int totalCost = 0;
  vector<Edge> mstEdges;
  for (auto &e : edges) {
    if (!uf.same(e.u, e.v)) {
      uf.merge(e.u, e.v);
      totalCost += e.w;
      mstEdges.push_back(e);
    }
  }

  vector<ai2> rocks;
  for (auto &e : mstEdges) {
    rocks.insert(rocks.end(), all(pathRocks[e.u][e.v]));
  }
  return pair{totalCost, rocks};
}

vector<ai2> precompute(vector<string> C) {
  rep(i, N) rep(j, N) {
    if (C[i][j] == 'A') {
      start_pos = {i, j};
      break;
    }
  }

  int min_cost = INF;
  vector<ai2> rocks_to_remove;

  // 穴から各 4 方向の岩を全除去するか否か，2^4 通り全探索
  rep(S, 16) {
    // 各岩を除去するコストを計算
    auto [c, cost_mat] = compute_dist(S);
    // 除去すべき岩を計算
    auto [c2, rocks] = compute_cost_rocks(cost_mat);

    // 下の係数の 2 はマジックナンバー．調整すべきかも
    int c3 = c + 2 * c2;

    if (chmin(min_cost, c3)) {
      swap(rocks_to_remove, rocks);
      rep(k, 4) if (S >> k & 1) {
        auto [di, dj] = dir[k];
        auto [i, j] = start_pos;
        while (true) {
          i += di;
          j += dj;
          if (i < 0 || i >= N || j < 0 || j >= N) break;
          if (C[i][j] == '@') rocks_to_remove.push_back({i, j});
        }
      }
    }
  }
  return rocks_to_remove;
}
}


void input() {
    int _; cin >> _;
    cin >> M;
    rep(i,0,N)rep(j,0,N) cin >> B[i][j];
    rep(i,0,N) rep(j,0,N) if(B[i][j] == 'A') sx = i, sy = j;
    // BをCに入れる
    rep(i,0,N) C[i].resize(N);
    rep(i,0,N)rep(j,0,N) C[i][j] = B[i][j];
}

string DIRS = "LURD";
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

bool is_valid(int x, int y){
    return 0 <= x && x < N && 0 <= y && y < N;
}

bool is_ore(char c){
    return c >= 'a' && c <= 'c';
}

// 各マスの各鉱石種類について距離
struct DistanceMap{
    int dist[3][N][N];
    void init(char B[N][N]){
        rep(i,0,N)rep(j,0,N) rep(k,0,3) dist[k][i][j] = INF;
        rep(i,0,3){
            // 'a'+iの鉱石までの距離をBFSで計算
            int gx = -1, gy = -1;
            rep(x,0,N)rep(y,0,N) if(B[x][y] == 'A'+i) gx = x, gy = y;
            if(gx == -1) continue;
            rep(x,0,N)rep(y,0,N) dist[i][x][y] = abs(x-gx) + abs(y-gy);
        }

        // C問題用
        int rock_cnt = 0; rep(i,0,N)rep(j,0,N) rock_cnt += B[i][j] == '@';
        if(rock_cnt >= N2 / 3){
            rep(i,0,N)rep(j,0,N) dist[0][i][j] = 999;
            // bfsで距離を埋める。Aだけ
            VV<bool> visited(N, V<bool>(N, false));
            queue<tuple<int, int, int>> q;
            q.push({sx, sy, 0});
            while(!q.empty()){
                auto [x, y, d] = q.front(); q.pop();
                if(visited[x][y]) continue;
                visited[x][y] = true;
                dist[0][x][y] = d;
                rep(k,0,4){
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if(!is_valid(nx, ny)) continue;
                    if(B[nx][ny] == '@') continue;
                    q.push({nx, ny, d+1});
                }
            }
        }
        // cerr distmap
        rep(i,0,N){
            rep(j,0,N){
                cerr << setw(3) << dist[0][i][j] << " ";
            }
            cerr << endl;
        }
    }
};

// 盤面に適当なHashを割り振る
struct BoardHash{
    ll hash[4][N][N];
    BoardHash(){
        // llの乱数生成気
        mt19937 mt(0);
        rep(i,0,4)rep(x,0,N)rep(y,0,N) hash[i][x][y] = mt();
    }
} board_hash;

struct OutputDebugger{
    void check(V<string> ans){
        // return ;
        char b[N][N];
        memcpy(b, B, sizeof(B));
        int cx = sx, cy = sy;
        rep(i,0,sz(ans)){
            string s = ans[i];
            // sをsplit
            int op = s[0] - '0';
            if(op == 1){
                char dir = s[2];
                if(dir == 'L') cy--;
                if(dir == 'U') cx--;
                if(dir == 'R') cy++;
                if(dir == 'D') cx++;
                assert(is_valid(cx, cy));
            }else if(op == 2){
                char dir_char = s[2];
                int dir = DIRS.find(dir_char);
                // move object
                int nx = cx + dx[dir];
                int ny = cy + dy[dir];
                assert(is_valid(nx, ny));
                char c = b[cx][cy];
                bool is_goal = (b[nx][ny] == 'A' + c - 'a');
                assert(b[nx][ny] == '.' || is_goal);
                b[cx][cy] = '.';
                if(!is_goal) b[nx][ny] = c;
                cx = nx, cy = ny;
            }else if(op == 3){
                char dir_char = s[2];
                int dir = DIRS.find(dir_char);
                // roll object
                int nx = cx, ny = cy;
                while(true){
                    int nnx = nx + dx[dir];
                    int nny = ny + dy[dir];
                    if(!is_valid(nnx, nny)){
                        break;
                    }
                    if(b[nnx][nny] == '@' || b[nnx][nny] >= 'a') break;
                    nx = nnx;
                    ny = nny;
                    if(b[nnx][nny] == 'A' || b[nnx][nny] == 'B' || b[nnx][nny] == 'C'){
                        nx = -1, ny = -1;
                        break;
                    }
                }
                if(nx >= 0){
                    assert(b[nx][ny] == '.');
                    char c = b[cx][cy];
                    b[cx][cy] = '.';
                    b[nx][ny] = c;
                }
                else{
                    b[cx][cy] = '.';
                }
            }
        }
    }
} output_debugger;

struct Operation{
    int x, y; // どの座標のオブジェクトを移動させるか
    int dir; // 0:L, 1:U, 2:R, 3:D
    bool is_roll; // 0:ひとマス移動, 1:転がす
};

struct State{
    char b[N][N];
    int cx, cy;
    Operation cur_op; // 今回の操作
    pair<int, int> prev_state; // 1つ前の状態. (ターン数, ビームの何番目に入れてるか)
    int cost = 0; // 全鉱石の穴までの距離の合計
    ll hash = 0;

    void debug_log_board(){
        rep(i,0,N){
            rep(j,0,N){
                cerr << b[i][j];
            }
            cerr << endl;
        }
    }

    bool operator<(const State &s) const {
        return cost < s.cost;
    }
};

struct BeamSearch{
    DistanceMap dmap;
    bool is_move_rock = true; // 岩もビムサで動かすか。C問題ではfalse想定. rockは'@'

    void output(int turn, State& state, V<State> beams[MaxT]){
        V<Operation> ops;
        V<State> states;
        while(true){
            ops.push_back(state.cur_op);
            states.push_back(state);
            if(state.prev_state.first == 0) break;
            state = beams[state.prev_state.first][state.prev_state.second];
        }
        reverse(all(ops));
        reverse(all(states));
        // for(auto state: states){
        //     state.debug_log_board();
        //     cerr << endl;
        // }

        V<string> ans;
        int cx = sx, cy = sy;
        for(auto& op: ops){
            // (op.x, op.y)に移動
            while(cx != op.x){
                cout << "1 " << (cx < op.x ? 'D' : 'U') << endl;
                ans.push_back("1 " + string(1, cx < op.x ? 'D' : 'U'));
                cx += (cx < op.x ? 1 : -1);
            }
            while(cy != op.y){
                cout << "1 " << (cy < op.y ? 'R' : 'L') << endl;
                ans.push_back("1 " + string(1, cy < op.y ? 'R' : 'L'));
                cy += (cy < op.y ? 1 : -1);
            }
            if(!op.is_roll){
                cout << "2 " << DIRS[op.dir] << endl;
                ans.push_back("2 " + string(1, DIRS[op.dir]));
                // charaも移動
                cx += dx[op.dir];
                cy += dy[op.dir];
            }else{
                cout << "3 " << DIRS[op.dir] << endl;
                ans.push_back("3 " + string(1, DIRS[op.dir]));
            }
        }
        cerr << "Score = " << turn << endl;
        output_debugger.check(ans);
    }

    State create_init_state(){
        State state;
        memcpy(state.b, B, sizeof(B));
        rep(i,0,N)rep(j,0,N) if(state.b[i][j] == 'A') state.cx = i, state.cy = j;
        
        // cost計算
        rep(i,0,N)rep(j,0,N) if(is_ore(state.b[i][j])){
            int ore_type = state.b[i][j] - 'a';
            state.cost += dmap.dist[ore_type][i][j];
            state.hash ^= board_hash.hash[ore_type][i][j];
        }
        rep(i,0,N)rep(j,0,N) if(state.b[i][j] == '@'){
            state.hash ^= board_hash.hash[3][i][j];
        }
        return state;
    }

    void run(){
        dmap.init(B);

        State init_state = create_init_state();
        is_move_rock = problem_type == 3;
        unordered_set<ll> hashes;
        static priority_queue<State> beams[MaxT];
        static V<State> caches[MaxT];

        State best_state = init_state;
        int best_cost = init_state.cost;
        int best_turn = 0;
        
        int beam_width = 80;
        beams[0].push(init_state);
        hashes.insert(init_state.hash);

        rep(t,0,MaxT){
            if(t%10 == 0) cerr << "t: " << t << " beams: " << beams[t].size() << endl;
            if(t > 1000){
                cerr << "t: " << t << " beams: " << beams[t].size() << endl;

            }
            if(beams[t].empty()) continue;
            while(!beams[t].empty()){
                caches[t].push_back(beams[t].top());
                beams[t].pop();
            }
            reverse(all(caches[t]));
            if(caches[t][0].cost == 0){
                // 全て穴に落ちたので終了
                output(t, caches[t][0], caches);
                return;
            }
            if(chmin(best_cost, caches[t][0].cost)){
                best_state = caches[t][0];
                best_turn = t;
            }

            // 次のビームを生成
            rep(si,0,min(beam_width, sz(caches[t]))){
                auto& state = caches[t][si];
                // 全ての鉱石について、8通りの操作を試す(is_move_rockなら、岩も操作対象)
                rep(i,0,N)rep(j,0,N){
                    char c = state.b[i][j];
                    int ore_type = c - 'a';
                    char goal_char = 'A' + ore_type;
                    bool is_rock = c == '@';
                    if(is_move_rock){
                        if(!is_rock && c < 'D') continue;
                    }else{
                        if(c < 'D') continue;
                    }
                    
                    int chara_move_turn = abs(i-state.cx) + abs(j-state.cy);
                    int next_turn = t + chara_move_turn + 1; // Objectを動かすのにかかるコスト=1
                    if(next_turn >= MaxT) continue;
                    rep(dir,0,4){
                        int nx = i + dx[dir];
                        int ny = j + dy[dir];
                        // 盤面外に出るならスキップ
                        // TODO: 岩は落としても良いので要対応。ただ、一旦この操作を無しにしても、さほど影響がないため、実装を楽にするためまずは無しで。
                        if(!is_valid(nx, ny)) continue;
                        // 1マスも動けない場合はスキップ
                        if(state.b[nx][ny] == '@' || state.b[nx][ny] >= 'a') continue; 
                        // 異なるゴールに落ちる場合もスキップ
                        if(state.b[nx][ny] != '.' && state.b[nx][ny] != goal_char) continue;

                        rep(op_type,0,2){ // 0:ひとマス移動, 1:転がす
                            // next_stateを生成する前に、実際に操作を行った後の状態をシミュレートして、コストを計算。棄却されるなら、next_stateを生成しない。
                            int next_cost;
                            // オブジェクトがどこに移動するか。転がす場合だけ更新する。
                            int mx = nx, my = ny;
                            if(op_type == 0){
                                // 1マス動かす
                                next_cost = is_rock ? state.cost : state.cost - dmap.dist[ore_type][i][j] + dmap.dist[ore_type][nx][ny];
                                if(beams[next_turn].size() >= beam_width && next_cost >= beams[next_turn].top().cost) continue;
                            }else{
                                // 転がす
                                // 鉱石が異なる穴or盤面外に落ちたらNG
                                if(state.b[nx][ny] == goal_char) continue;
                                bool is_ok = true;
                                while(true){
                                    int nnx = mx + dx[dir];
                                    int nny = my + dy[dir];
                                    if(!is_valid(nnx, nny)){
                                        break;
                                    }
                                    if(state.b[nnx][nny] == '@' || state.b[nnx][nny] >= 'a') break;
                                    mx = nnx;
                                    my = nny;
                                    if(state.b[nnx][nny] == goal_char) break;
                                    if(state.b[nnx][nny] != '.' && state.b[nnx][nny] != goal_char){
                                        mx = -1, my = -1;
                                        is_ok = false;
                                        break;
                                    }
                                }
                                if(!is_ok) continue;
                                next_cost = is_rock ? state.cost : state.cost - dmap.dist[ore_type][i][j] + dmap.dist[ore_type][mx][my];
                                if(beams[next_turn].size() >= beam_width && next_cost >= beams[next_turn].top().cost) continue;
                            }

                            ll next_hash = state.hash;
                            int hash_type = is_rock ? 3 : ore_type;
                            next_hash ^= board_hash.hash[hash_type][i][j];
                            if(mx >= 0) next_hash ^= board_hash.hash[hash_type][mx][my];
                            if(hashes.count(next_hash)) continue;
                            hashes.insert(next_hash);

                            State next_state = state;
                            next_state.hash = next_hash;
                            next_state.cur_op = {i, j, dir, op_type == 1};
                            next_state.prev_state = {t, si};
                            next_state.cost = next_cost;
                            next_state.b[i][j] = '.';
                            // ひとマス移動の場合は自分も動く
                            next_state.cx = op_type == 0 ? nx : i;
                            next_state.cy = op_type == 0 ? ny : j;
                            // NOTE: 盤面外に出たことを(-1,-1)で表現してあるので、mx >= 0 だけで判定してる
                            if(mx >= 0 && next_state.b[mx][my] != goal_char){
                                next_state.b[mx][my] = c;
                            }
                            beams[t+chara_move_turn+1].push(next_state);
                            if(beams[t+chara_move_turn+1].size() > beam_width)
                                beams[t+chara_move_turn+1].pop();
                        }
                    }
                }
            }
        }

        // クリア出来なかった
        cerr << "Failed to clear" << endl;
        output(MaxT, best_state, caches);
        assert(0);
    }
};

struct Solver{
    void check_probrem_type(){
        int rock_cnt = 0;
        rep(i,0,N)rep(j,0,N) rock_cnt += B[i][j] == '@';
        set<int> ore_set;
        rep(i,0,N)rep(j,0,N) if(is_ore(B[i][j])) ore_set.insert(B[i][j]);
        int ore_cnt = sz(ore_set);
        problem_type = 1;
        if(ore_cnt == 3) problem_type = 2;
        if(rock_cnt >= N2 / 3) problem_type = 3;
    }

    void run(){
        auto replaces = opt::precompute(C);
        for(auto [x, y]: replaces){
            B[x][y] = 'a';
        }
        BeamSearch beam_search;
        beam_search.run();
    }
};

int main() {
#if DEBUG
    freopen("tools/inC/0011.txt", "r", stdin);
#endif
    input();

    Solver solver;
    solver.run();
}

提出情報

コンパイルエラー

Main.cpp: In member function ‘void BeamSearch::run()’:
Main.cpp:859:60: warning: comparison of integer expressions of different signedness: ‘std::priority_queue<State>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  859 |                                 if(beams[next_turn].size() >= beam_width && next_cost >= beams[next_turn].top().cost) continue;
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
Main.cpp:883:60: warning: comparison of integer expressions of different signedness: ‘std::priority_queue<State>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  883 |                                 if(beams[next_turn].size() >= beam_width && next_cost >= beams[next_turn].top().cost) continue;
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
Main.cpp:907:66: warning: comparison of integer expressions of different signedness: ‘std::priority_queue<State>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  907 |                             if(beams[t+chara_move_turn+1].size() > beam_width)
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
Main.cpp:794:13: warning: variable ‘best_turn’ set but not used [-Wunused-but-set-variable]
  794 |         int best_turn = 0;
      |             ^~~~~~~~~

ジャッジ結果