提出 #76878850

---

ソースコード 拡げる

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define reps(i, a, n) for (int i = (a); i < (int)(n); ++i)

const int INF = 1e9;

struct Door {
    int a = -1;
    int b = -1;
    int g = -1;
};

struct PlacedSwitch {
    int v = -1;
    int s = -1;
};

struct Layout {
    vector<int> switch_index;
    vector<int> gate_edge_index;
};

struct SidePath {
    int main_index = -1;
    int first_vertex = -1;
    vector<int> path;
};

struct Candidate {
    vector<Door> doors;
    vector<PlacedSwitch> switches;

    vector<int> main_path;
    vector<int> path_a;
    vector<int> path_b;
    vector<int> path_c;
    set<int> skeleton_edges;

    int index_a = -1;
    int index_b = -1;
    int fixed_wall_count = 0;
    int full_isolation_wall_count = 0;
    int theoretical_t = -1;
    int selection_score = -1;
    int exact_t = -1;
    bool valid = false;
};

struct GraphEdge {
    int u = -1;
    int v = -1;
};

struct TreeState {
    vector<char> in_tree;
    vector<vector<int>> tree_adj;

    Candidate best_raw_candidate;
    int score = -INF;
    bool valid = false;
};

struct Solver {
    static constexpr double RANDOM_END_MS = 400.0;
    static constexpr double ANNEAL_END_MS = 1350.0;
    static constexpr double EXACT_END_MS = 1900.0;
    static constexpr int SA_SEED_COUNT = 4;
    static constexpr int RAW_POOL_LIMIT = 100;
    static constexpr int EXACT_CANDIDATE_LIMIT = 50;
    static constexpr int SA_EXCESS_WALL_PENALTY = 2;

    int N = 0;
    int M = 0;
    int K = 0;
    vector<string> c;
    vector<vector<int>> adj;
    vector<GraphEdge> all_edges;
    vector<vector<int>> edge_id;
    vector<uint64_t> edge_zobrist;
    vector<int> deg;
    vector<int> open_cells;
    uint64_t board_hash = 0;
    chrono::steady_clock::time_point start_time;

    long long generated_tree_count = 0;
    long long generated_side_path_count = 0;
    long long examined_pair_count = 0;
    long long detailed_pair_count = 0;
    long long valid_candidate_count = 0;
    long long exact_evaluated_count = 0;
    long long generated_raw_candidate_count = 0;
    long long lazy_repair_attempt_count = 0;
    long long lazy_repair_success_count = 0;
    mutable long long exact_bfs_count = 0;
    long long random_phase_tree_count = 0;
    long long sa_iteration_count = 0;
    long long sa_valid_neighbor_count = 0;
    long long sa_accepted_count = 0;
    long long sa_worse_accepted_count = 0;
    long long sa_rejected_count = 0;
    long long sa_best_update_count = 0;
    int sa_initial_best_score = -INF;
    int sa_final_best_score = -INF;
    vector<string> repair_logs;

    int id(int r, int col) const {
        return r * N + col;
    }

    pair<int, int> rc(int v) const {
        return {v / N, v % N};
    }

    int start_id() const {
        return 0;
    }

    int goal_id() const {
        return N * N - 1;
    }

    bool is_open_cell(int v) const {
        auto [r, col] = rc(v);
        return 0 <= r && r < N && 0 <= col && col < N && c[r][col] == '.';
    }

    int edge_key(int a, int b) const {
        if (a > b) swap(a, b);
        return a * N * N + b;
    }

    Door make_door(int a, int b, int g) const {
        return Door{a, b, g};
    }

    double elapsed_ms() const {
        auto now = chrono::steady_clock::now();
        return chrono::duration_cast<chrono::microseconds>(now - start_time).count() / 1000.0;
    }

    void read_input() {
        cin >> N >> M >> K;
        c.resize(N);
        rep(i, N) cin >> c[i];

        board_hash = 1469598103934665603ULL;
        rep(i, N) {
            for (char ch : c[i]) {
                board_hash ^= (uint64_t)(unsigned char)ch;
                board_hash *= 1099511628211ULL;
            }
        }
    }

    void build_graph() {
        adj.assign(N * N, {});
        edge_id.assign(N * N, vector<int>(N * N, -1));
        all_edges.clear();
        deg.assign(N * N, 0);
        open_cells.clear();
        const int dr[4] = {-1, 1, 0, 0};
        const int dc[4] = {0, 0, -1, 1};
        rep(r, N) rep(col, N) {
            if (c[r][col] == '#') continue;
            int v = id(r, col);
            open_cells.push_back(v);
            rep(dir, 4) {
                int nr = r + dr[dir];
                int nc = col + dc[dir];
                if (0 <= nr && nr < N && 0 <= nc && nc < N && c[nr][nc] == '.') {
                    adj[v].push_back(id(nr, nc));
                }
            }
            deg[v] = (int)adj[v].size();
        }
        rep(v, N * N) {
            for (int to : adj[v]) {
                if (v < to) {
                    int eid = (int)all_edges.size();
                    all_edges.push_back({v, to});
                    edge_id[v][to] = edge_id[to][v] = eid;
                }
            }
        }
        edge_zobrist.assign(all_edges.size(), 0);
        uint64_t z = board_hash ^ 0x9e3779b97f4a7c15ULL;
        rep(i, (int)all_edges.size()) {
            z ^= z << 7;
            z ^= z >> 9;
            z *= 11995408973635179863ULL;
            edge_zobrist[i] = z;
        }
    }

    bool make_layout(int edge_len, int switch_count, Layout& layout) const {
        if (edge_len < switch_count) return false;
        layout.switch_index.assign(switch_count, 0);
        layout.gate_edge_index.assign(max(0, switch_count - 1), 0);
        rep(t, switch_count) {
            layout.switch_index[t] = edge_len - (switch_count - 1 - t);
        }
        rep(t, switch_count - 1) {
            layout.gate_edge_index[t] = layout.switch_index[t + 1] - 1;
            if (layout.gate_edge_index[t] < 0) return false;
        }
        return true;
    }

    bool make_before_gate_layout(int edge_len, int switch_count, Layout& layout) const {
        if (edge_len < switch_count) return false;
        layout.switch_index.assign(switch_count, 0);
        layout.gate_edge_index.assign(switch_count, 0);
        rep(t, switch_count) {
            layout.switch_index[t] = edge_len - (switch_count - 1 - t);
            layout.gate_edge_index[t] = layout.switch_index[t] - 1;
            if (layout.gate_edge_index[t] < 0) return false;
        }
        return true;
    }

    vector<int> choose_c_gate_edges(int edge_len) const {
        if (edge_len < 9) return {};
        vector<int> edges;
        rep(i, 8) edges.push_back(i);
        edges.push_back(edge_len - 1);
        rep(i, (int)edges.size() - 1) {
            if (edges[i] >= edges[i + 1]) return {};
        }
        return edges;
    }

    void add_path_edges(const vector<int>& path, set<int>& edges) const {
        rep(i, (int)path.size() - 1) edges.insert(edge_key(path[i], path[i + 1]));
    }

    void add_path_vertices(const vector<int>& path, vector<char>& used) const {
        for (int v : path) used[v] = 1;
    }

    void add_gate_door(vector<Door>& doors, const vector<int>& path, int edge_index, int type) const {
        doors.push_back(make_door(path[edge_index], path[edge_index + 1], type));
    }

    uint64_t path_hash(const vector<int>& path) const {
        uint64_t h = 1469598103934665603ULL;
        for (int v : path) {
            h ^= (uint64_t)(v + 1009);
            h *= 1099511628211ULL;
        }
        return h;
    }

    uint64_t candidate_hash(const Candidate& cand) const {
        uint64_t h = path_hash(cand.main_path);
        h ^= path_hash(cand.path_a) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
        h ^= path_hash(cand.path_b) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
        h ^= (uint64_t)(cand.index_a + 10007) * 1000003ULL;
        h ^= (uint64_t)(cand.index_b + 10009) * 9176ULL;
        return h;
    }

    vector<int> make_prefix_lengths(int full_length, int minimum_length) const {
        vector<int> vals;
        if (full_length < minimum_length) return vals;
        vector<int> raw = {
            full_length,
            full_length - 2,
            full_length - 4,
            full_length - 6,
            full_length - 8,
            full_length - 12,
            (full_length * 3) / 4,
            minimum_length
        };
        for (int v : raw) {
            if (minimum_length <= v && v <= full_length) vals.push_back(v);
        }
        sort(vals.begin(), vals.end(), greater<int>());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        return vals;
    }

    vector<vector<int>> generate_random_tree(mt19937& rng) const {
        vector<vector<int>> shuffled = adj;
        for (int v : open_cells) shuffle(shuffled[v].begin(), shuffled[v].end(), rng);

        vector<vector<int>> tree(N * N);
        vector<char> visited(N * N, 0);
        int root = open_cells[(int)(rng() % open_cells.size())];
        vector<pair<int, int>> st;
        st.push_back({root, 0});
        visited[root] = 1;
        int seen = 1;

        while (!st.empty()) {
            int v = st.back().first;
            int& it = st.back().second;
            if (it == (int)shuffled[v].size()) {
                st.pop_back();
                continue;
            }
            int to = shuffled[v][it++];
            if (visited[to]) continue;
            visited[to] = 1;
            ++seen;
            tree[v].push_back(to);
            tree[to].push_back(v);
            st.push_back({to, 0});
        }
        if (seen != (int)open_cells.size()) return {};
        return tree;
    }

    TreeState generate_random_tree_state(mt19937& rng) const {
        TreeState state;
        state.in_tree.assign(all_edges.size(), 0);
        state.tree_adj.assign(N * N, {});

        vector<vector<int>> shuffled = adj;
        for (int v : open_cells) shuffle(shuffled[v].begin(), shuffled[v].end(), rng);

        vector<char> visited(N * N, 0);
        int root = open_cells[(int)(rng() % open_cells.size())];
        vector<pair<int, int>> st;
        st.push_back({root, 0});
        visited[root] = 1;
        int seen = 1;
        int tree_edges = 0;

        while (!st.empty()) {
            int v = st.back().first;
            int& it = st.back().second;
            if (it == (int)shuffled[v].size()) {
                st.pop_back();
                continue;
            }
            int to = shuffled[v][it++];
            if (visited[to]) continue;
            int eid = edge_id[v][to];
            if (eid < 0) continue;
            visited[to] = 1;
            ++seen;
            ++tree_edges;
            state.in_tree[eid] = 1;
            state.tree_adj[v].push_back(to);
            state.tree_adj[to].push_back(v);
            st.push_back({to, 0});
        }

        if (seen != (int)open_cells.size() || tree_edges != (int)open_cells.size() - 1) {
            state.valid = false;
            return state;
        }
        state.valid = true;
        return state;
    }

    uint64_t tree_hash(const TreeState& state) const {
        uint64_t h = 0;
        rep(eid, (int)state.in_tree.size()) {
            if (state.in_tree[eid]) h ^= edge_zobrist[eid];
        }
        return h;
    }

    void add_tree_edge(TreeState& state, int eid) const {
        if (eid < 0 || eid >= (int)all_edges.size()) return;
        if (state.in_tree[eid]) return;
        int u = all_edges[eid].u;
        int v = all_edges[eid].v;
        state.in_tree[eid] = 1;
        state.tree_adj[u].push_back(v);
        state.tree_adj[v].push_back(u);
    }

    void remove_tree_edge(TreeState& state, int eid) const {
        if (eid < 0 || eid >= (int)all_edges.size()) return;
        if (!state.in_tree[eid]) return;
        int u = all_edges[eid].u;
        int v = all_edges[eid].v;
        state.in_tree[eid] = 0;
        auto erase_one = [](vector<int>& xs, int value) {
            auto it = find(xs.begin(), xs.end(), value);
            if (it != xs.end()) xs.erase(it);
        };
        erase_one(state.tree_adj[u], v);
        erase_one(state.tree_adj[v], u);
    }

    vector<int> get_tree_path_edge_ids(const vector<vector<int>>& tree_adj, int src, int dst) const {
        vector<int> parent(N * N, -1), parent_edge(N * N, -1);
        queue<int> que;
        parent[src] = src;
        que.push(src);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            if (v == dst) break;
            for (int to : tree_adj[v]) {
                if (parent[to] != -1) continue;
                parent[to] = v;
                parent_edge[to] = edge_id[v][to];
                que.push(to);
            }
        }
        if (parent[dst] == -1) return {};
        vector<int> path_edges;
        for (int v = dst; v != src; v = parent[v]) path_edges.push_back(parent_edge[v]);
        reverse(path_edges.begin(), path_edges.end());
        return path_edges;
    }

    int choose_add_edge(const TreeState& state, mt19937& rng) const {
        rep(attempt, 60) {
            int eid = (int)(rng() % all_edges.size());
            if (!state.in_tree[eid]) return eid;
        }
        return -1;
    }

    vector<int> tree_path(const vector<vector<int>>& tree, int src, int dst) const {
        vector<int> parent(N * N, -1);
        queue<int> que;
        parent[src] = src;
        que.push(src);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            if (v == dst) break;
            for (int to : tree[v]) {
                if (parent[to] != -1) continue;
                parent[to] = v;
                que.push(to);
            }
        }
        if (parent[dst] == -1) return {};
        vector<int> path;
        for (int v = dst; v != src; v = parent[v]) path.push_back(v);
        path.push_back(src);
        reverse(path.begin(), path.end());
        return path;
    }

    vector<SidePath> collect_side_paths(const vector<vector<int>>& tree,
                                        const vector<int>& main_path,
                                        const vector<int>& main_index) {
        vector<SidePath> sides;
        vector<char> on_main(N * N, 0);
        for (int v : main_path) on_main[v] = 1;

        rep(i, (int)main_path.size()) {
            int root = main_path[i];
            int prev_main = (i > 0 ? main_path[i - 1] : -1);
            int next_main = (i + 1 < (int)main_path.size() ? main_path[i + 1] : -1);
            for (int first : tree[root]) {
                if (first == prev_main || first == next_main) continue;
                if (on_main[first]) continue;

                vector<int> parent(N * N, -1), dist(N * N, -1);
                queue<int> que;
                parent[first] = root;
                dist[first] = 1;
                que.push(first);
                int far = first;
                while (!que.empty()) {
                    int v = que.front();
                    que.pop();
                    if (dist[v] > dist[far]) far = v;
                    for (int to : tree[v]) {
                        if (to == parent[v] || on_main[to]) continue;
                        parent[to] = v;
                        dist[to] = dist[v] + 1;
                        que.push(to);
                    }
                }

                vector<int> path;
                for (int v = far; v != root; v = parent[v]) path.push_back(v);
                path.push_back(root);
                reverse(path.begin(), path.end());
                if ((int)path.size() >= 2) {
                    sides.push_back(SidePath{i, first, path});
                }
            }
        }
        (void)main_index;
        generated_side_path_count += (long long)sides.size();
        return sides;
    }

    int theoretical_time(const Candidate& cand, const Layout& layout_a, const Layout& layout_b) const {
        vector<int> a_dist(5), b_dist(4);
        rep(i, 5) a_dist[i] = layout_a.switch_index[i];
        rep(i, 4) b_dist[i] = layout_b.switch_index[i];
        struct Pos {
            int side;
            int idx;
        };
        vector<Pos> seq = {
            {0, 0}, {1, 0}, {0, 1}, {1, 1}, {0, 2}, {1, 2}, {0, 3}, {1, 3}, {0, 4},
            {1, 3}, {0, 3}, {1, 2}, {0, 2}, {1, 1}, {0, 1}, {1, 0}, {0, 0}
        };
        auto main_pos = [&](const Pos& p) {
            return p.side == 0 ? cand.index_a : cand.index_b;
        };
        auto branch_dist = [&](const Pos& p) {
            return p.side == 0 ? a_dist[p.idx] : b_dist[p.idx];
        };

        int main_edges = (int)cand.main_path.size() - 1;
        long long total = cand.index_a + a_dist[0];
        reps(i, 1, (int)seq.size()) {
            total += branch_dist(seq[i - 1]);
            total += abs(main_pos(seq[i - 1]) - main_pos(seq[i]));
            total += branch_dist(seq[i]);
        }
        total += a_dist[0] + (main_edges - cand.index_a);
        total += 17;
        return (int)total;
    }

    bool build_candidate(const vector<int>& main_path,
                         const SidePath& side_a,
                         const SidePath& side_b,
                         int len_a,
                         int len_b,
                         Candidate& cand) const {
        if (len_a < 5 || len_b < 4) return false;
        if ((int)side_a.path.size() <= len_a || (int)side_b.path.size() <= len_b) return false;
        int index_a = side_a.main_index;
        int index_b = side_b.main_index;
        int hi = max(index_a, index_b);
        int c_len = (int)main_path.size() - 1 - hi;
        if (c_len < 9) return false;
        if (index_a == index_b && side_a.first_vertex == side_b.first_vertex) return false;

        cand = Candidate{};
        cand.main_path = main_path;
        cand.index_a = index_a;
        cand.index_b = index_b;
        cand.path_a.assign(side_a.path.begin(), side_a.path.begin() + len_a + 1);
        cand.path_b.assign(side_b.path.begin(), side_b.path.begin() + len_b + 1);
        cand.path_c.assign(main_path.begin() + hi, main_path.end());

        set<int> skeleton_edges;
        vector<char> skeleton_vertices(N * N, 0);
        add_path_edges(cand.main_path, skeleton_edges);
        add_path_edges(cand.path_a, skeleton_edges);
        add_path_edges(cand.path_b, skeleton_edges);
        add_path_vertices(cand.main_path, skeleton_vertices);
        add_path_vertices(cand.path_a, skeleton_vertices);
        add_path_vertices(cand.path_b, skeleton_vertices);
        cand.skeleton_edges = skeleton_edges;

        set<int> fixed_edges;
        rep(v, N * N) {
            if (!skeleton_vertices[v]) continue;
            for (int to : adj[v]) {
                int ek = edge_key(v, to);
                if (!skeleton_edges.count(ek)) fixed_edges.insert(ek);
            }
        }

        Layout layout_a, layout_b;
        if (!make_layout(len_a, 5, layout_a)) return false;
        if (!make_before_gate_layout(len_b, 4, layout_b)) return false;
        vector<int> c_gate_edges = choose_c_gate_edges(c_len);
        if (c_gate_edges.empty()) return false;

        cand.doors.clear();
        rep(i, 4) add_gate_door(cand.doors, cand.path_a, layout_a.gate_edge_index[i], 4 * (i + 1) + 1);
        rep(i, 4) add_gate_door(cand.doors, cand.path_b, layout_b.gate_edge_index[i], 4 * i + 3);
        rep(i, 8) add_gate_door(cand.doors, cand.path_c, c_gate_edges[i], 2 * (i + 1));
        add_gate_door(cand.doors, cand.path_c, c_gate_edges.back(), 19);
        cand.fixed_wall_count = 0;
        cand.full_isolation_wall_count = (int)fixed_edges.size();
        if ((int)cand.doors.size() > M) return false;

        rep(i, 5) cand.switches.push_back({cand.path_a[layout_a.switch_index[i]], 2 * i + 1});
        rep(i, 4) cand.switches.push_back({cand.path_b[layout_b.switch_index[i]], 2 * (i + 1)});
        cand.theoretical_t = theoretical_time(cand, layout_a, layout_b);
        cand.selection_score = cand.theoretical_t - SA_EXCESS_WALL_PENALTY * max(0, cand.full_isolation_wall_count - 33);
        cand.valid = validate_candidate(cand);
        return cand.valid;
    }

    void keep_top_candidate(vector<Candidate>& top_candidates,
                            set<uint64_t>& seen,
                            Candidate cand,
                            int keep_count) const {
        uint64_t h = candidate_hash(cand);
        if (!seen.insert(h).second) return;
        top_candidates.push_back(std::move(cand));
        sort(top_candidates.begin(), top_candidates.end(), [](const Candidate& lhs, const Candidate& rhs) {
            if (lhs.selection_score != rhs.selection_score) return lhs.selection_score > rhs.selection_score;
            return lhs.theoretical_t > rhs.theoretical_t;
        });
        if ((int)top_candidates.size() > keep_count) top_candidates.resize(keep_count);
    }

    void process_tree(const vector<vector<int>>& tree,
                      vector<Candidate>& top_candidates,
                      set<uint64_t>& seen_candidates) {
        vector<int> main_path = tree_path(tree, start_id(), goal_id());
        if (main_path.empty()) return;
        vector<int> main_index(N * N, -1);
        rep(i, (int)main_path.size()) main_index[main_path[i]] = i;

        vector<SidePath> sides = collect_side_paths(tree, main_path, main_index);
        if ((int)sides.size() < 2) return;

        struct PairUpper {
            int score = 0;
            int x = -1;
            int y = -1;
        };
        vector<PairUpper> pairs;
        int main_edges = (int)main_path.size() - 1;
        rep(i, (int)sides.size()) reps(j, i + 1, (int)sides.size()) {
            ++examined_pair_count;
            const SidePath& x = sides[i];
            const SidePath& y = sides[j];
            if (x.main_index == y.main_index && x.first_vertex == y.first_vertex) continue;
            int lo = min(x.main_index, y.main_index);
            int hi = max(x.main_index, y.main_index);
            int c_len = main_edges - hi;
            if (c_len < 9) continue;
            int len_x = (int)x.path.size() - 1;
            int len_y = (int)y.path.size() - 1;
            int len_a = max(len_x, len_y);
            int len_b = min(len_x, len_y);
            if (len_a < 5 || len_b < 4) continue;
            int stem_len = lo;
            int connector_len = hi - lo;
            int rough = stem_len + 17 * connector_len + c_len + 18 * len_a + 16 * len_b;
            pairs.push_back({rough, i, j});
        }
        sort(pairs.begin(), pairs.end(), [](const PairUpper& lhs, const PairUpper& rhs) {
            return lhs.score > rhs.score;
        });
        if ((int)pairs.size() > 200) pairs.resize(200);

        for (const PairUpper& pu : pairs) {
            const SidePath& x = sides[pu.x];
            const SidePath& y = sides[pu.y];
            vector<pair<const SidePath*, const SidePath*>> assignments = {{&x, &y}, {&y, &x}};
            for (auto [pa, pb] : assignments) {
                vector<int> a_lengths = make_prefix_lengths((int)pa->path.size() - 1, 5);
                vector<int> b_lengths = make_prefix_lengths((int)pb->path.size() - 1, 4);
                for (int la : a_lengths) for (int lb : b_lengths) {
                    ++detailed_pair_count;
                    Candidate cand;
                    if (!build_candidate(main_path, *pa, *pb, la, lb, cand)) continue;
                    ++generated_raw_candidate_count;
                    ++valid_candidate_count;
                    keep_top_candidate(top_candidates, seen_candidates, std::move(cand), 60);
                }
            }
        }
    }

    vector<int> make_fast_prefix_lengths(int full_length, int minimum_length) const {
        vector<int> vals;
        if (full_length < minimum_length) return vals;
        vector<int> raw = {full_length, full_length - 4, full_length - 8, minimum_length};
        for (int v : raw) {
            if (minimum_length <= v && v <= full_length) vals.push_back(v);
        }
        sort(vals.begin(), vals.end(), greater<int>());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        return vals;
    }

    bool evaluate_tree_fast(const vector<vector<int>>& tree,
                            Candidate& best_candidate,
                            int& best_score) {
        best_score = -INF;
        vector<int> main_path = tree_path(tree, start_id(), goal_id());
        if (main_path.empty()) return false;
        vector<int> main_index(N * N, -1);
        rep(i, (int)main_path.size()) main_index[main_path[i]] = i;

        vector<SidePath> sides = collect_side_paths(tree, main_path, main_index);
        if ((int)sides.size() < 2) return false;

        struct PairUpper {
            int score = 0;
            int x = -1;
            int y = -1;
        };
        vector<PairUpper> pairs;
        int main_edges = (int)main_path.size() - 1;
        rep(i, (int)sides.size()) reps(j, i + 1, (int)sides.size()) {
            ++examined_pair_count;
            const SidePath& x = sides[i];
            const SidePath& y = sides[j];
            if (x.main_index == y.main_index && x.first_vertex == y.first_vertex) continue;
            int lo = min(x.main_index, y.main_index);
            int hi = max(x.main_index, y.main_index);
            int c_len = main_edges - hi;
            if (c_len < 9) continue;
            int len_x = (int)x.path.size() - 1;
            int len_y = (int)y.path.size() - 1;
            int len_a = max(len_x, len_y);
            int len_b = min(len_x, len_y);
            if (len_a < 5 || len_b < 4) continue;
            int stem_len = lo;
            int connector_len = hi - lo;
            int rough = stem_len + 17 * connector_len + c_len + 18 * len_a + 16 * len_b;
            pairs.push_back({rough, i, j});
        }
        if (pairs.empty()) return false;
        sort(pairs.begin(), pairs.end(), [](const PairUpper& lhs, const PairUpper& rhs) {
            return lhs.score > rhs.score;
        });
        if ((int)pairs.size() > 40) pairs.resize(40);

        for (const PairUpper& pu : pairs) {
            const SidePath& x = sides[pu.x];
            const SidePath& y = sides[pu.y];
            vector<pair<const SidePath*, const SidePath*>> assignments = {{&x, &y}, {&y, &x}};
            for (auto [pa, pb] : assignments) {
                vector<int> a_lengths = make_fast_prefix_lengths((int)pa->path.size() - 1, 5);
                vector<int> b_lengths = make_fast_prefix_lengths((int)pb->path.size() - 1, 4);
                for (int la : a_lengths) for (int lb : b_lengths) {
                    ++detailed_pair_count;
                    Candidate cand;
                    if (!build_candidate(main_path, *pa, *pb, la, lb, cand)) continue;
                    ++generated_raw_candidate_count;
                    ++valid_candidate_count;
                    if (cand.selection_score > best_score) {
                        best_score = cand.selection_score;
                        best_candidate = std::move(cand);
                    }
                }
            }
        }
        return best_score > -INF;
    }

    int door_type_between(const vector<vector<int>>& door_h,
                          const vector<vector<int>>& door_v,
                          int a,
                          int b) const {
        auto [ar, ac] = rc(a);
        auto [br, bc] = rc(b);
        if (ar == br) return door_v[ar][min(ac, bc)];
        return door_h[min(ar, br)][ac];
    }

    struct EvalResult {
        int shortest_time = 0;
        vector<int> route_states;
    };

    EvalResult calc_T_with_route(const Candidate& cand, bool restore_route) const {
        ++exact_bfs_count;
        vector<vector<int>> door_h(N - 1, vector<int>(N, -1));
        vector<vector<int>> door_v(N, vector<int>(N - 1, -1));
        for (const Door& door : cand.doors) {
            auto [ar, ac] = rc(door.a);
            auto [br, bc] = rc(door.b);
            if (ar == br) door_v[ar][min(ac, bc)] = door.g;
            else door_h[min(ar, br)][ac] = door.g;
        }

        vector<int> sw(N * N, -1);
        for (const PlacedSwitch& s : cand.switches) sw[s.v] = s.s;

        auto is_open_door = [](int g, int mask) {
            if (g == -1) return true;
            int k = g / 2;
            return ((mask >> k) & 1) == (g & 1);
        };

        const int V = N * N;
        const int state_count = (1 << K) * V;
        vector<int> dist(state_count, -1);
        vector<int> parent;
        if (restore_route) parent.assign(state_count, -2);
        queue<int> que;
        dist[start_id()] = 0;
        if (restore_route) parent[start_id()] = -1;
        que.push(start_id());
        while (!que.empty()) {
            int state = que.front();
            que.pop();
            int mask = state / V;
            int v = state % V;
            int d = dist[state];
            if (v == goal_id()) {
                EvalResult result;
                result.shortest_time = d;
                if (restore_route) {
                    for (int cur = state; cur != -1; cur = parent[cur]) result.route_states.push_back(cur);
                    reverse(result.route_states.begin(), result.route_states.end());
                }
                return result;
            }

            for (int to : adj[v]) {
                int g = door_type_between(door_h, door_v, v, to);
                if (!is_open_door(g, mask)) continue;
                int ns = mask * V + to;
                if (dist[ns] == -1) {
                    dist[ns] = d + 1;
                    if (restore_route) parent[ns] = state;
                    que.push(ns);
                }
            }

            if (sw[v] != -1) {
                int nmask = mask ^ (1 << sw[v]);
                int ns = nmask * V + v;
                if (dist[ns] == -1) {
                    dist[ns] = d + 1;
                    if (restore_route) parent[ns] = state;
                    que.push(ns);
                }
            }
        }
        return EvalResult{};
    }

    int calc_T(const Candidate& cand) const {
        return calc_T_with_route(cand, false).shortest_time;
    }

    bool has_door_on_edge(const Candidate& cand, int ek) const {
        for (const Door& door : cand.doors) {
            if (edge_key(door.a, door.b) == ek) return true;
        }
        return false;
    }

    Door find_first_non_skeleton_edge(const Candidate& cand, const vector<int>& route_states) const {
        const int V = N * N;
        reps(i, 1, (int)route_states.size()) {
            int prev_v = route_states[i - 1] % V;
            int next_v = route_states[i] % V;
            if (prev_v == next_v) continue;
            int ek = edge_key(prev_v, next_v);
            if (!cand.skeleton_edges.count(ek)) return make_door(prev_v, next_v, 1);
        }
        return Door{};
    }

    bool add_fixed_wall(Candidate& cand, int a, int b) const {
        bool adjacent = false;
        for (int to : adj[a]) {
            if (to == b) adjacent = true;
        }
        if (!adjacent) return false;
        int ek = edge_key(a, b);
        if (cand.skeleton_edges.count(ek)) return false;
        if (has_door_on_edge(cand, ek)) return false;
        if (cand.fixed_wall_count >= 33) return false;
        if ((int)cand.doors.size() >= M) return false;
        cand.doors.push_back(make_door(a, b, 1));
        ++cand.fixed_wall_count;
        return true;
    }

    bool lazy_repair_candidate(const Candidate& raw, Candidate& repaired, double deadline_ms) {
        Candidate cand = raw;
        int first_t = -1;
        for (int fixed = 0; fixed <= 33; ++fixed) {
            EvalResult result = calc_T_with_route(cand, true);
            if (elapsed_ms() >= deadline_ms) return false;
            if (first_t == -1) first_t = result.shortest_time;
            if (result.shortest_time <= 0) return false;
            Door shortcut = find_first_non_skeleton_edge(cand, result.route_states);
            if (shortcut.a == -1) {
                cand.exact_t = result.shortest_time;
                cand.fixed_wall_count = fixed;
                cand.valid = validate_candidate(cand);
                if (!cand.valid) return false;
                repaired = std::move(cand);
                if ((int)repair_logs.size() < 6) {
                    repair_logs.push_back("repair_before_T=" + to_string(first_t) +
                                          " added_fixed=" + to_string(fixed) +
                                          " repair_after_T=" + to_string(repaired.exact_t) +
                                          " success=1");
                }
                return true;
            }
            if (fixed == 33) {
                if ((int)repair_logs.size() < 6) {
                    repair_logs.push_back("repair_before_T=" + to_string(first_t) +
                                          " added_fixed=33 repair_after_T=" + to_string(result.shortest_time) +
                                          " success=0");
                }
                return false;
            }
            if (!add_fixed_wall(cand, shortcut.a, shortcut.b)) return false;
            if (!validate_candidate(cand)) return false;
        }
        return false;
    }

    vector<int> bfs_dist(int src) const {
        vector<int> dist(N * N, -1);
        queue<int> que;
        dist[src] = 0;
        que.push(src);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int to : adj[v]) {
                if (dist[to] != -1) continue;
                dist[to] = dist[v] + 1;
                que.push(to);
            }
        }
        return dist;
    }

    Candidate make_fallback() const {
        Candidate cand;
        cand.valid = true;
        for (int to : adj[goal_id()]) cand.doors.push_back(make_door(goal_id(), to, 19));
        vector<int> ds = bfs_dist(start_id());
        vector<int> dg = bfs_dist(goal_id());
        int best_v = start_id();
        int best_score = -1;
        rep(v, N * N) {
            if (!is_open_cell(v) || v == goal_id()) continue;
            if (ds[v] < 0 || dg[v] < 0) continue;
            int score = ds[v] + dg[v];
            if (score > best_score) {
                best_score = score;
                best_v = v;
            }
        }
        cand.switches.push_back({best_v, 9});
        cand.exact_t = calc_T(cand);
        cand.theoretical_t = cand.exact_t;
        return cand;
    }

    bool validate_candidate(const Candidate& cand) const {
        if ((int)cand.doors.size() > M) return false;
        set<int> door_edges;
        for (const Door& door : cand.doors) {
            if (door.g <= 0 || door.g >= 2 * K) return false;
            if (!is_open_cell(door.a) || !is_open_cell(door.b)) return false;
            bool adjacent = false;
            for (int to : adj[door.a]) if (to == door.b) adjacent = true;
            if (!adjacent) return false;
            int ek = edge_key(door.a, door.b);
            if (door_edges.count(ek)) return false;
            door_edges.insert(ek);
        }
        set<int> switch_cells;
        for (const PlacedSwitch& sw : cand.switches) {
            if (sw.s <= 0 || sw.s >= K) return false;
            if (!is_open_cell(sw.v)) return false;
            if (switch_cells.count(sw.v)) return false;
            switch_cells.insert(sw.v);
        }
        return true;
    }

    void keep_seed_tree(vector<TreeState>& seeds, set<uint64_t>& seen_trees, TreeState state) const {
        uint64_t h = tree_hash(state);
        if (!seen_trees.insert(h).second) return;
        seeds.push_back(std::move(state));
        sort(seeds.begin(), seeds.end(), [](const TreeState& lhs, const TreeState& rhs) {
            return lhs.score > rhs.score;
        });
        if ((int)seeds.size() > SA_SEED_COUNT) seeds.resize(SA_SEED_COUNT);
    }

    void keep_raw_candidate(vector<Candidate>& raw_pool,
                            set<uint64_t>& seen_raw,
                            Candidate cand) const {
        keep_top_candidate(raw_pool, seen_raw, std::move(cand), RAW_POOL_LIMIT);
    }

    void anneal_from_seed(const TreeState& seed,
                          int chain_index,
                          double chain_start_ms,
                          double chain_end_ms,
                          mt19937& rng,
                          vector<Candidate>& raw_pool,
                          set<uint64_t>& seen_raw) {
        TreeState current = seed;
        TreeState best_in_chain = seed;
        int chain_iterations = 0;
        int chain_accepted = 0;
        double start_temperature = max(50.0, abs(current.score) * 0.05);
        const double end_temperature = 1.0;
        uniform_real_distribution<double> dist01(0.0, 1.0);

        while (elapsed_ms() < chain_end_ms) {
            ++sa_iteration_count;
            ++chain_iterations;
            int add_eid = choose_add_edge(current, rng);
            if (add_eid == -1) continue;
            int u = all_edges[add_eid].u;
            int v = all_edges[add_eid].v;
            vector<int> path_edges = get_tree_path_edge_ids(current.tree_adj, u, v);
            if (path_edges.empty()) continue;
            int remove_eid = path_edges[(int)(rng() % path_edges.size())];

            int previous_score = current.score;
            remove_tree_edge(current, remove_eid);
            add_tree_edge(current, add_eid);

            Candidate next_candidate;
            int next_score = -INF;
            bool valid = evaluate_tree_fast(current.tree_adj, next_candidate, next_score);
            if (valid) {
                ++sa_valid_neighbor_count;
                keep_raw_candidate(raw_pool, seen_raw, next_candidate);
            }

            bool accept = false;
            if (valid) {
                int diff = next_score - previous_score;
                double progress = (elapsed_ms() - chain_start_ms) / max(1.0, chain_end_ms - chain_start_ms);
                progress = min(1.0, max(0.0, progress));
                double temperature = start_temperature * pow(end_temperature / start_temperature, progress);
                if (diff >= 0) {
                    accept = true;
                } else {
                    accept = dist01(rng) < exp((double)diff / max(1e-9, temperature));
                }
            }

            if (accept) {
                current.score = next_score;
                current.best_raw_candidate = next_candidate;
                current.valid = true;
                ++sa_accepted_count;
                ++chain_accepted;
                if (next_score < previous_score) ++sa_worse_accepted_count;
                if (current.score > best_in_chain.score) {
                    best_in_chain = current;
                    ++sa_best_update_count;
                }
            } else {
                remove_tree_edge(current, add_eid);
                add_tree_edge(current, remove_eid);
                ++sa_rejected_count;
            }
        }
        keep_raw_candidate(raw_pool, seen_raw, best_in_chain.best_raw_candidate);
        sa_final_best_score = max(sa_final_best_score, best_in_chain.score);
        cerr << "chain_index=" << chain_index
             << " chain_initial_score=" << seed.score
             << " chain_final_current_score=" << current.score
             << " chain_best_score=" << best_in_chain.score
             << " chain_iteration_count=" << chain_iterations
             << " chain_accepted_count=" << chain_accepted
             << '\n';
    }

    Candidate choose_best_candidate() {
        mt19937 rng((uint32_t)(board_hash ^ (board_hash >> 32)));
        vector<Candidate> raw_candidate_pool;
        set<uint64_t> seen_raw_candidates;
        vector<TreeState> seed_trees;
        set<uint64_t> seen_seed_trees;

        while (elapsed_ms() < RANDOM_END_MS) {
            TreeState state = generate_random_tree_state(rng);
            ++generated_tree_count;
            ++random_phase_tree_count;
            if (!state.valid) continue;
            Candidate best_raw;
            int fast_score = -INF;
            if (!evaluate_tree_fast(state.tree_adj, best_raw, fast_score)) continue;
            state.best_raw_candidate = best_raw;
            state.score = fast_score;
            state.valid = true;
            keep_seed_tree(seed_trees, seen_seed_trees, state);
            keep_raw_candidate(raw_candidate_pool, seen_raw_candidates, std::move(best_raw));
        }
        int sa_seed_count = (int)seed_trees.size();
        if (!seed_trees.empty()) sa_initial_best_score = seed_trees.front().score;
        sa_final_best_score = sa_initial_best_score;

        double anneal_start = elapsed_ms();
        double remaining = max(0.0, ANNEAL_END_MS - anneal_start);
        rep(i, (int)seed_trees.size()) {
            if (elapsed_ms() >= ANNEAL_END_MS) break;
            double chain_start = elapsed_ms();
            double chain_span = remaining / max(1, (int)seed_trees.size());
            double chain_end = min(ANNEAL_END_MS, chain_start + chain_span);
            if (i + 1 == (int)seed_trees.size()) chain_end = ANNEAL_END_MS;
            anneal_from_seed(seed_trees[i], i, chain_start, chain_end, rng, raw_candidate_pool, seen_raw_candidates);
        }

        Candidate best;
        best.exact_t = -1;
        sort(raw_candidate_pool.begin(), raw_candidate_pool.end(), [](const Candidate& lhs, const Candidate& rhs) {
            if (lhs.selection_score != rhs.selection_score) return lhs.selection_score > rhs.selection_score;
            return lhs.theoretical_t > rhs.theoretical_t;
        });
        int exact_limit = min<int>(EXACT_CANDIDATE_LIMIT, raw_candidate_pool.size());
        rep(i, exact_limit) {
            if (elapsed_ms() > EXACT_END_MS && best.exact_t >= 0) break;
            ++lazy_repair_attempt_count;
            Candidate repaired;
            bool ok = lazy_repair_candidate(raw_candidate_pool[i], repaired, EXACT_END_MS);
            ++exact_evaluated_count;
            if (!ok) continue;
            ++lazy_repair_success_count;
            if (repaired.exact_t > best.exact_t) best = std::move(repaired);
        }

        if (best.exact_t <= 0) best = make_fallback();
        if (!validate_candidate(best)) best = make_fallback();

        int main_path_length = max(0, (int)best.main_path.size() - 1);
        int stem_length = max(0, min(best.index_a, best.index_b));
        int connector_length = (best.index_a >= 0 && best.index_b >= 0) ? abs(best.index_a - best.index_b) : 0;
        int c_length = max(0, (int)best.path_c.size() - 1);
        double acceptance_rate = sa_iteration_count == 0 ? 0.0 : (double)sa_accepted_count / sa_iteration_count;
        double worse_acceptance_rate = sa_iteration_count == 0 ? 0.0 : (double)sa_worse_accepted_count / sa_iteration_count;
        cerr << "generated_tree_count=" << generated_tree_count
             << " generated_raw_candidate_count=" << generated_raw_candidate_count
             << " kept_raw_candidate_count=" << raw_candidate_pool.size()
             << " random_phase_tree_count=" << random_phase_tree_count
             << " sa_seed_count=" << sa_seed_count
             << " sa_iteration_count=" << sa_iteration_count
             << " sa_valid_neighbor_count=" << sa_valid_neighbor_count
             << " sa_accepted_count=" << sa_accepted_count
             << " sa_worse_accepted_count=" << sa_worse_accepted_count
             << " sa_rejected_count=" << sa_rejected_count
             << " sa_best_update_count=" << sa_best_update_count
             << " sa_initial_best_score=" << sa_initial_best_score
             << " sa_final_best_score=" << sa_final_best_score
             << " sa_acceptance_rate=" << acceptance_rate
             << " sa_worse_acceptance_rate=" << worse_acceptance_rate
             << " raw_candidate_pool_size=" << raw_candidate_pool.size()
             << " exact_attempt_count=" << lazy_repair_attempt_count
             << " lazy_repair_attempt_count=" << lazy_repair_attempt_count
             << " lazy_repair_success_count=" << lazy_repair_success_count
             << " exact_bfs_count=" << exact_bfs_count
             << " generated_side_path_count=" << generated_side_path_count
             << " examined_pair_count=" << examined_pair_count
             << " detailed_pair_count=" << detailed_pair_count
             << " valid_candidate_count=" << valid_candidate_count
             << " exact_evaluated_count=" << exact_evaluated_count
             << " best_main_path_length=" << main_path_length
             << " best_index_a=" << best.index_a
             << " best_index_b=" << best.index_b
             << " best_stem_length=" << stem_length
             << " best_connector_length=" << connector_length
             << " best_A_length=" << max(0, (int)best.path_a.size() - 1)
             << " best_B_length=" << max(0, (int)best.path_b.size() - 1)
             << " best_C_length=" << c_length
             << " best_full_isolation_wall_count=" << best.full_isolation_wall_count
             << " best_actual_fixed_wall_count=" << best.fixed_wall_count
             << " best_total_door_count=" << best.doors.size()
             << " best_theoretical_t=" << best.theoretical_t
             << " best_selection_score=" << best.selection_score
             << " best_exact_t=" << best.exact_t
             << " elapsed_ms=" << elapsed_ms()
             << '\n';
        for (const string& log : repair_logs) cerr << log << '\n';
        return best;
    }

    void print_door(const Door& door) const {
        auto [ar, ac] = rc(door.a);
        auto [br, bc] = rc(door.b);
        if (ar == br) {
            cout << 1 << ' ' << ar << ' ' << min(ac, bc) << ' ' << door.g << '\n';
        } else {
            cout << 0 << ' ' << min(ar, br) << ' ' << ac << ' ' << door.g << '\n';
        }
    }

    void print_answer(const Candidate& cand) const {
        cout << cand.doors.size() << '\n';
        for (const Door& door : cand.doors) print_door(door);
        cout << cand.switches.size() << '\n';
        for (const PlacedSwitch& sw : cand.switches) {
            auto [r, col] = rc(sw.v);
            cout << r << ' ' << col << ' ' << sw.s << '\n';
        }
    }

    void solve() {
        start_time = chrono::steady_clock::now();
        read_input();
        build_graph();
        Candidate answer = choose_best_candidate();
        print_answer(answer);
    }
};

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

    Solver solver;
    solver.solve();
    return 0;
}

提出情報

ジャッジ結果