提出 #68712493

---

ソースコード 拡げる

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

/*
  AHC052：配置(4..9) → 領域ロック×ローカル希望→グローバル投票（塗り 0..3） → 仕上げBFS
  - 0..3 は全ロボ共通で R(0), D(1), L(2), U(3)
  - 4..9 は「壁延長で領域抽出 → 中心に近い10領域を代表点化 → ハンガリー割当」
            → 最短路の要約（多数決）＋軽い座標降下 で 配置フェーズ を最適化
  - 塗りは「owner固定（配置後の位置から多源BFS）＋ 壁距離重み ＋ 担当外ペナルティ」
      各手で各ロボの“望む向き”を計算 → 4ボタンを投票評価（違反最小・重み最大・新規被覆多）
  - 全被覆で即終了。出力に T は不要（ボタン割当K行 → 操作列を1行ずつ）
*/

// ===== 調整パラメータ =====
static const int SPREAD_REPEAT =2;     // 4444..9999 各ボタンの連打回数（固定）
static const int GREEDY_PASSES  = 3;    // 4..9 の座標降下の周回
static const int IDLE_STREAK_TO_BFS = 6;// 貪欲塗りで増分が止まったら仕上げへ
static const int SPREAD_SAFE_LIMIT = 2; // 配置フェーズの press で (moved==0 && gain==0) が続いたら抜ける保険

// 重み（端優先 & 担当外抑止）
static const double ALPHA_WALL = 5.0;   // 壁距離の逆数の重み
static const double BETA_EDGE  = 1.0;   // owner境界セルボーナス
static const double GAMMA_BASE = 0.5;   // 基本加点
static const double LEAK_PEN   = 0.0;   // 担当外ペナルティ（大きいほど外へ出にくい）
static const double STAY_PEN   = 0.15;  // その場留まりの微罰（動けるなら動かす）

// 方向: 0=R,1=D,2=L,3=U,4=S
static inline char dch(int d){ return d==0?'R': d==1?'D': d==2?'L': d==3?'U':'S'; }
static inline int  cid(int i,int j,int N){ return i*N + j; }

// ---- ハンガリー法（最小化） ----
struct Hungarian {
    int n; vector<vector<int>> a;
    Hungarian(int n): n(n), a(n, vector<int>(n,0)) {}
    void set_cost(int i,int j,int c){ a[i][j]=c; }
    pair<int, vector<int>> solve(){
        const int INF=1e9;
        vector<int> u(n+1), v(n+1), p(n+1), way(n+1);
        for(int i=1;i<=n;i++){
            p[0]=i; int j0=0; vector<int> minv(n+1,INF); vector<char> used(n+1,false);
            do{
                used[j0]=true; int i0=p[j0], delta=INF, j1=0;
                for(int j=1;j<=n;j++) if(!used[j]){
                    int cur=a[i0-1][j-1]-u[i0]-v[j];
                    if(cur<minv[j]){ minv[j]=cur; way[j]=j0; }
                    if(minv[j]<delta){ delta=minv[j]; j1=j; }
                }
                for(int j=0;j<=n;j++){
                    if(used[j]){ u[p[j]]+=delta; v[j]-=delta; }
                    else minv[j]-=delta;
                }
                j0=j1;
            }while(p[j0]!=0);
            do{ int j1=way[j0]; p[j0]=p[j1]; j0=j1; }while(j0);
        }
        vector<int> match(n,-1);
        for(int j=1;j<=n;j++) if(p[j]) match[p[j]-1]=j-1;
        return {-v[0], match};
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M,K;                      // 期待: 30 10 10
    if(!(cin>>N>>M>>K)) return 0;
    vector<int> si(M), sj(M);
    for(int r=0;r<M;r++) cin>>si[r]>>sj[r];

    // vwall: N行×(N-1)列（左右の壁）; hwall: (N-1)行×N列（上下の壁）
    vector<string> vwall(N);
    for(int i=0;i<N;i++) cin>>vwall[i];
    vector<string> hwall(N-1);
    for(int i=0;i<N-1;i++) cin>>hwall[i];

    const int NN=N*N;

    // ---- 壁考慮の1手遷移 NEXT と 隣接 NBR ----
    vector<array<int,5>> NEXT(NN);
    vector<array<int,4>> NBR(NN);
    auto cid = [&](int i,int j){ return i*N + j; };
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int id=cid(i,j);
            // 右
            int ni=i, nj=j; if(j<N-1 && vwall[i][j]=='0') nj=j+1; NEXT[id][0]=cid(ni,nj);
            // 下
            ni=i; nj=j; if(i<N-1 && hwall[i][j]=='0') ni=i+1; NEXT[id][1]=cid(ni,nj);
            // 左
            ni=i; nj=j; if(j>0   && vwall[i][j-1]=='0') nj=j-1; NEXT[id][2]=cid(ni,nj);
            // 上
            ni=i; nj=j; if(i>0   && hwall[i-1][j]=='0') ni=i-1; NEXT[id][3]=cid(ni,nj);
            // 待機
            NEXT[id][4]=id;

            int ptr=0;
            for(int d=0; d<4; d++){ int v=NEXT[id][d]; if(v!=id) NBR[id][ptr++]=v; }
            for(;ptr<4;ptr++) NBR[id][ptr]=id;
        }
    }

    auto bfs_from = [&](int s){
        vector<int> dist(NN, INT_MAX);
        deque<int> dq; dist[s]=0; dq.push_back(s);
        while(!dq.empty()){
            int u=dq.front(); dq.pop_front();
            for(int k=0;k<4;k++){
                int v=NBR[u][k]; if(v==u) continue;
                if(dist[v] > dist[u]+1){ dist[v]=dist[u]+1; dq.push_back(v); }
            }
        }
        return dist;
    };

    // ---- 既存の壁を列/行方向に“延長”して分割境界（0..N）を作る ----
    auto build_cuts = [&](int N,
                          const vector<string>& vwall,
                          const vector<string>& hwall){
        vector<int> colCuts = {0, N};
        for(int j=0;j<N-1;j++){
            bool has=false; for(int i=0;i<N;i++) if(vwall[i][j]=='1'){ has=true; break; }
            if(has) colCuts.push_back(j+1);
        }
        sort(colCuts.begin(), colCuts.end());
        colCuts.erase(unique(colCuts.begin(), colCuts.end()), colCuts.end());

        vector<int> rowCuts = {0, N};
        for(int i=0;i<N-1;i++){
            bool has=false; for(int j=0;j<N;j++) if(hwall[i][j]=='1'){ has=true; break; }
            if(has) rowCuts.push_back(i+1);
        }
        sort(rowCuts.begin(), rowCuts.end());
        rowCuts.erase(unique(rowCuts.begin(), rowCuts.end()), rowCuts.end());
        return pair<vector<int>,vector<int>>(rowCuts, colCuts);
    };

    auto pick_center_in_rect = [&](int i0,int i1,int j0,int j1){
        int ci_geo=(i0+i1)/2, cj_geo=(j0+j1)/2;
        int bestI=i0, bestJ=j0, bestScore=INT_MIN;
        for(int i=i0;i<=i1;i++){
            for(int j=j0;j<=j1;j++){
                int toEdge = min({i-i0, i1-i, j-j0, j1-j});
                int nearGeo = -(abs(i-ci_geo)+abs(j-cj_geo));
                int sc = 10*toEdge + nearGeo; // 端から離す:10、幾何中心:1
                if(sc>bestScore){ bestScore=sc; bestI=i; bestJ=j; }
            }
        }
        return pair<int,int>(bestI,bestJ);
    };

    // ---- ターゲット（中心に近い領域の代表点 10 個）を作る ----
    auto [rowCuts, colCuts] = build_cuts(N, vwall, hwall);

    struct Rect { int i0,i1,j0,j1, ci,cj, centerDist; };
    vector<Rect> rects;
    int GI=(N-1)/2, GJ=(N-1)/2;
    for(int a=0; a+1<(int)rowCuts.size(); a++){
        for(int b=0; b+1<(int)colCuts.size(); b++){
            int i0=rowCuts[a], i1=rowCuts[a+1]-1;
            int j0=colCuts[b], j1=colCuts[b+1]-1;
            if(i0>i1 || j0>j1) continue;
            auto [ci,cj]=pick_center_in_rect(i0,i1,j0,j1);
            int cd=abs(ci-GI)+abs(cj-GJ);
            rects.push_back({i0,i1,j0,j1,ci,cj,cd});
        }
    }
    sort(rects.begin(),rects.end(),[&](const Rect&A,const Rect&B){return A.centerDist<B.centerDist;});

    vector<pair<int,int>> targets;
    for(int k=0;k<(int)rects.size() && (int)targets.size()<10; k++)
        targets.emplace_back(rects[k].ci, rects[k].cj);
    if((int)targets.size()<10){
        // フォールバック：2x5 の中点で補完
        int rc2[3]={0,N/2,N}, cc2[6]={0,N/5,2*N/5,3*N/5,4*N/5,N};
        for(int rb=0; rb<2 && (int)targets.size()<10; rb++)
            for(int cb=0; cb<5 && (int)targets.size()<10; cb++){
                int i0=rc2[rb], i1=rc2[rb+1]-1, j0=cc2[cb], j1=cc2[cb+1]-1;
                auto [ci,cj]=pick_center_in_rect(i0,i1,j0,j1);
                if(find(targets.begin(),targets.end(),make_pair(ci,cj))==targets.end())
                    targets.emplace_back(ci,cj);
            }
    }

    // ---- BFS距離 → ハンガリー割当 ----
    vector<vector<int>> distR(M);
    for(int r=0;r<M;r++) distR[r]=bfs_from(cid(si[r],sj[r]));
    vector<vector<int>> distT(10);
    for(int t=0;t<10;t++) distT[t]=bfs_from(cid(targets[t].first, targets[t].second));

    struct Hungarian {
        int n; vector<vector<int>> a;
        Hungarian(int n): n(n), a(n, vector<int>(n,0)) {}
        void set_cost(int i,int j,int c){ a[i][j]=c; }
        pair<int, vector<int>> solve(){
            const int INF=1e9;
            vector<int> u(n+1), v(n+1), p(n+1), way(n+1);
            for(int i=1;i<=n;i++){
                p[0]=i; int j0=0; vector<int> minv(n+1,INF); vector<char> used(n+1,false);
                do{
                    used[j0]=true; int i0=p[j0], delta=INF, j1=0;
                    for(int j=1;j<=n;j++) if(!used[j]){
                        int cur=a[i0-1][j-1]-u[i0]-v[j];
                        if(cur<minv[j]){ minv[j]=cur; way[j]=j0; }
                        if(minv[j]<delta){ delta=minv[j]; j1=j; }
                    }
                    for(int j=0;j<=n;j++){
                        if(used[j]){ u[p[j]]+=delta; v[j]-=delta; }
                        else minv[j]-=delta;
                    }
                    j0=j1;
                }while(p[j0]!=0);
                do{ int j1=way[j0]; p[j0]=p[j1]; j0=j1; }while(j0);
            }
            vector<int> match(n,-1);
            for(int j=1;j<=n;j++) if(p[j]) match[p[j]-1]=j-1;
            return {-v[0], match};
        }
    };

    Hungarian hung(M); // M==10
    for(int r=0;r<M;r++){
        for(int t=0;t<10;t++){
            int c = distR[r][ cid(targets[t].first, targets[t].second) ];
            if(c==INT_MAX) c=100000;
            hung.set_cost(r,t,c);
        }
    }
    auto [assignCost, matchRT] = hung.solve(); // matchRT[r] in [0,9]

    // ---- ボタン割当テーブル ACT[b][r] ----
    vector<array<int,128>> ACT(K);
    for(int b=0;b<K;b++) for(int r=0;r<M;r++) ACT[b][r]=4; // S 初期化
    // 0..3 は全ロボ共通で R D L U（塗り用）
    for(int r=0;r<M;r++){ ACT[0][r]=0; ACT[1][r]=1; ACT[2][r]=2; ACT[3][r]=3; }
    auto dch=[&](int d){ return d==0?'R': d==1?'D': d==2?'L': d==3?'U':'S'; };

    // r番ロボの start→target の最短路(方向列 0/1/2/3)
    auto shortest_dir_path = [&](int r)->vector<int>{
        int s = cid(si[r], sj[r]);
        int t = cid(targets[ matchRT[r] ].first, targets[ matchRT[r] ].second);
        vector<int> pre(NN,-1), pd(NN,-1);
        deque<int> dq; dq.push_back(s); pre[s]=s;
        while(!dq.empty()){
            int u=dq.front(); dq.pop_front();
            if(u==t) break;
            for(int d=0; d<4; d++){
                int v=NEXT[u][d]; if(v==u) continue;
                if(pre[v]==-1){ pre[v]=u; pd[v]=d; dq.push_back(v); }
            }
        }
        vector<int> path;
        if(pre[t]==-1) return path;
        for(int u=t; u!=s; u=pre[u]) path.push_back(pd[u]);
        reverse(path.begin(), path.end());
        return path;
    };

    vector<vector<int>> paths(M);
    for(int r=0;r<M;r++) paths[r]=shortest_dir_path(r);

    // 調整パラメータ
    static const int SPREAD_REPEAT = 2;     // 4444..9999 各ボタンの連打回数（固定）
    static const int GREEDY_PASSES  = 10;    // 4..9 の座標降下の周回
    static const int IDLE_STREAK_TO_BFS = 0;// 貪欲塗りで増分が止まったら仕上げへ
    static const int SPREAD_SAFE_LIMIT = 10; // 配置フェーズの press で (moved==0 && gain==0) が続いたら抜ける保険

    // 4..9 を「6ブロック×SPREAD_REPEAT 手」の多数決で初期化
    for(int r=0;r<M;r++){
        for(int k=0;k<6;k++){
            int b=4+k;
            array<int,5> cnt={0,0,0,0,0};
            for(int t=0;t<SPREAD_REPEAT; t++){
                int idx=k*SPREAD_REPEAT+t;
                if(idx<(int)paths[r].size()) cnt[ paths[r][idx] ]++;
                else cnt[4]++;
            }
            int best=4; for(int d=0; d<4; d++) if(cnt[d]>cnt[best]) best=d;
            ACT[b][r]=best;
        }
    }

    // 座標降下（4..9 のみ評価）：4444..9999 適用後の Σ距離(target_r, 最終pos_r) を最小化
    vector<int> spread_seq; spread_seq.reserve(6*SPREAD_REPEAT);
    for(int b=4;b<=9;b++) for(int t=0;t<SPREAD_REPEAT;t++) spread_seq.push_back(b);

    auto eval_spread = [&](const vector<array<int,128>>& A)->long long{
        array<int,128> pos{};
        for(int r=0;r<M;r++) pos[r]=cid(si[r],sj[r]);
        for(int btn: spread_seq)
            for(int r=0;r<M;r++) pos[r]=NEXT[pos[r]][ A[btn][r] ];
        long long sum=0;
        for(int r=0;r<M;r++){
            int t = matchRT[r];
            int d = distT[t][ pos[r] ];
            if(d==INT_MAX) d=100000;
            sum += d;
        }
        return sum; // 小さいほど良
    };

    auto greedy_coordinate_descent = [&](){
        long long cur = eval_spread(ACT);
        bool improved=true;
        for(int pass=0; pass<GREEDY_PASSES && improved; ++pass){
            improved=false;
            for(int r=0;r<M;r++){
                for(int b=4;b<=9;b++){
                    int old = ACT[b][r];
                    int bestAct=old; long long bestVal=cur;
                    for(int cand=0;cand<=4;cand++){
                        if(cand==old) continue;
                        ACT[b][r]=cand;
                        long long val=eval_spread(ACT);
                        if(val<bestVal){ bestVal=val; bestAct=cand; }
                    }
                    if(bestAct!=old){ ACT[b][r]=bestAct; cur=bestVal; improved=true; }
                    else ACT[b][r]=old;
                }
            }
        }
    };
    greedy_coordinate_descent();

    // === (追加) 0..3 のロボ別変換を「多数決ロックイン」で最適化 =====================
    const int MAP_PROBE_STEPS    = 320; // 仮本番の手数
    const int MAP_LOCK_ROUNDS    = 3;   // ロックのラウンド数
    const int MAP_LOCK_PER_ROUND = 1;   // 1ラウンドで固定するロボ数
    const double LOCK_MIN_FRAC   = 0.55;// ロック閾値（賛成率）

    const int TBL[8][4] = {
        {0,1,2,3}, {1,2,3,0}, {2,3,0,1}, {3,0,1,2},
        {2,1,0,3}, {1,0,3,2}, {0,3,2,1}, {3,2,1,0}
    };
    auto next_with_map = [&](int p, int mapi, int btn)->int{
        return NEXT[p][ TBL[mapi][btn] ];
    };

    // 4..9 をオフライン適用して配置後を得る
    vector<int> pos_sim(M); vector<char> seen_sim(NN,0); int covered_sim=0;
    for(int r=0;r<M;r++){ int p=cid(si[r],sj[r]); pos_sim[r]=p; if(!seen_sim[p]){ seen_sim[p]=1; covered_sim++; } }
    for(int btn: spread_seq){
        for(int r=0;r<M;r++) pos_sim[r]=NEXT[pos_sim[r]][ ACT[btn][r] ];
        for(int r=0;r<M;r++){ int p=pos_sim[r]; if(!seen_sim[p]){ seen_sim[p]=1; covered_sim++; } }
    }

    // owner_fix（配置後基準）
    vector<int> owner_fix(NN,-1), distOwn_fix(NN,INT_MAX);
    auto build_owner_fix = [&](){
        fill(owner_fix.begin(),owner_fix.end(),-1);
        fill(distOwn_fix.begin(),distOwn_fix.end(),INT_MAX);
        deque<int> dq;
        for(int r=0;r<M;r++){
            int s=pos_sim[r];
            if(distOwn_fix[s]>0){ distOwn_fix[s]=0; owner_fix[s]=r; dq.push_back(s); }
            else if(owner_fix[s]>r) owner_fix[s]=r;
        }
        while(!dq.empty()){
            int u=dq.front(); dq.pop_front();
            for(int k=0;k<4;k++){
                int v=NBR[u][k]; if(v==u) continue;
                if(distOwn_fix[v] > distOwn_fix[u]+1){
                    distOwn_fix[v]=distOwn_fix[u]+1; owner_fix[v]=owner_fix[u]; dq.push_back(v);
                }else if(distOwn_fix[v]==distOwn_fix[u]+1 && owner_fix[v]>owner_fix[u]){
                    owner_fix[v]=owner_fix[u];
                }
            }
        }
    };
    build_owner_fix();

    // 壁距離（外周＆実壁に接するセルから）
    vector<int> distWall_fix(NN, INT_MAX);
    auto build_wall_distance_fix = [&](){
        deque<int> dq;
        auto touch_wall = [&](int i,int j)->bool{
            if(i==0||i==N-1||j==0||j==N-1) return true;
            if(vwall[i][j]=='1') return true;
            if(j>0 && vwall[i][j-1]=='1') return true;
            if(hwall[i][j]=='1') return true;
            if(i>0 && hwall[i-1][j]=='1') return true;
            return false;
        };
        for(int i=0;i<N;i++)for(int j=0;j<N;j++){
            int p=cid(i,j);
            if(touch_wall(i,j)){ distWall_fix[p]=0; dq.push_back(p); }
        }
        while(!dq.empty()){
            int u=dq.front(); dq.pop_front();
            for(int k=0;k<4;k++){
                int v=NBR[u][k]; if(v==u) continue;
                if(distWall_fix[v] > distWall_fix[u]+1){
                    distWall_fix[v]=distWall_fix[u]+1;
                    dq.push_back(v);
                }
            }
        }
    };
    build_wall_distance_fix();

    // owner 境界マーキング
    vector<char> isBorder_fix(NN,0);
    auto mark_owner_border_fix = [&](){
        fill(isBorder_fix.begin(),isBorder_fix.end(),0);
        for(int p=0;p<NN;p++){
            int r=owner_fix[p]; if(r<0) continue;
            for(int k=0;k<4;k++){
                int v=NBR[p][k]; if(v==p) continue;
                if(owner_fix[v]!=r){ isBorder_fix[p]=1; break; }
            }
        }
    };
    mark_owner_border_fix();

    // 重み（端優先 & 担当外抑止）
    static const double ALPHA_WALL = 5.0;
    static const double BETA_EDGE  = 1.0;
    static const double GAMMA_BASE = 0.5;
    static const double LEAK_PEN   = 2.0;
    static const double STAY_PEN   = 0.15;

    auto weight_of_fix = [&](int p)->double{
        double w = GAMMA_BASE + ALPHA_WALL / (1.0 + (double)distWall_fix[p]);
        if(isBorder_fix[p]) w += BETA_EDGE;
        return w;
    };

    // probe（仮本番）
    auto local_best_dir_probe = [&](int posr, int r, int mapi, const vector<char>& seen)->pair<int,double>{
        double bestSc=-1e100; int bestB=0; bool haveIn=false;
        for(int b=0;b<4;b++){
            int q = next_with_map(posr, mapi, b);
            if(q!=posr && owner_fix[q]==r){ haveIn=true; break; }
        }
        for(int b=0;b<4;b++){
            int q = next_with_map(posr, mapi, b);
            double sc=0.0;
            if(q==posr) sc-=STAY_PEN;
            if(!seen[q]) sc += weight_of_fix(q);
            if(owner_fix[q]!=r){ sc -= haveIn ? LEAK_PEN : (0.3*LEAK_PEN); }
            if(sc>bestSc){ bestSc=sc; bestB=b; }
        }
        return {bestB, bestSc};
    };

    auto eval_button_global_probe = [&](int b,
                                        const vector<int>& posv,
                                        const vector<int>& mapv,
                                        const vector<char>& seen,
                                        const vector<pair<int,double>>& wish){
        int viol=0,gain=0,agree=0; double sumScore=0.0;
        static vector<char> mark; mark.assign(NN,0);
        for(int r=0;r<M;r++){
            int q = next_with_map(posv[r], mapv[r], b);
            if(wish[r].first==b) agree++;
            if(q!=posv[r] && owner_fix[q]!=r) viol++;
            double sc=0.0;
            if(q==posv[r]) sc-=STAY_PEN;
            if(!seen[q]){ sc+=weight_of_fix(q); mark[q]=1; }
            if(q!=posv[r] && owner_fix[q]!=r) sc-=LEAK_PEN;
            sumScore+=sc;
        }
        for(int p=0;p<NN;p++) if(mark[p] && !seen[p]) gain++;
        return tuple<int,int,int,double>(viol,gain,agree,sumScore);
    };

    auto better_tuple = [&](const tuple<int,int,int,double>& A, const tuple<int,int,int,double>& B){
        auto [va,ga,aa,sa]=A; auto [vb,gb,ab,sb]=B;
        if(va!=vb) return va<vb;   // 違反最小
        if(sa!=sb) return sa>sb;   // スコア最大
        if(ga!=gb) return ga>gb;   // 新規被覆最大
        if(aa!=ab) return aa>ab;   // 賛成多数
        return true;
    };

    struct ProbeResult{ vector<int> press_seq; vector<int> agree_cnt; };

    auto run_probe = [&](const vector<int>& mapv)->ProbeResult{
        vector<int> pos=pos_sim; vector<char> seen=seen_sim;
        vector<int> agree(M,0); vector<int> presses; presses.reserve(MAP_PROBE_STEPS);
        for(int step=0; step<MAP_PROBE_STEPS; ++step){
            vector<pair<int,double>> wish(M);
            for(int r=0;r<M;r++) wish[r]=local_best_dir_probe(pos[r], r, mapv[r], seen);
            array<tuple<int,int,int,double>,4> ev;
            for(int b=0;b<4;b++) ev[b]=eval_button_global_probe(b,pos,mapv,seen,wish);
            int best=0;
            for(int b=1;b<4;b++) if(better_tuple(ev[b],ev[best])) best=b;
            for(int r=0;r<M;r++) if(wish[r].first==best) agree[r]++;
            // 適用
            for(int r=0;r<M;r++) pos[r]=next_with_map(pos[r], mapv[r], best);
            for(int r=0;r<M;r++){ int p=pos[r]; if(!seen[p]) seen[p]=1; }
            presses.push_back(best);
        }
        return {presses, agree};
    };

    vector<int> mapIdx(M,0), locked(M,0);
    for(int round=0; round<MAP_LOCK_ROUNDS; ++round){
        ProbeResult pr = run_probe(mapIdx);
        vector<int> idxs(M); iota(idxs.begin(), idxs.end(), 0);
        sort(idxs.begin(), idxs.end(), [&](int a,int b){
            if(locked[a]!=locked[b]) return locked[a]>locked[b];
            return pr.agree_cnt[a] > pr.agree_cnt[b];
        });
        int did=0;
        double bestFrac = 0.0;
        for(int r=0;r<M;r++) bestFrac = max(bestFrac, pr.agree_cnt[r] / max(1.0, (double)MAP_PROBE_STEPS));
        for(int id: idxs){
            if(locked[id]) continue;
            double frac = pr.agree_cnt[id] / max(1.0, (double)MAP_PROBE_STEPS);
            if(frac >= max(LOCK_MIN_FRAC, min(0.9, bestFrac*0.9))){
                locked[id]=1; if(++did>=MAP_LOCK_PER_ROUND) break;
            }
        }
        for(int r=0;r<M;r++) if(!locked[r]){
            int bestIdx = mapIdx[r];
            double bestScore = -1e100;
            for(int cand=0;cand<8;cand++){
                int posr = pos_sim[r];
                double s=0.0;
                for(int b: pr.press_seq){
                    int q = next_with_map(posr, cand, b);
                    if(q==posr) s -= STAY_PEN;
                    if(owner_fix[q]==r) s += 1.0; else s -= 0.5*LEAK_PEN;
                    s += 0.2 * (ALPHA_WALL / (1.0 + (double)distWall_fix[q]));
                    posr = q;
                }
                if(s>bestScore){ bestScore=s; bestIdx=cand; }
            }
            mapIdx[r]=bestIdx;
        }
        if(accumulate(locked.begin(), locked.end(), 0)==M) break;
    }
    // 決定した変換を ACT[0..3] に反映
    for(int r=0;r<M;r++) for(int b=0;b<4;b++) ACT[b][r] = TBL[ mapIdx[r] ][b];

    // ★ ここで「実方向→押すボタン」逆写像を作る（仕上げBFSで使用）
    vector<array<int,4>> invBtn(M);
    for(int r=0;r<M;r++){
        for(int d=0; d<4; d++) invBtn[r][d]=0;
        for(int b=0; b<4; b++){
            int dir = ACT[b][r];       // ボタンbの実方向
            if(dir<4) invBtn[r][dir] = b; // 実方向→ボタン
        }
    }
    // === ここまで 0..3 最適化 =====================================================

    // ---- ボタン割当（K行）を出力（Tは出さない） ----
    for(int b=0;b<K;b++){
        for(int r=0;r<M;r++){
            if(r) cout<<' ';
            cout<<dch(ACT[b][r]);
        }
        cout<<'\n';
    }

    // ---- 操作適用ユーティリティ ----
    vector<int> pos(M); vector<char> seen(NN,0);
    int covered=0;
    for(int r=0;r<M;r++){ int p=cid(si[r],sj[r]); pos[r]=p; if(!seen[p]){ seen[p]=1; covered++; } }

    const int LIMIT = 2*N*N;
    int used=0;
    auto press_button = [&](int b)->pair<int,int>{ // (moved, gain)
        if(used>=LIMIT) return pair<int,int>(0,0);
        int moved=0,gain=0;
        for(int r=0;r<M;r++){
            int before=pos[r];
            int after = NEXT[before][ ACT[b][r] ];
            if(after!=before) moved++;
            pos[r]=after;
        }
        for(int r=0;r<M;r++){ int p=pos[r]; if(!seen[p]){ seen[p]=1; gain++; } }
        covered+=gain;
        cout<<b<<"\n";
        used++;
        return {moved,gain};
    };

    // === 1) 配置フェーズ（4444..9999） ===
    {
        int dead=0;
        for(int btn: spread_seq){
            auto [mv,gn] = press_button(btn);
            if(mv==0 && gn==0){ if(++dead>=SPREAD_SAFE_LIMIT) break; }
            else dead=0;
            if(covered==NN || used>=LIMIT) return 0;
        }
    }

    // === 2) 領域ロック（owner固定） ===
    vector<int> owner(NN,-1), distOwn(NN,INT_MAX);
    auto lock_owner = [&](){
        fill(owner.begin(),owner.end(),-1);
        fill(distOwn.begin(),distOwn.end(),INT_MAX);
        deque<int> dq;
        for(int r=0;r<M;r++){
            int s=pos[r];
            if(distOwn[s]>0){ distOwn[s]=0; owner[s]=r; dq.push_back(s); }
            else if(owner[s]>r) owner[s]=r;
        }
        while(!dq.empty()){
            int u=dq.front(); dq.pop_front();
            for(int k=0;k<4;k++){
                int v=NBR[u][k]; if(v==u) continue;
                if(distOwn[v] > distOwn[u]+1){
                    distOwn[v]=distOwn[u]+1; owner[v]=owner[u]; dq.push_back(v);
                }else if(distOwn[v]==distOwn[u]+1 && owner[v]>owner[u]){
                    owner[v]=owner[u];
                }
            }
        }
    };
    lock_owner();

    // 壁距離場（外周＋実壁に接するセルをソース）
    vector<int> distWall(NN, INT_MAX);
    auto build_wall_distance = [&](){
        deque<int> dq;
        auto touch_wall = [&](int i,int j)->bool{
            if(i==0 || i==N-1 || j==0 || j==N-1) return true;
            if(vwall[i][j]=='1') return true;              // 右側に壁
            if(j>0 && vwall[i][j-1]=='1') return true;     // 左側に壁
            if(hwall[i][j]=='1') return true;              // 下側に壁
            if(i>0 && hwall[i-1][j]=='1') return true;     // 上側に壁
            return false;
        };
        for(int i=0;i<N;i++)for(int j=0;j<N;j++){
            int p=cid(i,j);
            if(touch_wall(i,j)){ distWall[p]=0; dq.push_back(p); }
        }
        while(!dq.empty()){
            int u=dq.front(); dq.pop_front();
            for(int k=0;k<4;k++){
                int v=NBR[u][k]; if(v==u) continue;
                if(distWall[v] > distWall[u]+1){
                    distWall[v] = distWall[u]+1;
                    dq.push_back(v);
                }
            }
        }
    };
    build_wall_distance();

    // owner境界セルマーキング（ボーナス用）
    vector<char> isBorder(NN,0);
    auto mark_owner_border = [&](){
        fill(isBorder.begin(), isBorder.end(), 0);
        for(int p=0;p<NN;p++){
            int r=owner[p]; if(r<0) continue;
            for(int k=0;k<4;k++){
                int v=NBR[p][k]; if(v==p) continue;
                if(owner[v]!=r){ isBorder[p]=1; break; }
            }
        }
    };
    mark_owner_border();

    auto weight_of = [&](int p)->double{
        double w = GAMMA_BASE + ALPHA_WALL / (1.0 + (double)distWall[p]);
        if(isBorder[p]) w += BETA_EDGE;
        return w;
    };

    // ローカル希望：各ロボが「担当内で」「一番おいしい」方向を選ぶ
    auto local_best_dir = [&](int r)->pair<int,double>{
        int cur = pos[r];
        double bestSc = -1e100; int bestB = 0;
        bool exists_in_owner_move=false;
        for(int b=0;b<4;b++){
            int q = NEXT[cur][ ACT[b][r] ];
            if(q!=cur && owner[q]==r){ exists_in_owner_move=true; break; }
        }
        for(int b=0;b<4;b++){
            int q = NEXT[cur][ ACT[b][r] ];
            double sc = 0.0;
            if(q==cur) sc -= STAY_PEN;
            if(!seen[q]) sc += weight_of(q);
            if(owner[q]!=r){
                sc -= exists_in_owner_move ? LEAK_PEN : (0.3 * LEAK_PEN);
            }
            if(sc > bestSc){ bestSc=sc; bestB=b; }
        }
        return {bestB, bestSc};
    };

    // ボタン b を全体に押したときの評価
    auto eval_button_global = [&](int b,
                                  const vector<pair<int,double>>& wish)->tuple<int,int,int,double>{
        int agree=0, viol=0, moved=0; double sumScore=0.0;
        static vector<char> mark; mark.assign(NN,0);
        for(int r=0;r<M;r++){
            int q = NEXT[pos[r]][ ACT[b][r] ];
            if(wish[r].first==b) agree++;
            if(q!=pos[r]) moved++;
            if(owner[q]!=r && q!=pos[r]) viol++;
            double sc = 0.0;
            if(q==pos[r]) sc -= STAY_PEN;
            if(!seen[q]) sc += weight_of(q);
            if(owner[q]!=r && q!=pos[r]) sc -= LEAK_PEN;
            sumScore += sc;
            mark[q]=1;
        }
        int gain=0;
        for(int p=0;p<NN;p++) if(mark[p] && !seen[p]) gain++;
        return {viol, gain, agree, sumScore};
    };

    // === 3) 領域ロック × ローカル希望 → グローバル投票（塗り） ===
    int idle_streak=0;
    while(covered<NN && used<LIMIT){
        vector<pair<int,double>> wish(M);
        for(int r=0;r<M;r++) wish[r] = local_best_dir(r);
        array<tuple<int,int,int,double>,4> ev;
        for(int b=0;b<4;b++) ev[b] = eval_button_global(b, wish);
        int best = 0;
        auto better = [&](int x, int y){
            auto [vx, gx, ax, sx] = ev[x];
            auto [vy, gy, ay, sy] = ev[y];
            if(vx != vy) return vx < vy;
            if(sx != sy) return sx > sy;
            if(gx != gy) return gx > gy;  // gain大
            if(ax != ay) return ax > ay;  // 賛成多数
            return x < y;
        };
        for(int b=1;b<4;b++) if(better(b, best)) best=b;

        int before = covered;
        auto [mv,gn] = press_button(best);
        (void)mv;
        if(covered==before) idle_streak++; else idle_streak=0;
        if(idle_streak >= IDLE_STREAK_TO_BFS) break;
    }

    if(covered==NN || used>=LIMIT) return 0;

    // === 4) 仕上げ：最寄り未訪1マスを選び、その最寄りロボ r★ の最短路を「r★に合うボタン」で押す ===
    auto multi_source_from_robots = [&](
        const vector<int>& pos,
        vector<int>& ownerTmp, vector<int>& distTmp
    ){
        ownerTmp.assign(NN,-1);
        distTmp.assign(NN, INT_MAX);
        deque<int> dq;
        for(int r=0;r<M;r++){
            int s=pos[r];
            if(distTmp[s]>0){ distTmp[s]=0; ownerTmp[s]=r; dq.push_back(s); }
            else if(ownerTmp[s]>r) ownerTmp[s]=r;
        }
        while(!dq.empty()){
            int u=dq.front(); dq.pop_front();
            for(int k=0;k<4;k++){
                int v=NBR[u][k]; if(v==u) continue;
                if(distTmp[v] > distTmp[u]+1){
                    distTmp[v]=distTmp[u]+1; ownerTmp[v]=ownerTmp[u]; dq.push_back(v);
                }else if(distTmp[v]==distTmp[u]+1 && ownerTmp[v]>ownerTmp[u]){
                    ownerTmp[v]=ownerTmp[u];
                }
            }
        }
    };

    vector<int> owner2, dist2;
    while(covered<NN && used<LIMIT){
        multi_source_from_robots(pos, owner2, dist2);
        int pstar=-1, best=INT_MAX;
        for(int p=0;p<NN;p++) if(!seen[p] && dist2[p]<best){ best=dist2[p]; pstar=p; }
        if(pstar==-1 || best==INT_MAX) break;

        int rstar = owner2[pstar];

        // rstar 単一源BFSで経路復元（絶対方向 0..3）
        vector<int> pre(NN,-1), pd(NN,-1);
        deque<int> q;
        int s = pos[rstar];
        q.push_back(s); pre[s]=s;
        while(!q.empty()){
            int u=q.front(); q.pop_front();
            if(u==pstar) break;
            for(int d=0; d<4; d++){
                int v=NEXT[u][d]; if(v==u) continue;
                if(pre[v]==-1){ pre[v]=u; pd[v]=d; q.push_back(v); }
            }
        }
        if(pre[pstar]==-1) break; // 保険

        vector<int> path;
        for(int u=pstar; u!=s; u=pre[u]) path.push_back(pd[u]);
        reverse(path.begin(), path.end());

        // ★ 絶対方向 → r★ に対して押すべきボタンへ変換して押下
        for(int dAbs: path){
            int b = invBtn[rstar][dAbs];
            auto [mv,gn] = press_button(b);
            (void)mv; (void)gn;
            if(covered==NN || used>=LIMIT) break;
        }
    }

    return 0;
}

提出情報

ジャッジ結果