Submission #73749020

---

Source Code Expand

/*
 * solver_c.cpp - Problem C solver
 *
 * ── 問題設定 ──────────────────────────────────────────────
 *   N=20, AK=1000, AM=1, AW=1000 (壁コスト高 → 壁0枚)
 *   目標: 1台のロボット × 少ない状態数M で全400セルを巡回
 *   スコア = 1 + 1e6 * log2(base / V),  V = AK*(K-1) + AM*M
 *   → K=1, M小 が最高スコア。M=4で16,607,476, M=8で15,607,476
 *
 * ── 改善の道のり ──────────────────────────────────────────
 *   v1: SA + fallback (spinner robots)
 *       → Pass=~50/100, Avg=9.1M
 *       ボトルネック: SA探索空間が広すぎ、良い初期解がないと収束しない
 *
 *   v2: SA前にビームサーチ挿入 (M+1状態を系統的に探索)
 *       → Pass=43/100, SAの時間が減って逆効果
 *
 *   v3: SA廃止、ビームサーチ一本化
 *       → ビームサーチの候補数が爆発 (3×M×2×M per attachment)
 *       → M=6以降に到達できず Pass=43
 *
 *   v4: 単一位置評価 (17倍高速化)
 *       try_candでseedの最良位置1箇所だけsimulate → top候補のみfull eval
 *       → M=8まで到達可能に。Pass=53
 *
 *   v5: シードパターン多様化 (PatA/B/C/D)
 *       A: {0,2}=F, {1,3}=turn  B: {0,3}=F, {1,2}=turn
 *       C: {0,1}=F, {2,3}=turn  D: {1,2}=F, {0,3}=turn
 *       → Pass=61, Avg=11.9M
 *
 *   v6: チームメイトのv9_cからハードコードシード導入
 *       8種ジグザグ(M=4) + 壁追従(M=4) + ゴールデンパターン(M=5,6)
 *       事前検証済みの高品質パターンをfull evalしてシードに
 *       → Pass=94, Avg=15.8M  ← 現在
 *
 * ── 現在のアーキテクチャ ──────────────────────────────────
 *   Phase 0: ハードコードシード (14パターン × 全1600開始位置)  ~0.16s
 *   Phase 1: パターン列挙 (A/B/C/D) M=4シード生成              ~0.30s
 *   Phase 2: ビームサーチ M=5→8
 *            - 各レベルで親シードの遷移1本を新状態に繋ぎ替え
 *            - 新状態の(a0,b0,a1,b1)を全列挙
 *            - 単一位置評価で高速フィルタ → top-50 → top-20 full eval
 *            - ビーム幅: M=5:60, M=6:50, M=7:35, M=8:20          ~1.40s
 *   Fallback: best partial + 未カバーセルにspinner robot (M=1回転)
 *
 * ── 残課題 ────────────────────────────────────────────────
 *   - 6/100ケースがフォールバック (5件はuncov=1-2, 1件はuncov=20)
 *   - 乱数シード変更やSA追加で拾える可能性あり
 *   - ビームサーチの評価関数に距離ペナルティ導入で改善余地
 */

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
using namespace std;

const int N = 20;                           // グリッドサイズ (Problem Cは常に20)
const int DI[] = {-1, 0, 1, 0};             // 方向: U=0, R=1, D=2, L=3
const int DJ[] = {0, 1, 0, -1};
const char DIR_CH[] = {'U', 'R', 'D', 'L'};
const char* ACT_STR[] = {"F", "R", "L"};    // アクション: 0=前進, 1=右回転, 2=左回転

int wall_v[N][N], wall_h[N][N];

auto t0 = chrono::steady_clock::now();
double elapsed() {
    return chrono::duration<double>(chrono::steady_clock::now() - t0).count();
}

inline bool has_wall(int r, int c, int d) {
    if (d == 0) return r == 0 || wall_h[r-1][c];
    if (d == 2) return r == N-1 || wall_h[r][c];
    if (d == 1) return c == N-1 || wall_v[r][c];
    return c == 0 || wall_v[r][c-1];
}

// オートマトン: M状態、各状態sに対し
//   壁なし: アクション a0[s], 遷移先 b0[s]
//   壁あり: アクション a1[s], 遷移先 b1[s]
// 最大8状態 (M=4のジグザグ → ビームでM=8まで拡張)
struct Automaton {
    int M;
    int a0[8], b0[8];  // no-wall: action, next_state
    int a1[8], b1[8];  // wall:    action, next_state
};

// サイクル検出用の世代管理配列 (simulate/simulate_cellsで共用)
// キー: (row*N+col)*4+dir)*M+state → 最大 20*20*4*8 = 12800
static int g_fv_gen[N * N * 4 * 8];  // 訪問世代
static int g_fv_val[N * N * 4 * 8];  // 訪問ステップ番号
static int g_gen = 0;                // 現在の世代 (毎simulate呼び出しでインクリメント)

// シミュレーション: 開始位置(si,sj,sd)からサイクルに入るまで実行し、
// サイクル内で訪問するユニークセル数を返す。~2μs/call
int simulate(const Automaton& aut, int si, int sj, int sd) {
    g_gen++;
    int m = aut.M;
    int r = si, c = sj, d = sd, s = 0;
    int max_steps = N * N * 4 * m;
    for (int step = 0; step <= max_steps; step++) {
        int enc = ((r * N + c) * 4 + d) * m + s;
        if (g_fv_gen[enc] == g_gen) {
            int cycle_start = g_fv_val[enc];
            bool seen[N][N] = {};
            int cnt = 0;
            int r2 = si, c2 = sj, d2 = sd, s2 = 0;
            for (int t = 0; t < step; t++) {
                if (t >= cycle_start && !seen[r2][c2]) { seen[r2][c2] = true; cnt++; }
                bool w = has_wall(r2, c2, d2);
                int act = w ? aut.a1[s2] : aut.a0[s2];
                int nxt = w ? aut.b1[s2] : aut.b0[s2];
                if (act == 0) { r2 += DI[d2]; c2 += DJ[d2]; }
                else if (act == 1) d2 = (d2 + 1) % 4;
                else d2 = (d2 + 3) % 4;
                s2 = nxt;
            }
            return cnt;
        }
        g_fv_gen[enc] = g_gen;
        g_fv_val[enc] = step;
        bool w = has_wall(r, c, d);
        int act = w ? aut.a1[s] : aut.a0[s];
        int nxt = w ? aut.b1[s] : aut.b0[s];
        if (act == 0) { r += DI[d]; c += DJ[d]; }
        else if (act == 1) d = (d + 1) % 4;
        else d = (d + 3) % 4;
        s = nxt;
    }
    return 0;
}

// カバーセル取得: サイクル内で訪問するセルをcovered[][]に記録 (フォールバック用)
void simulate_cells(const Automaton& aut, int si, int sj, int sd, bool covered[N][N]) {
    g_gen++;
    memset(covered, 0, sizeof(bool)*N*N);
    int m = aut.M;
    int r = si, c = sj, d = sd, s = 0;
    int max_steps = N * N * 4 * m;
    for (int step = 0; step <= max_steps; step++) {
        int enc = ((r * N + c) * 4 + d) * m + s;
        if (g_fv_gen[enc] == g_gen) {
            int cycle_start = g_fv_val[enc];
            int r2 = si, c2 = sj, d2 = sd, s2 = 0;
            for (int t = 0; t < step; t++) {
                if (t >= cycle_start) covered[r2][c2] = true;
                bool w = has_wall(r2, c2, d2);
                int act = w ? aut.a1[s2] : aut.a0[s2];
                int nxt = w ? aut.b1[s2] : aut.b0[s2];
                if (act == 0) { r2 += DI[d2]; c2 += DJ[d2]; }
                else if (act == 1) d2 = (d2 + 1) % 4;
                else d2 = (d2 + 3) % 4;
                s2 = nxt;
            }
            return;
        }
        g_fv_gen[enc] = g_gen;
        g_fv_val[enc] = step;
        bool w = has_wall(r, c, d);
        int act = w ? aut.a1[s] : aut.a0[s];
        int nxt = w ? aut.b1[s] : aut.b0[s];
        if (act == 0) { r += DI[d]; c += DJ[d]; }
        else if (act == 1) d = (d + 1) % 4;
        else d = (d + 3) % 4;
        s = nxt;
    }
}

struct Result { int cov, si, sj, sd; };

// 全1600開始位置 (20×20×4方向) を試して最良カバレッジを返す。~3.2ms/call
Result best_start(const Automaton& aut) {
    Result best = {0, 0, 0, 0};
    for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
    for (int d = 0; d < 4; d++) {
        int c = simulate(aut, i, j, d);
        if (c > best.cov) { best = {c, i, j, d}; if (c == N*N) return best; }
    }
    return best;
}

// 候補: オートマトン + そのベスト開始位置でのカバレッジ
struct Cand { Automaton aut; int cov, si, sj, sd; };

int main() {
    int n, ak, am, aw;
    scanf("%d%d%d%d", &n, &ak, &am, &aw);
    fprintf(stderr, "N=%d AK=%d AM=%d AW=%d\n", n, ak, am, aw);

    for (int i = 0; i < N; i++) {
        char s[32]; scanf("%s", s);
        for (int j = 0; j < N-1; j++) wall_v[i][j] = s[j] - '0';
    }
    for (int i = 0; i < N-1; i++) {
        char s[32]; scanf("%s", s);
        for (int j = 0; j < N; j++) wall_h[i][j] = s[j] - '0';
    }
    t0 = chrono::steady_clock::now();
    mt19937 rng(42);

    Cand global_best = {{}, 0, 0, 0, 0};
    vector<Cand> top_seeds;

    // ビームサーチ用: seedの最良位置1箇所だけでsimulate (高速、~2μs)
    // seed.cov-10以上なら候補に追加。full evalはバッチで後からやる
    auto try_cand = [&](Automaton& ext, const Cand& seed, vector<Cand>& cands) -> bool {
        int q = simulate(ext, seed.si, seed.sj, seed.sd);
        if (q >= seed.cov - 10)
            cands.push_back({ext, q, seed.si, seed.sj, seed.sd});
        return false; // never short-circuit; batch full-eval at end
    };

    // シード列挙用: 粗いグリッド (5刻み×4方向=64点) で評価
    // cov≥80ならシード追加、global_bestより良ければfull eval
    auto try_seed = [&](Automaton a) -> bool {
        int q = simulate(a, 0, 0, 1);
        if (q < 50) return false;
        int best_q = q; int bi=0, bj=0, bd=1;
        for (int pi = 0; pi < N; pi += 5)
        for (int pj = 0; pj < N; pj += 5)
        for (int pd = 0; pd < 4; pd++) {
            int c = simulate(a, pi, pj, pd);
            if (c > best_q) { best_q = c; bi=pi; bj=pj; bd=pd; }
        }
        if (best_q >= 80)
            top_seeds.push_back({a, best_q, bi, bj, bd});
        if (best_q > global_best.cov) {
            auto res = best_start(a);
            if (res.cov > global_best.cov)
                global_best = {a, res.cov, res.si, res.sj, res.sd};
            if (res.cov == N*N) return true;
        }
        return false;
    };

    // ============================================================
    // Phase 0: ハードコードシード (チームメイトv9_cから)
    //   事前検証済みの高品質パターンをfull eval (全1600位置)
    //   27パターン × 3.2ms = ~0.09s。大半のケースはここで解決
    // ============================================================
    {
        // 21 unique automata mined from 94/100 successful runs on inC/0000-0099
        // + wall followers + v9_c templates. Sorted by M.
        Automaton hc_all[] = {
            // M=4: 7 patterns (5 zigzag classes + 2 wall followers)
            {4, {0,2,0,1}, {1,2,3,0}, {1,2,1,2}, {0,0,2,2}},  // zigzag class 1
            {4, {0,2,0,1}, {1,2,3,0}, {2,2,1,1}, {2,0,2,0}},  // zigzag class 2
            {4, {0,2,1,0}, {2,0,3,1}, {1,2,1,2}, {3,3,0,0}},  // zigzag class 3
            {4, {0,1,0,2}, {1,2,3,0}, {2,1,2,1}, {0,0,2,2}},  // mirror 1
            {4, {0,1,0,2}, {1,2,3,0}, {1,1,2,2}, {2,0,2,0}},  // mirror 2
            {4, {1,0,0,0}, {1,0,0,0}, {1,2,2,2}, {1,2,3,0}},  // right wall follower
            {4, {2,0,0,0}, {1,0,0,0}, {2,1,1,1}, {1,2,3,0}},  // left wall follower
            // M=5: 10 patterns (beam search discoveries)
            {5, {0,2,0,1,1,0,0,0}, {1,2,3,0,1,0,0,0}, {2,2,1,1,1,0,0,0}, {2,0,4,0,2,0,0,0}},
            {5, {0,1,0,2,2,0,0,0}, {1,2,3,0,1,0,0,0}, {1,1,2,2,2,0,0,0}, {2,0,4,0,2,0,0,0}},
            {5, {0,2,0,1,1,0,0,0}, {1,2,3,0,1,0,0,0}, {2,2,1,1,1,0,0,0}, {2,0,4,0,1,0,0,0}},
            {5, {0,1,0,2,2,0,0,0}, {1,2,3,0,4,0,0,0}, {2,1,2,1,2,0,0,0}, {4,0,2,2,0,0,0,0}},
            {5, {0,1,0,2,2,0,0,0}, {1,2,3,0,1,0,0,0}, {1,1,2,2,2,0,0,0}, {2,0,4,0,1,0,0,0}},
            {5, {0,2,1,0,2,0,0,0}, {2,0,3,1,4,0,0,0}, {1,2,1,2,2,0,0,0}, {3,4,0,0,3,0,0,0}},
            {5, {0,1,0,2,2,0,0,0}, {1,2,3,0,1,0,0,0}, {1,1,2,2,2,0,0,0}, {2,0,4,0,4,0,0,0}},
            {5, {0,2,0,1,1,0,0,0}, {1,2,3,0,1,0,0,0}, {2,2,1,1,1,0,0,0}, {2,0,4,0,4,0,0,0}},
            {5, {0,2,0,1,2,0,0,0}, {1,2,3,0,4,0,0,0}, {1,2,1,2,2,0,0,0}, {0,0,2,4,2,0,0,0}},
            {5, {0,2,0,1,0,0,0,0}, {1,2,3,0,2,0,0,0}, {2,2,1,1,2,0,0,0}, {4,0,2,0,2,0,0,0}},
            // M=6: 5 patterns (golden patterns + beam discoveries)
            {6, {0,2,0,1,1,0,0,0}, {1,2,3,0,5,5,0,0}, {1,2,1,2,1,1,0,0}, {4,0,2,2,5,0,0,0}},
            {6, {0,1,0,2,2,0,0,0}, {1,2,3,0,5,5,0,0}, {2,1,2,1,2,2,0,0}, {4,0,2,2,5,0,0,0}},
            {6, {0,1,0,2,0,1,0,0}, {1,2,3,0,5,4,0,0}, {2,1,2,1,2,1,0,0}, {0,4,2,2,4,0,0,0}},
            {6, {0,2,1,0,1,1,0,0}, {2,0,3,1,4,5,0,0}, {1,2,1,2,1,1,0,0}, {4,3,5,0,3,0,0,0}},
            {6, {0,2,1,0,1,2,0,0}, {2,0,3,1,4,5,0,0}, {1,2,1,2,1,2,0,0}, {4,3,0,5,3,0,0,0}},
            // M=7: 2 patterns
            {7, {0,2,0,1,1,0,2,0}, {1,2,3,0,5,5,6,0}, {1,2,1,2,1,1,2,0}, {4,0,2,6,5,0,2,0}},
            {7, {0,2,0,1,1,0,2,0}, {1,2,3,0,5,5,6,0}, {1,2,1,2,1,1,2,0}, {4,6,2,2,5,0,0,0}},  // from 0016
        };
        // Also keep v9_c templates not already in mined set
        Automaton hc_extra[] = {
            {4, {0,1,2,0}, {2,0,3,1}, {2,1,2,1}, {3,3,0,0}},  // mirror 3
            {4, {0,2,1,0}, {2,0,3,1}, {2,1,2,1}, {3,3,0,0}},  // wall swap 1
            {4, {0,2,1,0}, {2,0,3,1}, {1,2,1,2}, {0,0,0,0}},  // wall swap 2
            {5, {0,1,0,2,1,0,0,0}, {1,2,3,0,4,0,0,0}, {2,1,2,1,1,0,0,0}, {0,0,2,4,2,0,0,0}},
        };

        auto full_seed = [&](Automaton& a) {
            auto res = best_start(a);
            if (res.cov >= 50) {
                top_seeds.push_back({a, res.cov, res.si, res.sj, res.sd});
                if (res.cov > global_best.cov)
                    global_best = {a, res.cov, res.si, res.sj, res.sd};
            }
            return res.cov == N*N;
        };

        for (auto& a : hc_all)   if (full_seed(a)) { fprintf(stderr, "HC found! M=%d\n", a.M); goto output; }
        for (auto& a : hc_extra) if (full_seed(a)) { fprintf(stderr, "HC extra found! M=%d\n", a.M); goto output; }
        fprintf(stderr, "[%.2fs] Hardcoded seeds: %d added, best=%d\n",
                elapsed(), (int)top_seeds.size(), global_best.cov);

    }

    // ============================================================
    // Phase 1: パターン列挙でM=4シード生成
    //   4つのF位置パターン (A/B/C/D) × 壁遷移全列挙
    //   時間制限付き (各パターン0.05-0.10s)
    //   ハードコードで拾えなかったケース用の多様なシード確保
    // ============================================================

    // Pattern A: state {0,2}=前進, {1,3}=回転。古典的ジグザグ型
    {
        int cnt = 0;
        for (int t1 = 1; t1 <= 2; t1++)
        for (int t3 = 1; t3 <= 2; t3++)
        for (int b00 : {1,3}) for (int b01 : {0,2})
        for (int b02 : {1,3}) for (int b03 : {0,2})
        for (int w0 = 1; w0 <= 2; w0++) for (int w1 = 1; w1 <= 2; w1++)
        for (int w2 = 1; w2 <= 2; w2++) for (int w3 = 1; w3 <= 2; w3++)
        for (int wb0 : {0,1,2,3}) for (int wb1 : {0,1,2,3})
        for (int wb2 : {0,1,2,3}) for (int wb3 : {0,1,2,3}) {
            cnt++;
            Automaton a = {4, {0,t1,0,t3}, {b00,b01,b02,b03},
                              {w0,w1,w2,w3}, {wb0,wb1,wb2,wb3}};
            if (try_seed(a) && global_best.cov == N*N) {
                fprintf(stderr, "[%.2fs] Seed full coverage M=4 (patA)!\n", elapsed());
                goto output;
            }
            if (elapsed() > 0.10) goto patA_done;
        }
        patA_done:
        fprintf(stderr, "[%.2fs] PatA: %d enumerated\n", elapsed(), cnt);
    }

    // Pattern B: state {0,3}=前進, {1,2}=回転。交差配線型
    {
        int cnt = 0;
        for (int t1 = 1; t1 <= 2; t1++)
        for (int t2 = 1; t2 <= 2; t2++)
        for (int b00 : {1,2}) for (int b01 : {0,3})
        for (int b02 : {0,3}) for (int b03 : {1,2})
        for (int w0 = 1; w0 <= 2; w0++) for (int w1 = 1; w1 <= 2; w1++)
        for (int w2 = 1; w2 <= 2; w2++) for (int w3 = 1; w3 <= 2; w3++)
        for (int wb0 : {0,1,2,3}) for (int wb1 : {0,1,2,3})
        for (int wb2 : {0,1,2,3}) for (int wb3 : {0,1,2,3}) {
            cnt++;
            Automaton a = {4, {0,t1,t2,0}, {b00,b01,b02,b03},
                              {w0,w1,w2,w3}, {wb0,wb1,wb2,wb3}};
            if (try_seed(a) && global_best.cov == N*N) {
                fprintf(stderr, "[%.2fs] Seed full coverage M=4 (patB)!\n", elapsed());
                goto output;
            }
            if (elapsed() > 0.20) goto patB_done;
        }
        patB_done:
        fprintf(stderr, "[%.2fs] PatB: %d enumerated\n", elapsed(), cnt);
    }

    // Pattern C: state {0,1}=前進, {2,3}=回転。連続前進型
    {
        int cnt = 0;
        for (int t2 = 1; t2 <= 2; t2++)
        for (int t3 = 1; t3 <= 2; t3++)
        for (int b00 : {0,1,2,3}) for (int b01 : {0,1,2,3})
        for (int b02 : {0,1,2,3}) for (int b03 : {0,1,2,3})
        for (int w0 = 1; w0 <= 2; w0++) for (int w1 = 1; w1 <= 2; w1++)
        for (int w2 = 1; w2 <= 2; w2++) for (int w3 = 1; w3 <= 2; w3++)
        for (int wb0 : {0,1,2,3}) for (int wb1 : {0,1,2,3})
        for (int wb2 : {0,1,2,3}) for (int wb3 : {0,1,2,3}) {
            cnt++;
            Automaton a = {4, {0,0,t2,t3}, {b00,b01,b02,b03},
                              {w0,w1,w2,w3}, {wb0,wb1,wb2,wb3}};
            if (try_seed(a) && global_best.cov == N*N) {
                fprintf(stderr, "[%.2fs] Seed full coverage M=4 (patC)!\n", elapsed());
                goto output;
            }
            if (elapsed() > 0.25) goto patC_done;
        }
        patC_done:
        fprintf(stderr, "[%.2fs] PatC: %d enumerated\n", elapsed(), cnt);
    }

    // Pattern D: state {1,2}=前進, {0,3}=回転。中央前進型
    {
        int cnt = 0;
        for (int t0 = 1; t0 <= 2; t0++)
        for (int t3 = 1; t3 <= 2; t3++)
        for (int b00 : {0,1,2,3}) for (int b01 : {0,1,2,3})
        for (int b02 : {0,1,2,3}) for (int b03 : {0,1,2,3})
        for (int w0 = 1; w0 <= 2; w0++) for (int w1 = 1; w1 <= 2; w1++)
        for (int w2 = 1; w2 <= 2; w2++) for (int w3 = 1; w3 <= 2; w3++)
        for (int wb0 : {0,1,2,3}) for (int wb1 : {0,1,2,3})
        for (int wb2 : {0,1,2,3}) for (int wb3 : {0,1,2,3}) {
            cnt++;
            Automaton a = {4, {t0,0,0,t3}, {b00,b01,b02,b03},
                              {w0,w1,w2,w3}, {wb0,wb1,wb2,wb3}};
            if (try_seed(a) && global_best.cov == N*N) {
                fprintf(stderr, "[%.2fs] Seed full coverage M=4 (patD)!\n", elapsed());
                goto output;
            }
            if (elapsed() > 0.30) goto patD_done;
        }
        patD_done:
        fprintf(stderr, "[%.2fs] PatD: %d enumerated\n", elapsed(), cnt);
    }

    // シードをカバレッジ降順でソートし、上位80個に絞る
    sort(top_seeds.begin(), top_seeds.end(),
         [](const Cand& a, const Cand& b) { return a.cov > b.cov; });
    if ((int)top_seeds.size() > 80) top_seeds.resize(80);
    fprintf(stderr, "[%.2fs] Total seeds: %d, best=%d M=%d\n",
            elapsed(), (int)top_seeds.size(), global_best.cov, global_best.aut.M);

    // ============================================================
    // Phase 2: ビームサーチ (M=5→8)
    //   親シードの遷移1本を新状態new_sに繋ぎ替え、
    //   new_sの(a0,b0,a1,b1)を全列挙 → 単一位置評価でフィルタ
    //   候補数/seed: 2M attachments × 3×M×2×M = 12M³
    //   M=5: 1500/seed, M=6: 2160/seed (単一位置eval → ~2μs/候補)
    //   ビーム幅を段階的に縮小: M=5:60, M=6:50, M=7:35, M=8:20
    // ============================================================

    // M=4シードの正確な評価 (Phase 0で粗評価のものをfull eval)
    {
        for (int i = 0; i < min(20, (int)top_seeds.size()) && elapsed() < 0.40; i++) {
            if (top_seeds[i].aut.M != 4) continue;
            auto res = best_start(top_seeds[i].aut);
            top_seeds[i].cov = res.cov;
            top_seeds[i].si = res.si; top_seeds[i].sj = res.sj; top_seeds[i].sd = res.sd;
            if (res.cov > global_best.cov) global_best = top_seeds[i];
            if (res.cov == N*N) {
                fprintf(stderr, "  FOUND M=4!\n");
                goto output;
            }
        }
        sort(top_seeds.begin(), top_seeds.end(),
             [](const Cand& a, const Cand& b) { return a.cov > b.cov; });
        fprintf(stderr, "[%.2fs] M=4 full eval done, best=%d\n", elapsed(), global_best.cov);
    }

    // M+1ビームサーチ本体: 各Mレベルで新状態を1つ追加して全列挙
    {
        static const int max_seeds[] = {0,0,0,0,0, 60, 50, 35, 20};
        for (int target_m = 5; target_m <= 8 && elapsed() < 1.85; target_m++) {
            int n_prev = 0;
            for (auto& s : top_seeds) if (s.aut.M == target_m - 1) n_prev++;
            if (n_prev == 0) continue;
            int use_seeds = min(n_prev, max_seeds[target_m]);

            fprintf(stderr, "[%.2fs] === Beam M=%d (using %d/%d seeds) ===\n",
                    elapsed(), target_m, use_seeds, n_prev);
            int new_s = target_m - 1;
            vector<Cand> next_cands;
            int seed_cnt = 0;

            for (auto& seed : top_seeds) {
                if (seed.aut.M != target_m - 1) continue;
                if (++seed_cnt > use_seeds) break;
                if (elapsed() > 1.85) break;

                for (int from = 0; from < seed.aut.M && elapsed() < 1.85; from++) {
                    for (int wall = 0; wall <= 1; wall++) {
                        for (int na0 = 0; na0 < 3; na0++)
                        for (int nb0 = 0; nb0 < target_m; nb0++)
                        for (int na1 = 1; na1 <= 2; na1++)
                        for (int nb1 = 0; nb1 < target_m; nb1++) {
                            Automaton ext = seed.aut;
                            ext.M = target_m;
                            if (wall == 0) ext.b0[from] = new_s;
                            else ext.b1[from] = new_s;
                            ext.a0[new_s] = na0;
                            ext.b0[new_s] = nb0;
                            ext.a1[new_s] = na1;
                            ext.b1[new_s] = nb1;

                            if (try_cand(ext, seed, next_cands)) {
                                fprintf(stderr, "  Beam FOUND M=%d!\n", target_m);
                                goto output;
                            }
                        }
                    }
                }
            }

            // Sort, trim to top-50, but keep all with cov>=395 for full eval
            sort(next_cands.begin(), next_cands.end(),
                 [](const Cand& a, const Cand& b) { return a.cov > b.cov; });
            {
                int keep = 50;
                while (keep < (int)next_cands.size() && next_cands[keep].cov >= 395) keep++;
                if ((int)next_cands.size() > keep) next_cands.resize(keep);
            }

            // Full eval: top-20 always + any with cov>=395
            for (int i = 0; i < (int)next_cands.size() && elapsed() < 1.88; i++) {
                if (i >= 20 && next_cands[i].cov < 395) break;
                auto res = best_start(next_cands[i].aut);
                next_cands[i].cov = res.cov;
                next_cands[i].si = res.si; next_cands[i].sj = res.sj; next_cands[i].sd = res.sd;
                if (res.cov > global_best.cov) global_best = next_cands[i];
                if (res.cov == N*N) {
                    fprintf(stderr, "  Beam top20 FOUND M=%d!\n", target_m);
                    goto output;
                }
            }
            // Re-sort after full eval
            sort(next_cands.begin(), next_cands.end(),
                 [](const Cand& a, const Cand& b) { return a.cov > b.cov; });

            // Merge into seeds for next level
            for (auto& c : next_cands) top_seeds.push_back(c);
            sort(top_seeds.begin(), top_seeds.end(),
                 [](const Cand& a, const Cand& b) { return a.cov > b.cov; });
            if ((int)top_seeds.size() > 80) top_seeds.resize(80);

            fprintf(stderr, "[%.2fs] Beam M=%d: %d cands, best=%d\n",
                    elapsed(), target_m, (int)next_cands.size(),
                    next_cands.empty() ? 0 : next_cands[0].cov);
        }
    }

    // ============================================================
    // Fallback: 全被覆できなかった場合
    //   best partialのロボット + 未カバーセルにspinner (1状態で回転するだけ)
    //   コスト = AK*(K-1) + AM*M_total  (K=1+uncov, M_total=best.M+uncov)
    // ============================================================
    fprintf(stderr, "[%.2fs] No full coverage found (best=%d M=%d). Using fallback.\n",
            elapsed(), global_best.cov, global_best.aut.M);
    {
        // Find exact covered cells of global_best
        bool covered[N][N];
        simulate_cells(global_best.aut, global_best.si, global_best.sj, global_best.sd, covered);

        // Count actually covered
        int cov_cnt = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (covered[i][j]) cov_cnt++;

        // Output: main robot + spinners for uncovered
        int uncov = N*N - cov_cnt;
        int K = 1 + uncov;
        int total_M = global_best.aut.M + uncov;
        long long cost = (long long)ak * (K - 1) + (long long)am * total_M;
        fprintf(stderr, "Fallback: K=%d M_total=%d uncov=%d cost=%lld\n", K, total_M, uncov, cost);

        printf("%d\n", K);
        // Main robot
        printf("%d %d %d %c\n", global_best.aut.M, global_best.si, global_best.sj, DIR_CH[global_best.sd]);
        for (int s = 0; s < global_best.aut.M; s++)
            printf("%s %d %s %d\n",
                ACT_STR[global_best.aut.a0[s]], global_best.aut.b0[s],
                ACT_STR[global_best.aut.a1[s]], global_best.aut.b1[s]);
        // Spinner robots for uncovered cells
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (!covered[i][j]) {
                    printf("1 %d %d U\nR 0 R 0\n", i, j);
                }

        // No new walls
        for (int i = 0; i < N; i++) { for (int j = 0; j < N-1; j++) printf("0"); printf("\n"); }
        for (int i = 0; i < N-1; i++) { for (int j = 0; j < N; j++) printf("0"); printf("\n"); }
        return 0;
    }

    output:
    fprintf(stderr, "[%.2fs] Output: M=%d cov=%d start=(%d,%d,%c)\n",
            elapsed(), global_best.aut.M, global_best.cov,
            global_best.si, global_best.sj, DIR_CH[global_best.sd]);

    printf("1\n");
    printf("%d %d %d %c\n", global_best.aut.M, global_best.si, global_best.sj, DIR_CH[global_best.sd]);
    for (int s = 0; s < global_best.aut.M; s++)
        printf("%s %d %s %d\n",
            ACT_STR[global_best.aut.a0[s]], global_best.aut.b0[s],
            ACT_STR[global_best.aut.a1[s]], global_best.aut.b1[s]);
    for (int i = 0; i < N; i++) { for (int j = 0; j < N-1; j++) printf("0"); printf("\n"); }
    for (int i = 0; i < N-1; i++) { for (int j = 0; j < N; j++) printf("0"); printf("\n"); }
    return 0;
}

Submission Info

Judge Result