提出 #63337972

---

ソースコード 拡げる

#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;
}
}  // namespace opt

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] = round(100 * pow(abs(x - gx) + abs(y - gy), 0.6));
        }

        // 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;
    int rock_dist = 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 {
        if (cost != s.cost)
            return cost < s.cost;
        else
            return rock_dist > s.rock_dist;
    }
};

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];
            state.rock_dist += dmap.dist[0][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 = 60;
        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 next_rock_dist = state.rock_dist;
                            // オブジェクトがどこに移動するか。転がす場合だけ更新する。
                            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 (is_rock) next_rock_dist = state.rock_dist - dmap.dist[0][i][j] + dmap.dist[0][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 (is_rock) next_rock_dist = state.rock_dist - dmap.dist[0][i][j] + dmap.dist[0][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.rock_dist = next_rock_dist;
                            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);
    }
};

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:866:61: warning: comparison of integer expressions of different signedness: ‘std::priority_queue<State>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  866 |                                 if (beams[next_turn].size() >= beam_width && next_cost >= beams[next_turn].top().cost) continue;
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
Main.cpp:891:61: warning: comparison of integer expressions of different signedness: ‘std::priority_queue<State>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  891 |                                 if (beams[next_turn].size() >= beam_width && next_cost >= beams[next_turn].top().cost) continue;
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
Main.cpp:916:71: warning: comparison of integer expressions of different signedness: ‘std::priority_queue<State>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  916 |                             if (beams[t + chara_move_turn + 1].size() > beam_width)
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
Main.cpp:800:13: warning: variable ‘best_turn’ set but not used [-Wunused-but-set-variable]
  800 |         int best_turn = 0;
      |             ^~~~~~~~~

ジャッジ結果