提出 #72330408

---

ソースコード 拡げる

/**
 * AtCoder Heuristic Contest 059 Solution
 * Strategy: SA on Dyck Path + Iterative Tree DP + Pruning
 * Updates:
 * 1. Base: Improved Iterative Tree DP version.
 * 2. Improved Block Shift:
 * - 20%: Insert as leaf (v v) at optimal position.
 * - 80%: Insert wrapping an existing block u (v u ... u v) at optimal position.
 */

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <chrono>
#include <random>
#include <numeric>
#include <cassert>

using namespace std;

// --- Constants ---
const int N = 20;
const int NUM_PAIRS = N * N / 2; // 200
const double TIME_LIMIT = 1.95;

// --- Structs ---
struct Point {
    int r, c;
    inline int dist(const Point& other) const {
        return abs(r - other.r) + abs(c - other.c);
    }
};

struct Xorshift {
    uint32_t x = 123456789;
    uint32_t y = 362436069;
    uint32_t z = 521288629;
    uint32_t w = 88675123;
    inline uint32_t next() {
        uint32_t t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
    inline int next_int(int n) {
        return next() % n;
    }
    inline double next_double() {
        return next() / 4294967295.0;
    }
};

// --- Globals ---
Point pair_locs[NUM_PAIRS][2];
Point start_pos = { 0, 0 };

struct CostPair {
    int c0;
    int c1;
};

// --- Solver ---
class Solver {
    Xorshift rng;
    vector<int> p;

    // Tree DP buffers
    vector<int> adj_head;      
    vector<int> adj_next;      
    vector<int> node_stack;
    vector<bool> seen;
    vector<int> post_order;    
    vector<CostPair> memo;     

    // Transition buffers
    vector<int> temp_next_p;
    vector<int> current_block; 
    vector<int> p_without_blocks;
    
    // Relabel buffers
    vector<int> r_list;
    vector<bool> visited;
    vector<int> mapping;
    
    // Block tracking
    vector<int> block_starts;

public:
    void read_input() {
        int n_dummy;
        if (cin >> n_dummy) {}

        for (int i = 0; i < NUM_PAIRS; ++i) {
            pair_locs[i][0] = { -1, -1 };
            pair_locs[i][1] = { -1, -1 };
        }

        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int val;
                cin >> val;
                if (pair_locs[val][0].r == -1) pair_locs[val][0] = { r, c };
                else pair_locs[val][1] = { r, c };
            }
        }

        // Resize buffers
        adj_head.resize(NUM_PAIRS + 1);
        adj_next.resize(NUM_PAIRS); 
        node_stack.resize(NUM_PAIRS + 5);
        seen.resize(NUM_PAIRS);
        post_order.resize(NUM_PAIRS + 1);
        memo.resize(NUM_PAIRS + 1);
        
        temp_next_p.reserve(2 * NUM_PAIRS);
        current_block.reserve(2 * NUM_PAIRS);
        p_without_blocks.reserve(2 * NUM_PAIRS);
        
        r_list.reserve(NUM_PAIRS);
        visited.resize(NUM_PAIRS);
        mapping.resize(NUM_PAIRS);
        
        block_starts.resize(NUM_PAIRS);
    }

    // Helper: Min dist
    inline int get_min_dist(int id1, int id2) {
        if (id1 == -1 && id2 == -1) return 0;
        
        Point p1_0, p1_1;
        if (id1 == -1) { p1_0 = start_pos; p1_1 = start_pos; }
        else { p1_0 = pair_locs[id1][0]; p1_1 = pair_locs[id1][1]; }

        Point p2_0, p2_1;
        if (id2 == -1) { p2_0 = start_pos; p2_1 = start_pos; }
        else { p2_0 = pair_locs[id2][0]; p2_1 = pair_locs[id2][1]; }

        int d1 = p1_0.dist(p2_0);
        int d2 = p1_0.dist(p2_1);
        int d3 = p1_1.dist(p2_0);
        int d4 = p1_1.dist(p2_1);
        
        int m1 = (d1 < d2) ? d1 : d2;
        int m2 = (d3 < d4) ? d3 : d4;
        return (m1 < m2) ? m1 : m2;
    }

    // Helper: Block range
    pair<int, int> get_block_range(const vector<int>& seq, int target_pair) {
        int start = -1;
        for(int i=0; i<(int)seq.size(); ++i) {
            if (seq[i] == target_pair) {
                if (start == -1) start = i;
                else return {start, i + 1};
            }
        }
        return {-1, -1};
    }

    void build_tree() {
        fill(adj_head.begin(), adj_head.end(), -1);
        fill(seen.begin(), seen.end(), false);
        
        int stack_top = 0;
        node_stack[stack_top++] = NUM_PAIRS; 
        
        int po_idx = 0;
        static int last_child[NUM_PAIRS + 1];
        fill(last_child, last_child + NUM_PAIRS + 1, -1);

        for (int x : p) {
            if (!seen[x]) {
                int parent = node_stack[stack_top - 1];
                if (adj_head[parent] == -1) {
                    adj_head[parent] = x;
                } else {
                    adj_next[last_child[parent]] = x;
                }
                last_child[parent] = x;
                adj_next[x] = -1;

                node_stack[stack_top++] = x;
                seen[x] = true;
            }
            else {
                post_order[po_idx++] = x;
                stack_top--;
            }
        }
        post_order[po_idx++] = NUM_PAIRS;
    }

    int calc_score_iterative() {
        build_tree();

        for (int k = 0; k <= NUM_PAIRS; ++k) {
            int u = post_order[k];

            Point u0_in, u0_out, u1_in, u1_out;
            if (u == NUM_PAIRS) {
                u0_in = u0_out = u1_in = u1_out = start_pos;
            } else {
                u0_in = pair_locs[u][0]; u0_out = pair_locs[u][1];
                u1_in = pair_locs[u][1]; u1_out = pair_locs[u][0];
            }

            int first_child = adj_head[u];
            if (first_child == -1) {
                if (u == NUM_PAIRS) {
                    memo[u] = { 0, 0 };
                } else {
                    int d = u0_in.dist(u0_out);
                    memo[u] = { d, d };
                }
                continue;
            }

            // Config 0
            int dp0, dp1;
            Point pt0 = u0_in; 
            Point pt1 = u0_in;

            {
                int v = first_child;
                int cost_v0 = memo[v].c0;
                int cost_v1 = memo[v].c1;
                
                dp0 = pt0.dist(pair_locs[v][0]) + cost_v0;
                dp1 = pt0.dist(pair_locs[v][1]) + cost_v1;
                pt0 = pair_locs[v][1]; 
                pt1 = pair_locs[v][0]; 
            }

            int v = adj_next[first_child];
            while (v != -1) {
                int cost_v0 = memo[v].c0;
                int cost_v1 = memo[v].c1;
                
                int t0_0 = dp0 + pt0.dist(pair_locs[v][0]);
                int t0_1 = dp1 + pt1.dist(pair_locs[v][0]);
                int next0 = (t0_0 < t0_1 ? t0_0 : t0_1) + cost_v0;

                int t1_0 = dp0 + pt0.dist(pair_locs[v][1]);
                int t1_1 = dp1 + pt1.dist(pair_locs[v][1]);
                int next1 = (t1_0 < t1_1 ? t1_0 : t1_1) + cost_v1;

                dp0 = next0; dp1 = next1;
                pt0 = pair_locs[v][1];
                pt1 = pair_locs[v][0];

                v = adj_next[v];
            }

            int res_c0 = min(dp0 + pt0.dist(u0_out), dp1 + pt1.dist(u0_out));

            if (u == NUM_PAIRS) {
                int root_res = min(dp0, dp1); 
                memo[u] = { root_res, root_res };
                continue; 
            }

            // Config 1
            {
                dp0 = 0; dp1 = 0;
                pt0 = u1_in; pt1 = u1_in;
                
                int v = first_child;
                int curr0 = pt0.dist(pair_locs[v][0]) + memo[v].c0;
                int curr1 = pt0.dist(pair_locs[v][1]) + memo[v].c1;
                dp0 = curr0; dp1 = curr1;
                pt0 = pair_locs[v][1]; pt1 = pair_locs[v][0];

                v = adj_next[v];
                while(v != -1) {
                    int cost_v0 = memo[v].c0;
                    int cost_v1 = memo[v].c1;

                    int t0_0 = dp0 + pt0.dist(pair_locs[v][0]);
                    int t0_1 = dp1 + pt1.dist(pair_locs[v][0]);
                    int next0 = (t0_0 < t0_1 ? t0_0 : t0_1) + cost_v0;

                    int t1_0 = dp0 + pt0.dist(pair_locs[v][1]);
                    int t1_1 = dp1 + pt1.dist(pair_locs[v][1]);
                    int next1 = (t1_0 < t1_1 ? t1_0 : t1_1) + cost_v1;

                    dp0 = next0; dp1 = next1;
                    pt0 = pair_locs[v][1]; pt1 = pair_locs[v][0];
                    v = adj_next[v];
                }
            }
            int res_c1 = min(dp0 + pt0.dist(u1_out), dp1 + pt1.dist(u1_out));

            memo[u] = { res_c0, res_c1 };
        }

        return memo[NUM_PAIRS].c0;
    }

    void solve() {
        auto start_clock = chrono::system_clock::now();

        vector<int> r_perm(NUM_PAIRS);
        iota(r_perm.begin(), r_perm.end(), 0);
        for (int i = NUM_PAIRS - 1; i > 0; i--) {
            int j = rng.next_int(i + 1);
            swap(r_perm[i], r_perm[j]);
        }
        
        p.clear();
        for (int i = 0; i < NUM_PAIRS; i++) p.push_back(r_perm[i]);
        for (int i = 0; i < NUM_PAIRS; i++) p.push_back(r_perm[NUM_PAIRS - 1 - i]);

        int current_score = calc_score_iterative();
        int best_score = current_score;
        vector<int> best_p = p;

        double temp_start = 1.0;
        double temp_end = 0.1;

        int iter = 0;
        double temp = temp_start;
        double ratio = 0.0;

        while (true) {
            iter++;
            if ((iter & 0x1FF) == 0) { 
                auto now = chrono::system_clock::now();
                double elapsed = chrono::duration_cast<chrono::microseconds>(now - start_clock).count() * 1e-6;
                if (elapsed > TIME_LIMIT) break;

                ratio = elapsed / TIME_LIMIT;
                temp = temp_start + (temp_end - temp_start) * ratio;
            }

            int type = rng.next_int(100);

            if (type < 40 && ratio > 0.5) {
                // --- 1. Single Block Shift (Improved) ---
                int v = rng.next_int(NUM_PAIRS);
                pair<int, int> range = get_block_range(p, v);
                
                current_block.assign(p.begin() + range.first, p.begin() + range.second);
                
                p_without_blocks.clear();
                p_without_blocks.insert(p_without_blocks.end(), p.begin(), p.begin() + range.first);
                p_without_blocks.insert(p_without_blocks.end(), p.begin() + range.second, p.end());

                // Find valid insertion points (existing blocks to wrap)
                fill(block_starts.begin(), block_starts.end(), -1);
                vector<int> existing_blocks;
                for(int i=0; i<(int)p_without_blocks.size(); ++i) {
                    int id = p_without_blocks[i];
                    if(block_starts[id] == -1) {
                        block_starts[id] = i;
                    } else {
                        existing_blocks.push_back(id);
                    }
                }

                int best_type = -1; // 0: leaf, 1: wrap
                int best_ins_param = -1; 
                int best_heuristic = 2e9;
                
                int outer_v = v; 
                int d_v_self = pair_locs[outer_v][0].dist(pair_locs[outer_v][1]);
                
                int trials = 20;
                for(int k=0; k<trials; ++k) {
                    // 20% Leaf, 80% Wrap
                    bool try_wrap = (rng.next_int(100) < 80 && !existing_blocks.empty());
                    
                    if (try_wrap) {
                        // Wrap around u
                        int u = existing_blocks[rng.next_int(existing_blocks.size())];
                        int u_start = block_starts[u];
                        int u_end = -1;
                        for(int i=u_start+1; i<(int)p_without_blocks.size(); ++i) {
                            if(p_without_blocks[i] == u) { u_end = i; break; }
                        }
                        
                        // Insert v ... u ... u ... v
                        // Pos1: u_start, Pos2: u_end + 1
                        int prev_id_1 = (u_start > 0) ? p_without_blocks[u_start-1] : -1;
                        int next_id_1 = u; 
                        
                        int prev_id_2 = u; 
                        int next_id_2 = (u_end < (int)p_without_blocks.size()-1) ? p_without_blocks[u_end+1] : -1;
                        
                        int d_delta1 = get_min_dist(prev_id_1, outer_v) + get_min_dist(outer_v, next_id_1) - get_min_dist(prev_id_1, next_id_1);
                        int d_delta2 = get_min_dist(prev_id_2, outer_v) + get_min_dist(outer_v, next_id_2) - get_min_dist(prev_id_2, next_id_2);
                        
                        int heuristic = d_delta1 + d_delta2 + d_v_self;
                        
                        if (heuristic < best_heuristic) {
                            best_heuristic = heuristic;
                            best_type = 1;
                            best_ins_param = u;
                        }
                    } else {
                        // Leaf insertion
                        int idx = rng.next_int(p_without_blocks.size() + 1);
                        int prev_id = (idx > 0) ? p_without_blocks[idx-1] : -1;
                        int next_id = (idx < (int)p_without_blocks.size()) ? p_without_blocks[idx] : -1;
                        
                        int d_prev_v = get_min_dist(prev_id, outer_v);
                        int d_v_next = get_min_dist(outer_v, next_id);
                        int d_rem = get_min_dist(prev_id, next_id);
                        
                        int heuristic = d_prev_v + d_v_self + d_v_next - d_rem;
                        if (heuristic < best_heuristic) {
                            best_heuristic = heuristic;
                            best_type = 0;
                            best_ins_param = idx;
                        }
                    }
                }

                temp_next_p = p_without_blocks;
                
                if (best_type == 1) {
                    // Wrap u
                    int u = best_ins_param;
                    int u_start = -1, u_end = -1;
                    for(int i=0; i<(int)temp_next_p.size(); ++i) {
                        if(temp_next_p[i] == u) {
                            if(u_start == -1) u_start = i;
                            else { u_end = i; break; }
                        }
                    }
                    
                    // Note: current_block contains v's full subtree.
                    // To wrap u, we need to split current_block into [v, children..., v].
                    // If v is a leaf, it's just v, v. 
                    // If v has children, we need to decide where to put them.
                    // For simplicity, if v has children (size > 2), we fallback to Leaf Insertion.
                    // If v is leaf (size == 2), we can wrap.
                    
                    if (current_block.size() > 2) {
                         int idx = rng.next_int(temp_next_p.size() + 1);
                         temp_next_p.insert(temp_next_p.begin() + idx, current_block.begin(), current_block.end());
                    } else {
                        temp_next_p.insert(temp_next_p.begin() + u_end + 1, v);
                        temp_next_p.insert(temp_next_p.begin() + u_start, v);
                    }
                } else {
                    // Leaf or fallback
                    int idx = (best_type == 0) ? best_ins_param : rng.next_int(temp_next_p.size() + 1);
                    temp_next_p.insert(temp_next_p.begin() + idx, current_block.begin(), current_block.end());
                }
                
                p.swap(temp_next_p);
                int new_score = calc_score_iterative();
                int delta = new_score - current_score;

                if (delta < 0 || rng.next_double() < exp(-delta / temp)) {
                    current_score = new_score;
                    if (current_score < best_score) {
                        best_score = current_score;
                        best_p = p;
                        cerr << "Update: " << best_score << endl;
                    }
                } else {
                    p.swap(temp_next_p); // Revert
                }

            } else if (type < 70 && ratio > 0.5) {
                // --- 2. Subtree Reverse ---
                int best_target = -1, best_L = -1, best_R = -1;
                int best_heuristic_gain = 2e9; 

                for(int k=0; k<10; ++k) {
                    int target = rng.next_int(NUM_PAIRS);
                    int L = -1, R = -1;
                    for (int i = 0; i < (int)p.size(); ++i) {
                        if (p[i] == target) {
                            if (L == -1) L = i;
                            else { R = i; break; }
                        }
                    }
                    if (L + 1 < R) {
                        int id_P = p[L];      
                        int id_First = p[L+1]; 
                        int id_Last = p[R-1];  
                        
                        int current_conn = get_min_dist(id_P, id_First) + get_min_dist(id_Last, id_P);
                        int new_conn     = get_min_dist(id_P, id_Last)  + get_min_dist(id_First, id_P);
                        int gain = new_conn - current_conn;
                        
                        if (gain < best_heuristic_gain) {
                            best_heuristic_gain = gain;
                            best_target = target;
                            best_L = L; best_R = R;
                        }
                    }
                }

                if (best_L != -1) {
                    reverse(p.begin() + best_L + 1, p.begin() + best_R);
                    int new_score = calc_score_iterative();
                    int delta = new_score - current_score;

                    if (delta < 0 || rng.next_double() < exp(-delta / temp)) {
                        current_score = new_score;
                        if (current_score < best_score) {
                            best_score = current_score;
                            best_p = p;
                            cerr << "Update: " << best_score << endl;
                        }
                    } else {
                        reverse(p.begin() + best_L + 1, p.begin() + best_R);
                    }
                }

            } else {
                // --- 3. Interval Relabeling ---
                r_list.clear();
                fill(visited.begin(), visited.end(), false);
                for (int x : p) {
                    if (!visited[x]) {
                        visited[x] = true;
                        r_list.push_back(x);
                    }
                }

                int i = rng.next_int(NUM_PAIRS);
                int j = rng.next_int(NUM_PAIRS);
                if (i > j) swap(i, j);

                for (int k = 0; k < NUM_PAIRS; ++k) mapping[k] = k;
                for (int k = 0; k <= j - i; ++k) {
                    mapping[r_list[i + k]] = r_list[j - k];
                }

                vector<int> old_p = p;
                for (int& x : p) x = mapping[x];

                int new_score = calc_score_iterative();
                int delta = new_score - current_score;

                if (delta < 0 || rng.next_double() < exp(-delta / temp)) {
                    current_score = new_score;
                    if (current_score < best_score) {
                        best_score = current_score;
                        best_p = p;
                        cerr << "Update: " << best_score << endl;
                    }
                } else {
                    p = old_p; // Revert
                }
            }
        }
        
        reconstruct_and_print(best_p);
    }

    void reconstruct_and_print(const vector<int>& final_p) {
        p = final_p;
        calc_score_iterative();
        vector<int> final_q(NUM_PAIRS);

        vector<pair<int, int>> assign_stack;
        assign_stack.reserve(NUM_PAIRS + 1);
        assign_stack.push_back({NUM_PAIRS, 0});

        while(!assign_stack.empty()) {
            auto [u, u_config] = assign_stack.back();
            assign_stack.pop_back();

            if (u != NUM_PAIRS) final_q[u] = u_config;

            int first_child = adj_head[u];
            if (first_child == -1) continue;
            
            vector<int> children;
            for(int v = first_child; v != -1; v = adj_next[v]) children.push_back(v);
            int K = children.size();

            Point start_pt;
            if (u == NUM_PAIRS) start_pt = start_pos;
            else start_pt = (u_config == 0) ? pair_locs[u][0] : pair_locs[u][1];
            
            vector<vector<int>> dp(K, vector<int>(2));
            vector<vector<int>> parent_cfg(K, vector<int>(2));

            int v0 = children[0];
            dp[0][0] = start_pt.dist(pair_locs[v0][0]) + memo[v0].c0;
            dp[0][1] = start_pt.dist(pair_locs[v0][1]) + memo[v0].c1;

            for(int i=1; i<K; ++i) {
                int v = children[i];
                int prev_v = children[i-1];
                int c00 = dp[i-1][0] + pair_locs[prev_v][1].dist(pair_locs[v][0]) + memo[v].c0;
                int c10 = dp[i-1][1] + pair_locs[prev_v][0].dist(pair_locs[v][0]) + memo[v].c0;
                if (c00 < c10) { dp[i][0] = c00; parent_cfg[i][0] = 0; } else { dp[i][0] = c10; parent_cfg[i][0] = 1; }

                int c01 = dp[i-1][0] + pair_locs[prev_v][1].dist(pair_locs[v][1]) + memo[v].c1;
                int c11 = dp[i-1][1] + pair_locs[prev_v][0].dist(pair_locs[v][1]) + memo[v].c1;
                if (c01 < c11) { dp[i][1] = c01; parent_cfg[i][1] = 0; } else { dp[i][1] = c11; parent_cfg[i][1] = 1; }
            }

            int last_cfg = 0;
            if (u == NUM_PAIRS) {
                if (dp[K-1][1] < dp[K-1][0]) last_cfg = 1;
            } else {
                Point u_out = (u_config == 0) ? pair_locs[u][1] : pair_locs[u][0];
                int v_last = children.back();
                int total0 = dp[K-1][0] + pair_locs[v_last][1].dist(u_out);
                int total1 = dp[K-1][1] + pair_locs[v_last][0].dist(u_out);
                if (total1 < total0) last_cfg = 1;
            }

            for(int i=K-1; i>=0; --i) {
                assign_stack.push_back({children[i], last_cfg});
                if (i > 0) last_cfg = parent_cfg[i][last_cfg];
            }
        }

        string ops = "";
        Point curr = start_pos;
        vector<int> count(NUM_PAIRS, 0);
        auto move_gen = [&](Point target) {
            while (curr.r < target.r) { ops += 'D'; curr.r++; }
            while (curr.r > target.r) { ops += 'U'; curr.r--; }
            while (curr.c < target.c) { ops += 'R'; curr.c++; }
            while (curr.c > target.c) { ops += 'L'; curr.c--; }
            ops += 'Z';
        };

        for (int x : p) {
            bool is_sec = (count[x] > 0);
            int type = is_sec ? (1 - final_q[x]) : final_q[x];
            move_gen(pair_locs[x][type]);
            count[x]++;
        }
        for (char c : ops) cout << c << "\n";
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    Solver solver;
    solver.read_input();
    solver.solve();
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In member function 'void Solver::solve()':
./Main.cpp:469:21: warning: variable 'best_target' set but not used [-Wunused-but-set-variable]
  469 |                 int best_target = -1, best_L = -1, best_R = -1;
      |                     ^~~~~~~~~~~

ジャッジ結果