提出 #73749558

---

ソースコード 拡げる

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <random>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

// 実行時間管理
struct Timer {
    chrono::high_resolution_clock::time_point start_time;
    Timer() { start_time = chrono::high_resolution_clock::now(); }
    double get_time() {
        auto now = chrono::high_resolution_clock::now();
        return chrono::duration<double>(now - start_time).count();
    }
};

const int N = 20;

struct Input {
    int N_val;
    long long AK, AM, AW;
    vector<string> wall_v;
    vector<string> wall_h;
    
    void read() {
        if (!(cin >> N_val >> AK >> AM >> AW)) return;
        wall_v.resize(N_val);
        for (int i = 0; i < N_val; ++i) cin >> wall_v[i];
        wall_h.resize(N_val - 1);
        for (int i = 0; i < N_val - 1; ++i) cin >> wall_h[i];
    }
    
    bool has_wall(int r, int c, int d) const {
        if (d == 0) { // U
            if (r == 0) return true;
            return wall_h[r - 1][c] == '1';
        } else if (d == 1) { // R
            if (c == N - 1) return true;
            return wall_v[r][c] == '1';
        } else if (d == 2) { // D
            if (r == N - 1) return true;
            return wall_h[r][c] == '1';
        } else if (d == 3) { // L
            if (c == 0) return true;
            return wall_v[r][c - 1] == '1';
        }
        return true;
    }
};

struct Robot {
    int mk;
    int r, c;
    char d;
    vector<char> a0, a1;
    vector<int> b0, b1;
};

struct Solution {
    vector<Robot> robots;
    long long cost;
    void calc_cost(long long AK, long long AM) {
        long long K = robots.size();
        long long M = 0;
        for (const auto& r : robots) M += r.mk;
        cost = AK * max(0LL, K - 1) + AM * M;
    }
    void print() const {
        cout << robots.size() << "\n";
        for (const auto& rob : robots) {
            cout << rob.mk << " " << rob.r << " " << rob.c << " " << rob.d << "\n";
            for (int s = 0; s < rob.mk; ++s) {
                cout << rob.a0[s] << " " << rob.b0[s] << " " << rob.a1[s] << " " << rob.b1[s] << "\n";
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N - 1; ++j) cout << "0";
            cout << "\n";
        }
        for (int i = 0; i < N - 1; ++i) {
            for (int j = 0; j < N; ++j) cout << "0";
            cout << "\n";
        }
    }
};

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
const char dir_char[] = {'U', 'R', 'D', 'L'};

struct CycleInfo {
    Robot rob;
    vector<int> cells;
};

Robot shift_robot(Robot rob, int target_r, int target_c, const Input& in) {
    int r = rob.r, c = rob.c, d = 0;
    if (rob.d == 'U') d = 0; else if (rob.d == 'R') d = 1; else if (rob.d == 'D') d = 2; else if (rob.d == 'L') d = 3;
    int s = 0;
    
    for (int step = 0; step < 10000; ++step) {
        if (r == target_r && c == target_c) {
            vector<int> map_state(rob.mk, -1);
            map_state[s] = 0;
            int nfree = 1;
            for (int i = 0; i < rob.mk; ++i) {
                if (map_state[i] == -1) map_state[i] = nfree++;
            }
            
            Robot nrob = rob;
            nrob.r = r; nrob.c = c; nrob.d = dir_char[d];
            for (int i = 0; i < rob.mk; ++i) {
                int n_s = map_state[i];
                nrob.a0[n_s] = rob.a0[i];
                nrob.b0[n_s] = map_state[rob.b0[i]];
                nrob.a1[n_s] = rob.a1[i];
                nrob.b1[n_s] = map_state[rob.b1[i]];
            }
            return nrob;
        }
        
        bool wall = in.has_wall(r, c, d);
        char act = wall ? rob.a1[s] : rob.a0[s];
        int nxt_s = wall ? rob.b1[s] : rob.b0[s];
        
        if (act == 'F' && !wall) {
            r += dr[d]; c += dc[d];
        } else if (act == 'R') d = (d + 1) % 4;
        else if (act == 'L') d = (d + 3) % 4;
        s = nxt_s;
    }
    return rob; 
}

void explore_policy(int mk, const vector<char>& a0, const vector<int>& b0, const vector<char>& a1, const vector<int>& b1, vector<CycleInfo>& pool, const Input& in, vector<int>& visited, vector<int>& path) {
    int V = N * N * 4 * mk;
    if (visited.size() < V) visited.resize(V);
    else fill(visited.begin(), visited.begin() + V, 0);
    
    for (int start_v = 0; start_v < V; ++start_v) {
        if (visited[start_v]) continue;
        
        int curr = start_v;
        path.clear();
        
        while (visited[curr] == 0) {
            visited[curr] = 1;
            path.push_back(curr);
            
            int s = curr % mk;
            int tmp = curr / mk;
            int d = tmp % 4;
            int c = (tmp / 4) % N;
            int r = (tmp / 4) / N;
            
            bool wall = in.has_wall(r, c, d);
            char act = wall ? a1[s] : a0[s];
            int nxt_s = wall ? b1[s] : b0[s];
            
            int nr = r, nc = c, nd = d;
            if (act == 'F') {
                nr += dr[d]; nc += dc[d];
            } else if (act == 'R') {
                nd = (d + 1) % 4;
            } else if (act == 'L') {
                nd = (d + 3) % 4;
            }
            curr = ((nr * N + nc) * 4 + nd) * mk + nxt_s;
        }
        
        if (visited[curr] == 1) {
            // found cycle!
            int cycle_start_idx = -1;
            for (int i = 0; i < (int)path.size(); ++i) {
                if (path[i] == curr) { cycle_start_idx = i; break; }
            }
            if (cycle_start_idx != -1) {
                set<int> cov;
                for (int i = cycle_start_idx; i < (int)path.size(); ++i) {
                    int tmp = path[i] / mk;
                    int cell = tmp / 4;
                    cov.insert(cell);
                }
                
                int start_state = curr % mk;
                int start_tmp = curr / mk;
                int start_d = start_tmp % 4;
                int start_c = (start_tmp / 4) % N;
                int start_r = (start_tmp / 4) / N;
                
                vector<int> state_map(mk, -1);
                state_map[start_state] = 0;
                int nxt_free = 1;
                for(int i = cycle_start_idx; i < (int)path.size(); ++i) {
                    int s = path[i] % mk;
                    if(state_map[s] == -1) state_map[s] = nxt_free++;
                }
                for(int s = 0; s < mk; ++s) {
                    if(state_map[s] == -1) state_map[s] = nxt_free++;
                }
                
                Robot rob;
                rob.mk = mk;
                rob.r = start_r; rob.c = start_c; rob.d = dir_char[start_d];
                rob.a0.resize(mk); rob.a1.resize(mk);
                rob.b0.resize(mk); rob.b1.resize(mk);
                
                for(int s = 0; s < mk; ++s) {
                    int new_s = state_map[s];
                    rob.a0[new_s] = a0[s];
                    rob.b0[new_s] = state_map[b0[s]];
                    rob.a1[new_s] = a1[s];
                    rob.b1[new_s] = state_map[b1[s]];
                }
                
                CycleInfo ci;
                ci.rob = rob;
                for (int cell : cov) ci.cells.push_back(cell);
                pool.push_back(ci);
            }
        }
        for (int v : path) visited[v] = 2;
    }
}

Solution solve_pattern_A(const Input& in, mt19937& rng, Timer& timer) {
    vector<CycleInfo> pool;
    vector<int> visited, path;

    char acts0[] = {'F', 'R', 'L'};
    char acts1[] = {'R', 'L'};

    // --- 1. プールの生成（既存のロジック） ---
    for (int a0_0 = 0; a0_0 < 3; ++a0_0) {
        for (int a1_0 = 0; a1_0 < 2; ++a1_0) {
            explore_policy(1, {acts0[a0_0]}, {0}, {acts1[a1_0]}, {0}, pool, in, visited, path);
        }
    }

    for(int a0_0=0; a0_0<3; ++a0_0)
    for(int a1_0=0; a1_0<2; ++a1_0)
    for(int b0_0=0; b0_0<2; ++b0_0)
    for(int b1_0=0; b1_0<2; ++b1_0)
    for(int a0_1=0; a0_1<3; ++a0_1)
    for(int a1_1=0; a1_1<2; ++a1_1)
    for(int b0_1=0; b0_1<2; ++b0_1)
    for(int b1_1=0; b1_1<2; ++b1_1) {
        explore_policy(2, {acts0[a0_0], acts0[a0_1]}, {b0_0, b0_1}, {acts1[a1_0], acts1[a1_1]}, {b1_0, b1_1}, pool, in, visited, path);
    }

    for (int mk = 3; mk <= 6; ++mk) {
        int iter = 0;
        double mk_time_limit = 0.3 * (mk - 1);
        while (true) {
            iter++;
            if ((iter & 31) == 0) {
                double t = timer.get_time();
                if (t > 1.0) goto EXPLORE_END; 
                if (t > mk_time_limit) break;
            }
            vector<char> a0(mk), a1(mk);
            vector<int> b0(mk), b1(mk);
            for (int s = 0; s < mk; ++s) {
                int r0 = rng() % 10;
                a0[s] = (r0 < 8) ? 'F' : ((r0 == 8) ? 'R' : 'L');
                b0[s] = rng() % mk;
                a1[s] = (rng() % 2 == 0) ? 'R' : 'L';
                b1[s] = rng() % mk;
            }
            explore_policy(mk, a0, b0, a1, b1, pool, in, visited, path);
        }
    }

EXPLORE_END:
    int P = pool.size();
    if (P == 0) return Solution();

    // --- 2. 貪欲法による初期解の構築 ---
    vector<bool> current_state(P, false);
    vector<int> cov_count(N * N, 0);
    int current_uncov = N * N;
    int current_k = 0;
    long long current_m_sum = 0;

    while (current_uncov > 0) {
        if ((current_k & 15) == 0 && timer.get_time() > 1.2) break; // Emergency timeout
        
        int best_idx = -1;
        double best_score = 1e18;
        for (int i = 0; i < P; ++i) {
            if (current_state[i]) continue;
            int new_cov = 0;
            for (int cell : pool[i].cells) if (cov_count[cell] == 0) new_cov++;
            if (new_cov == 0) continue;

            long long cost_delta = in.AM * pool[i].rob.mk;
            if (current_k > 0) cost_delta += in.AK;
            double score = (double)cost_delta / new_cov;
            if (score < best_score) { best_score = score; best_idx = i; }
        }
        if (best_idx == -1) break; // Infinite loop fix: no more robots can help

        current_state[best_idx] = true;
        current_k++;
        current_m_sum += pool[best_idx].rob.mk;
        for (int cell : pool[best_idx].cells) {
            if (cov_count[cell] == 0) current_uncov--;
            cov_count[cell]++;
        }
    }

    // --- 3. 焼きなまし法 (SA) ---
    auto calc_energy = [&](int k, long long m_sum, int uncov_count) -> double {
        double cost = (double)in.AK * max(0, k - 1) + (double)in.AM * m_sum;
        // ペナルティをマイルドに設定。1マス未踏につき、平均的なロボット追加コストより少し高いくらいにする
        double penalty_per_cell = in.AK + in.AM * 4.0 + 1000.0; 
        return cost + (double)uncov_count * penalty_per_cell;
    };

    double current_energy = calc_energy(current_k, current_m_sum, current_uncov);
    vector<bool> best_state = current_state;
    double best_energy = current_energy;

    double start_time = timer.get_time();
    double time_limit = 1.15;
    
    // Safety check in case greedy generation took so long we're already out of time
    if (start_time >= time_limit) {
        Solution sol;
        vector<bool> used_initial(N * N, false);
        for (int i = 0; i < P; ++i) {
            if (best_state[i]) {
                Robot rob = pool[i].rob;
                int target_cell = -1;
                for (int cell : pool[i].cells) {
                    if (!used_initial[cell]) {
                        target_cell = cell;
                        break;
                    }
                }
                if (target_cell != -1) {
                    used_initial[target_cell] = true;
                    rob = shift_robot(rob, target_cell / N, target_cell % N, in);
                }
                sol.robots.push_back(rob);
            }
        }
        sol.calc_cost(in.AK, in.AM);
        return sol;
    }
    
    int sa_iter = 0;
    while (true) {
        sa_iter++;
        if ((sa_iter & 2047) == 0) { // Check time less frequently
            if (timer.get_time() > time_limit) break;
        }

        double progress = (timer.get_time() - start_time) / (time_limit - start_time);
        // 温度スケールを調整: 悪化幅(approx 1000~2000)に対して確率的に受理されるように
        double temp_start = 2000.0; 
        double temp_end = 1.0;
        double temp = temp_start * pow(temp_end / temp_start, progress); // 指数冷却

        int type = rng() % 3;
        int add_idx = -1, rem_idx = -1;
        if (type == 0 || type == 2) {
            add_idx = rng() % P;
            if (current_state[add_idx]) add_idx = -1;
        }
        if (type == 1 || type == 2) {
            if (current_k > 0) {
                int r = rng() % P;
                for(int i=0; i<P; ++i) {
                    int idx = (r+i)%P;
                    if(current_state[idx]) { rem_idx = idx; break; }
                }
            }
        }
        
        if (type == 2 && (add_idx == -1 || rem_idx == -1)) continue;
        if (type == 0 && add_idx == -1) continue;
        if (type == 1 && rem_idx == -1) continue;

        // 差分計算
        int next_k = current_k;
        long long next_m_sum = current_m_sum;
        int next_uncov = current_uncov;

        if (add_idx != -1) { next_k++; next_m_sum += pool[add_idx].rob.mk; }
        if (rem_idx != -1) { next_k--; next_m_sum -= pool[rem_idx].rob.mk; }

        // 未被覆数の変化を確認
        if (add_idx != -1) {
            for (int cell : pool[add_idx].cells) {
                if (cov_count[cell] == 0) next_uncov--;
                cov_count[cell]++;
            }
        }
        if (rem_idx != -1) {
            for (int cell : pool[rem_idx].cells) {
                cov_count[cell]--;
                if (cov_count[cell] == 0) next_uncov++;
            }
        }

        double next_energy = calc_energy(next_k, next_m_sum, next_uncov);
        double delta = next_energy - current_energy;

        bool accept = false;
        if (delta <= 0) accept = true;
        else if (temp > 0) {
            // Fast integer-based approximation or direct comparison for SA
            // Double division and exp() are very slow.
            // Since we just need a probability, we can use a lookup table or just simple math.
            if ((double)(rng() % 1000000) / 1000000.0 < exp(-delta / temp)) {
                accept = true;
            }
        }

        if (accept) {
            current_energy = next_energy;
            current_k = next_k;
            current_m_sum = next_m_sum;
            current_uncov = next_uncov;
            if (add_idx != -1) current_state[add_idx] = true;
            if (rem_idx != -1) current_state[rem_idx] = false;

            if (current_uncov == 0 && current_energy < best_energy) {
                best_energy = current_energy;
                best_state = current_state;
            }
        } else {
            // ロールバック
            if (add_idx != -1) {
                for (int cell : pool[add_idx].cells) cov_count[cell]--;
            }
            if (rem_idx != -1) {
                for (int cell : pool[rem_idx].cells) cov_count[cell]++;
            }
        }
    }

    Solution sol;
    vector<bool> used_initial(N * N, false);
    for (int i = 0; i < P; ++i) {
        if (best_state[i]) {
            Robot rob = pool[i].rob;
            int target_cell = -1;
            for (int cell : pool[i].cells) {
                if (!used_initial[cell]) {
                    target_cell = cell;
                    break;
                }
            }
            if (target_cell != -1) {
                used_initial[target_cell] = true;
                rob = shift_robot(rob, target_cell / N, target_cell % N, in);
            }
            sol.robots.push_back(rob);
        }
    }
    sol.calc_cost(in.AK, in.AM);
    return sol;
}

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

    Input in;
    in.read();

    Timer timer;
    mt19937 rng(42);

    Solution best_sol = solve_pattern_A(in, rng, timer);
    best_sol.print();

    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'void explore_policy(int, const std::vector<char>&, const std::vector<int>&, const std::vector<char>&, const std::vector<int>&, std::vector<CycleInfo>&, const Input&, std::vector<int>&, std::vector<int>&)':
./Main.cpp:143:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |     if (visited.size() < V) visited.resize(V);
      |         ~~~~~~~~~~~~~~~^~~

ジャッジ結果