提出 #65212525

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

/* ---- 型エイリアス ---- */
using ull = unsigned long long; using ll = long long;
using vi = vector<int>;  using vl = vector<long long>;
using pii = pair<int,int>; using pll = pair<ll,ll>;

/* ---- 定数 ---- */
constexpr int N = 20, M_FIXED = 40;
int MAX_TURN = 2*N*M_FIXED;
int BEAM_WIDTH = 6000;

constexpr double ALPHA = 0.2, BETA = 50.0, GAMMA = 0.8;
const int DX[4]={-1,1,0,0}, DY[4]={0,0,-1,1};
const char DC[4]={'U','D','L','R'};
inline bool inside(int x,int y){ return 0<=x && x<N && 0<=y && y<N; }

/* ---- 壁を 1 行 = 20bit の uint32_t に圧縮 ---- */
using Wall = array<uint32_t,N>;      // bit==1 ならブロック

inline bool is_wall(const Wall& w,int x,int y){ return (w[x]>>y)&1u; }
inline void toggle_wall(Wall& w,int x,int y){ w[x] ^= (1u<<y); }


/* ---------- 状態 ---------- */
struct State{
    Wall wall;
    int x,y;                // 現在位置
    int goal;               // 次ゴール index
    double score;
    vector<char> act;       // 行動列
};

/* ---------- 1 手展開 ---------- */
inline int manh(int x,int y,int gx,int gy){
    return abs(x-gx) + abs(y-gy);
}
/* ---------- 1 手展開（マンハッタン評価版） ---------- */
void expand(const State& st,const vector<pii>& goals,
            vector<State>& buf)
{
    
    const int gx = st.x, gy = st.y;
    const pii gnow = goals[st.goal];

    // --- ① 向きの決定（ゴールへの主方向） ---
    int dxG = gnow.first  - gx;
    int dyG = gnow.second - gy;
    int forwardDir;
    if(abs(dxG) > abs(dyG)){
        forwardDir = (dxG > 0 ? 1 /*D*/ : 0 /*U*/);
    } else {
        forwardDir = (dyG > 0 ? 3 /*R*/ : 2 /*L*/);
    }

    const int d_here = manh(gx, gy, gnow.first, gnow.second);

    /* ---- Move / Slide ---- */
    for(int dir=0; dir<4; ++dir){
        /* ---------- Move ---------- */
        int mx = gx + DX[dir], my = gy + DY[dir];
        if(inside(mx,my) && !is_wall(st.wall,mx,my)){
            State nx = st; nx.x = mx; nx.y = my;

            int d_next = manh(mx,my, gnow.first, gnow.second);
            bool reach = (d_next == 0);

            double sc = (d_here - d_next) + (reach ? BETA : 0);
            nx.score += sc;
            if(reach) ++nx.goal;

            nx.act.push_back('M'); nx.act.push_back(DC[dir]);
            buf.emplace_back(move(nx));
        }

        /* ---------- Slide ---------- */
        int sx=gx, sy=gy;
        while(true){
            int tx=sx+DX[dir], ty=sy+DY[dir];
            if(!inside(tx,ty) || is_wall(st.wall,tx,ty)) break;
            sx=tx; sy=ty;
        }
        if(sx!=gx || sy!=gy){
            State nx = st; nx.x = sx; nx.y = sy;

            int d_next = manh(sx,sy, gnow.first, gnow.second);
            bool reach = (d_next == 0);

            double sc = (d_here - d_next) + (reach ? BETA : 0);
            nx.score += sc;
            if(reach) ++nx.goal;

            nx.act.push_back('S'); nx.act.push_back(DC[dir]);
            buf.emplace_back(move(nx));
        }
    }

      /* ---- Toggle（新しい周辺／行列ペナルティ付き評価） ---- */
    constexpr int    R_CHECK           = 3;      // 周辺チェック距離
    constexpr double BONUS_NO_NEAR     = 5.0;    // 周辺にブロック無しで加点
    constexpr double PENALTY_NEAR      = 3.0;    // 周辺にブロックありで減点
    constexpr double PENALTY_ROWCOL    = 2.0;    // 同行／同列にブロックありで減点

 for(int dir=0; dir<4; ++dir){
    int cx = gx + DX[dir], cy = gy + DY[dir];
    if(!inside(cx,cy)) continue;

    bool wasWall = is_wall(st.wall, cx, cy);

    // ─── 未来のゴールへの設置を禁止 ───
    if(!wasWall){
        bool isFutureTarget = false;
        for(int k = st.goal; k < (int)goals.size(); ++k){
            if(goals[k].first == cx && goals[k].second == cy){
                isFutureTarget = true;
                break;
            }
        }
        if(isFutureTarget) continue;  // 置く操作をスキップ
    }

    State nx = st;
    toggle_wall(nx.wall, cx, cy);

    // １ターン消費分のコスト
    double sc = -1.0;

    // ① 周辺チェック...
    bool anyNear = false;
    for(int dx=-R_CHECK; dx<=R_CHECK && !anyNear; ++dx){
        for(int dy=-(R_CHECK-abs(dx)); dy<=(R_CHECK-abs(dx)); ++dy){
            int x2 = cx + dx, y2 = cy + dy;
            if(!inside(x2,y2)) continue;
            if(is_wall(st.wall, x2, y2)){
                anyNear = true;
                break;
            }
        }
    }
    if(!anyNear)       sc += BONUS_NO_NEAR;
    else               sc -= PENALTY_NEAR;

    // ② 行列チェック...
    bool blockRowCol = false;
    for(int y2=0; y2<N; ++y2){
        if(y2!=cy && is_wall(st.wall, cx, y2)){
            blockRowCol = true; break;
        }
    }
    if(!blockRowCol){
        for(int x2=0; x2<N; ++x2){
            if(x2!=cx && is_wall(st.wall, x2, cy)){
                blockRowCol = true; break;
            }
        }
    }
    if(blockRowCol) sc -= PENALTY_ROWCOL;

    // 枝刈り
    if(sc < -0.5) continue;

    // スコア反映＆アクション登録
    nx.score += sc;
    nx.act.push_back('A');
    nx.act.push_back(DC[dir]);
    buf.emplace_back(move(nx));
}
}

/* ========================================================= */
int main(int argc,char* argv[]){
    bool debug = true;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    /* ---- 入力 ---- */
    int n, M;                // n = 20, M = 40
    cin >> n >> M;
    if(argc >= 2) BEAM_WIDTH = max(1, stoi(argv[1]));

    int sx, sy;              // 初期位置
    cin >> sx >> sy;

    vector<pii> goals(M-1);
    for(auto& g : goals) cin >> g.first >> g.second;

    /* ---- 初期状態 ---- */
    State init;
    init.wall.fill(0u);
    init.x = sx;  init.y = sy;
    init.goal = 0;
    init.score = 0.0;

    /* ------------- 省略: すべての前半部分は元コードと同じ ------------- */

    vector<State> beam{init}, nxt;
    beam.reserve(BEAM_WIDTH);
    nxt.reserve(BEAM_WIDTH * 12);   // 1 手で最大 12 分岐

    for(int turn = 0; turn < MAX_TURN && !beam.empty(); ++turn){
        /* --- 動的ビーム幅調整をここで実行 --- */
        if(turn == 400)  BEAM_WIDTH = max(1, BEAM_WIDTH / 2);
        if(turn == 1000) BEAM_WIDTH = max(1, BEAM_WIDTH / 4);

        nxt.clear();
        for(const State& st : beam){
            if(st.goal == M-1){               // すでに全ゴール達成
                nxt.push_back(st);
                continue;
            }
            /* ---- 1 手展開（マンハッタン評価版） ---- */
            expand(st, goals, nxt);
        }

        /* ---- ビーム選択 ---- */
        int keep = min(BEAM_WIDTH, (int)nxt.size());
        partial_sort(nxt.begin(), nxt.begin() + keep, nxt.end(),
                     [](const State& a, const State& b){ return a.score > b.score; });
        nxt.resize(keep);
        beam.swap(nxt);

        if(beam[0].goal == M-1) break;        // 早期終了
    }

    /* ---- 出力 ---- */
    const State& best = beam[0];
    for(size_t i = 0; i + 1 < best.act.size(); i += 2){
        cout << best.act[i] << ' ' << best.act[i + 1] << '\n';
    }
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘void expand(const State&, const std::vector<std::pair<int, int> >&, std::vector<State>&)’:
Main.cpp:50:9: warning: variable ‘forwardDir’ set but not used [-Wunused-but-set-variable]
   50 |     int forwardDir;
      |         ^~~~~~~~~~
Main.cpp: In function ‘int main(int, char**)’:
Main.cpp:173:10: warning: unused variable ‘debug’ [-Wunused-variable]
  173 |     bool debug = true;
      |          ^~~~~

ジャッジ結果