提出 #74068829

---

ソースコード 拡げる

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

using ll = long long;

struct Solver {
    static constexpr int N = 200;
    static constexpr int G = 4;            // macro cell size
    static constexpr int M = N / G;        // 50
    static constexpr int TOTAL = N * N;    // 40000
    static constexpr int STATES = 24;      // 4!

    vector<vector<int>> A;
    vector<vector<int>> C; // centered values for approximate DP

    enum Dir : int { L = 0, R = 1, U = 2, D = 3 };

    struct Perm {
        array<int, 4> p; // entry lane -> stream id
    };

    using LocalPath = vector<pair<int,int>>; // coordinates in [0,3]^2

    struct Gadget {
        array<LocalPath, 4> path; // indexed by entry lane
        array<int, 4> out_lane;   // entry lane i exits from out_lane[i]
    };

    struct MacroStep {
        pair<int,int> macro;
        Dir in_dir, out_dir;
        bool is_straight;
    };

    struct Candidate {
        string name;
        vector<MacroStep> steps; // size 2500
    };

    struct DPResult {
        bool ok = false;
        ll approx_score = -(1LL << 60);
        vector<int> state_trace;      // entry state at step i
        vector<short> choice_trace;   // gadget index at step i, or -2 for compressed straight
        int terminal_state = -1;
    };

    vector<Perm> perms;
    int perm_id[4][4][4][4]{};
    vector<vector<int>> trans;          // permutation transitions realizable by one straight 4x4 cell
    vector<Gadget> gadgets[4][4];       // by (in,out), in != out

    Solver() : A(N, vector<int>(N)), C(N, vector<int>(N)) {
        build_perms();
        build_straight_transitions();
        build_gadgets();
    }

    static bool king_adj(pair<int,int> a, pair<int,int> b) {
        return max(abs(a.first - b.first), abs(a.second - b.second)) == 1;
    }

    pair<int,int> to_global(pair<int,int> macro, pair<int,int> local) const {
        return {macro.first * G + local.first, macro.second * G + local.second};
    }

    Dir dir_between(pair<int,int> a, pair<int,int> b) const {
        if (a.first == b.first) {
            if (a.second + 1 == b.second) return R;
            if (a.second - 1 == b.second) return L;
        }
        if (a.second == b.second) {
            if (a.first + 1 == b.first) return D;
            if (a.first - 1 == b.first) return U;
        }
        throw runtime_error("dir_between: non-adjacent macro cells");
    }

    Dir opposite(Dir d) const {
        if (d == L) return R;
        if (d == R) return L;
        if (d == U) return D;
        return U;
    }

    int side_lane_of_cell(pair<int,int> p, Dir side) const {
        auto [r, c] = p;
        if (side == L) return (c == 0 ? r : -1);
        if (side == R) return (c == 3 ? r : -1);
        if (side == U) return (r == 0 ? c : -1);
        if (side == D) return (r == 3 ? c : -1);
        return -1;
    }

    Gadget make_gadget(const array<LocalPath,4>& raw, Dir in, Dir out) const {
        Gadget g;
        array<int,4> seen_in{};
        array<int,4> seen_out{};

        for (int k = 0; k < 4; ++k) {
            const auto& p = raw[k];
            if (p.empty()) throw runtime_error("empty local path");

            int a = side_lane_of_cell(p.front(), in);
            int b = side_lane_of_cell(p.back(), out);

            if (!(0 <= a && a < 4 && 0 <= b && b < 4)) {
                throw runtime_error("make_gadget: endpoint side mismatch");
            }
            if (seen_in[a] || seen_out[b]) {
                throw runtime_error("make_gadget: duplicate lane");
            }

            seen_in[a] = 1;
            seen_out[b] = 1;
            g.path[a] = p;
            g.out_lane[a] = b;
        }

        for (int i = 0; i < 4; ++i) {
            if (!seen_in[i] || !seen_out[i]) {
                throw runtime_error("make_gadget: missing lane");
            }
            for (int j = 0; j + 1 < (int)g.path[i].size(); ++j) {
                if (!king_adj(g.path[i][j], g.path[i][j + 1])) {
                    throw runtime_error("make_gadget: non-adj local path");
                }
            }
        }

        return g;
    }

    void build_perms() {
        array<int,4> a = {0,1,2,3};
        int id = 0;
        do {
            perms.push_back({a});
            perm_id[a[0]][a[1]][a[2]][a[3]] = id++;
        } while (next_permutation(a.begin(), a.end()));
    }

    int get_perm_id(const array<int,4>& p) const {
        return perm_id[p[0]][p[1]][p[2]][p[3]];
    }

    vector<array<int,4>> one_layer_perms() const {
        vector<array<int,4>> res;
        res.push_back({0,1,2,3});
        res.push_back({1,0,2,3});
        res.push_back({0,2,1,3});
        res.push_back({0,1,3,2});
        res.push_back({1,0,3,2});
        return res;
    }

    void build_straight_transitions() {
        trans.assign(STATES, {});

        auto layers = one_layer_perms();
        vector<array<int,4>> cell_perms;
        {
            set<array<int,4>> st;
            for (auto p1 : layers) {
                for (auto p2 : layers) {
                    for (auto p3 : layers) {
                        array<int,4> q{};
                        array<int,4> t{}, u{};
                        for (int i = 0; i < 4; ++i) t[i] = p1[i];
                        for (int i = 0; i < 4; ++i) u[i] = p2[t[i]];
                        for (int i = 0; i < 4; ++i) q[i] = p3[u[i]];
                        st.insert(q);
                    }
                }
            }
            for (auto q : st) cell_perms.push_back(q);
        }

        for (int pid = 0; pid < STATES; ++pid) {
            const auto& p = perms[pid].p;
            vector<int> nxt;
            for (auto qlane : cell_perms) {
                array<int,4> np{};
                for (int in_lane = 0; in_lane < 4; ++in_lane) {
                    np[qlane[in_lane]] = p[in_lane];
                }
                nxt.push_back(get_perm_id(np));
            }
            sort(nxt.begin(), nxt.end());
            nxt.erase(unique(nxt.begin(), nxt.end()), nxt.end());
            trans[pid] = move(nxt);
        }
    }

    LocalPath transpose_path(const LocalPath& p) const {
        LocalPath q = p;
        for (auto& x : q) swap(x.first, x.second);
        return q;
    }

    void build_straight_lr_gadgets() {
        vector<int> masks = {0, 1, 2, 4, 5}; // 01,12,23,01+23 on one layer

        auto apply_mask = [&](int row, int mask) -> int {
            if (mask & 1) {
                if (row == 0) return 1;
                if (row == 1) return 0;
            }
            if (mask & 2) {
                if (row == 1) return 2;
                if (row == 2) return 1;
            }
            if (mask & 4) {
                if (row == 2) return 3;
                if (row == 3) return 2;
            }
            return row;
        };

        // L -> R exact 3-layer ladders
        for (int m0 : masks) {
            for (int m1 : masks) {
                for (int m2 : masks) {
                    array<LocalPath,4> raw;
                    for (int in_lane = 0; in_lane < 4; ++in_lane) {
                        int row = in_lane;
                        raw[in_lane].push_back({row, 0});
                        row = apply_mask(row, m0);
                        raw[in_lane].push_back({row, 1});
                        row = apply_mask(row, m1);
                        raw[in_lane].push_back({row, 2});
                        row = apply_mask(row, m2);
                        raw[in_lane].push_back({row, 3});
                    }
                    gadgets[L][R].push_back(make_gadget(raw, L, R));
                }
            }
        }

        // R -> L
        for (const auto& g0 : gadgets[L][R]) {
            array<LocalPath,4> raw;
            for (int i = 0; i < 4; ++i) {
                raw[i] = g0.path[i];
                reverse(raw[i].begin(), raw[i].end());
            }
            gadgets[R][L].push_back(make_gadget(raw, R, L));
        }

        // U -> D
        for (const auto& g0 : gadgets[L][R]) {
            array<LocalPath,4> raw;
            for (int i = 0; i < 4; ++i) raw[i] = transpose_path(g0.path[i]);
            gadgets[U][D].push_back(make_gadget(raw, U, D));
        }

        // D -> U
        for (const auto& g0 : gadgets[U][D]) {
            array<LocalPath,4> raw;
            for (int i = 0; i < 4; ++i) {
                raw[i] = g0.path[i];
                reverse(raw[i].begin(), raw[i].end());
            }
            gadgets[D][U].push_back(make_gadget(raw, D, U));
        }
    }

    void build_corner_gadgets() {
        // L -> D
        {
            array<LocalPath,4> x;
            x[0] = {{0,0},{0,1},{0,2},{0,3},{1,3},{2,3},{3,3}};
            x[1] = {{1,0},{1,1},{1,2},{2,2},{3,2}};
            x[2] = {{2,0},{2,1},{3,1}};
            x[3] = {{3,0}};
            gadgets[L][D].push_back(make_gadget(x, L, D));
        }
        // D -> R
        {
            array<LocalPath,4> x;
            x[0] = {{3,0},{2,0},{1,0},{0,0},{0,1},{0,2},{0,3}};
            x[1] = {{3,1},{2,1},{1,1},{1,2},{1,3}};
            x[2] = {{3,2},{2,2},{2,3}};
            x[3] = {{3,3}};
            gadgets[D][R].push_back(make_gadget(x, D, R));
        }
        // R -> U
        {
            array<LocalPath,4> x;
            x[0] = {{3,3},{3,2},{3,1},{3,0},{2,0},{1,0},{0,0}};
            x[1] = {{2,3},{2,2},{2,1},{1,1},{0,1}};
            x[2] = {{1,3},{1,2},{0,2}};
            x[3] = {{0,3}};
            gadgets[R][U].push_back(make_gadget(x, R, U));
        }
        // U -> L
        {
            array<LocalPath,4> x;
            x[0] = {{0,3},{1,3},{2,3},{3,3},{3,2},{3,1},{3,0}};
            x[1] = {{0,2},{1,2},{2,2},{2,1},{2,0}};
            x[2] = {{0,1},{1,1},{1,0}};
            x[3] = {{0,0}};
            gadgets[U][L].push_back(make_gadget(x, U, L));
        }
        // D -> L
        {
            array<LocalPath,4> x;
            x[0] = {{3,3},{2,3},{1,3},{0,3},{0,2},{0,1},{0,0}};
            x[1] = {{3,2},{2,2},{1,2},{1,1},{1,0}};
            x[2] = {{3,1},{2,1},{2,0}};
            x[3] = {{3,0}};
            gadgets[D][L].push_back(make_gadget(x, D, L));
        }
        // L -> U
        {
            array<LocalPath,4> x;
            x[0] = {{3,0},{3,1},{3,2},{3,3},{2,3},{1,3},{0,3}};
            x[1] = {{2,0},{2,1},{2,2},{1,2},{0,2}};
            x[2] = {{1,0},{1,1},{0,1}};
            x[3] = {{0,0}};
            gadgets[L][U].push_back(make_gadget(x, L, U));
        }
        // U -> R
        {
            array<LocalPath,4> x;
            x[0] = {{0,0},{1,0},{2,0},{3,0},{3,1},{3,2},{3,3}};
            x[1] = {{0,1},{1,1},{2,1},{2,2},{2,3}};
            x[2] = {{0,2},{1,2},{1,3}};
            x[3] = {{0,3}};
            gadgets[U][R].push_back(make_gadget(x, U, R));
        }
        // R -> D
        {
            array<LocalPath,4> x;
            x[0] = {{0,3},{0,2},{0,1},{0,0},{1,0},{2,0},{3,0}};
            x[1] = {{1,3},{1,2},{1,1},{2,1},{3,1}};
            x[2] = {{2,3},{2,2},{3,2}};
            x[3] = {{3,3}};
            gadgets[R][D].push_back(make_gadget(x, R, D));
        }
    }

    void build_gadgets() {
        build_straight_lr_gadgets();
        build_corner_gadgets();

        for (int in = 0; in < 4; ++in) {
            for (int out = 0; out < 4; ++out) {
                if (in == out) continue;
                if (gadgets[in][out].empty()) {
                    throw runtime_error("missing gadget");
                }
            }
        }
    }

    static bool valid_macro_path(const vector<pair<int,int>>& p) {
        if ((int)p.size() != M * M) return false;
        vector<vector<int>> used(M, vector<int>(M, 0));
        for (auto [r, c] : p) {
            if (r < 0 || r >= M || c < 0 || c >= M) return false;
            if (used[r][c]) return false;
            used[r][c] = 1;
        }
        for (int i = 0; i + 1 < (int)p.size(); ++i) {
            auto [r1, c1] = p[i];
            auto [r2, c2] = p[i + 1];
            if (abs(r1 - r2) + abs(c1 - c2) != 1) return false;
        }
        return true;
    }

    vector<pair<int,int>> make_row_snake_macro() const {
        vector<pair<int,int>> p;
        p.reserve(M * M);
        for (int r = 0; r < M; ++r) {
            if (r % 2 == 0) {
                for (int c = 0; c < M; ++c) p.push_back({r, c});
            } else {
                for (int c = M - 1; c >= 0; --c) p.push_back({r, c});
            }
        }
        return p;
    }

    vector<pair<int,int>> make_col_snake_macro() const {
        vector<pair<int,int>> p;
        p.reserve(M * M);
        for (int c = 0; c < M; ++c) {
            if (c % 2 == 0) {
                for (int r = 0; r < M; ++r) p.push_back({r, c});
            } else {
                for (int r = M - 1; r >= 0; --r) p.push_back({r, c});
            }
        }
        return p;
    }

    pair<int,int> apply_sym(pair<int,int> p, int sym) const {
        auto [r, c] = p;
        if (sym == 0) return {r, c};
        if (sym == 1) return {c, M - 1 - r};
        if (sym == 2) return {M - 1 - r, M - 1 - c};
        if (sym == 3) return {M - 1 - c, r};
        if (sym == 4) return {r, M - 1 - c};
        if (sym == 5) return {M - 1 - r, c};
        if (sym == 6) return {c, r};
        if (sym == 7) return {M - 1 - c, M - 1 - r};
        return {0,0};
    }

    vector<pair<int,int>> transform_macro(const vector<pair<int,int>>& p, int sym) const {
        vector<pair<int,int>> q;
        q.reserve(p.size());
        for (auto x : p) q.push_back(apply_sym(x, sym));
        return q;
    }

    vector<pair<int,int>> reverse_macro(vector<pair<int,int>> p) const {
        reverse(p.begin(), p.end());
        return p;
    }

    Candidate build_candidate_from_macro(const vector<pair<int,int>>& macro, const string& name) const {
        Candidate cand;
        cand.name = name;
        cand.steps.reserve(macro.size());

        for (int i = 0; i < (int)macro.size(); ++i) {
            MacroStep st;
            st.macro = macro[i];

            if (i == 0) {
                st.out_dir = dir_between(macro[0], macro[1]);
                st.in_dir = opposite(st.out_dir);
            } else if (i + 1 == (int)macro.size()) {
                st.in_dir = opposite(dir_between(macro[i - 1], macro[i]));
                st.out_dir = opposite(st.in_dir);
            } else {
                st.in_dir = opposite(dir_between(macro[i - 1], macro[i]));
                st.out_dir = dir_between(macro[i], macro[i + 1]);
            }

            st.is_straight =
                (st.in_dir == L && st.out_dir == R) ||
                (st.in_dir == R && st.out_dir == L) ||
                (st.in_dir == U && st.out_dir == D) ||
                (st.in_dir == D && st.out_dir == U);

            cand.steps.push_back(st);
        }

        return cand;
    }

    vector<Candidate> build_candidates() const {
        vector<Candidate> res;
        unordered_set<string> seen;

        auto encode = [&](const vector<pair<int,int>>& p) {
            string s;
            s.reserve(p.size() * 2);
            for (auto [r, c] : p) {
                s.push_back(char(r));
                s.push_back(char(c));
            }
            return s;
        };

        vector<vector<pair<int,int>>> seeds = {
            make_row_snake_macro(),
            make_col_snake_macro()
        };

        for (int sid = 0; sid < (int)seeds.size(); ++sid) {
            for (int sym = 0; sym < 8; ++sym) {
                auto p = transform_macro(seeds[sid], sym);
                if (!valid_macro_path(p)) continue;
                auto key = encode(p);
                if (seen.insert(key).second) {
                    res.push_back(build_candidate_from_macro(p, "seed" + to_string(sid) + "_sym" + to_string(sym)));
                }

                auto rp = reverse_macro(p);
                if (!valid_macro_path(rp)) continue;
                auto rkey = encode(rp);
                if (seen.insert(rkey).second) {
                    res.push_back(build_candidate_from_macro(rp, "seed" + to_string(sid) + "_sym" + to_string(sym) + "_rev"));
                }
            }
        }
        return res;
    }

    array<int,4> approx_stream_base(int step_idx) const {
        int x = 4 * step_idx;
        return {x, 19999 - x, 20000 + x, 39999 - x};
    }

    ll gadget_score_approx(const Candidate& cand, int step_idx, const Gadget& g, const array<int,4>& entry_perm) const {
        auto base = approx_stream_base(step_idx);
        ll s = 0;

        for (int entry_lane = 0; entry_lane < 4; ++entry_lane) {
            int stream = entry_perm[entry_lane];
            bool increasing = (stream == 0 || stream == 2);

            for (int k = 0; k < (int)g.path[entry_lane].size(); ++k) {
                auto cell = to_global(cand.steps[step_idx].macro, g.path[entry_lane][k]);
                int t = increasing ? (base[stream] + k) : (base[stream] - k);
                s += 1LL * C[cell.first][cell.second] * t;
            }
        }
        return s;
    }

    array<int,4> apply_gadget_perm(const Gadget& g, const array<int,4>& entry_perm) const {
        array<int,4> out{};
        for (int in_lane = 0; in_lane < 4; ++in_lane) {
            out[g.out_lane[in_lane]] = entry_perm[in_lane];
        }
        return out;
    }

    bool valid_start_perm(const array<int,4>& perm) const {
        array<int,4> pos{};
        for (int lane = 0; lane < 4; ++lane) pos[perm[lane]] = lane;
        return abs(pos[1] - pos[2]) == 1;
    }

    bool valid_terminal_perm(const array<int,4>& perm) const {
        array<int,4> pos{};
        for (int lane = 0; lane < 4; ++lane) pos[perm[lane]] = lane;
        return abs(pos[0] - pos[1]) == 1 && abs(pos[2] - pos[3]) == 1;
    }

    array<array<ll, STATES>, STATES> build_straight_step_table(const Candidate& cand, int step_idx) const {
        array<array<ll, STATES>, STATES> best;
        for (int i = 0; i < STATES; ++i) {
            for (int j = 0; j < STATES; ++j) {
                best[i][j] = -(1LL << 60);
            }
        }

        const auto& gs = gadgets[cand.steps[step_idx].in_dir][cand.steps[step_idx].out_dir];
        for (int from = 0; from < STATES; ++from) {
            const auto& entry_perm = perms[from].p;
            for (const auto& g : gs) {
                auto next_perm = apply_gadget_perm(g, entry_perm);
                int to = get_perm_id(next_perm);
                ll sc = gadget_score_approx(cand, step_idx, g, entry_perm);
                best[from][to] = max(best[from][to], sc);
            }
        }
        return best;
    }

    int best_straight_gadget_for_transition(const Candidate& cand, int step_idx, int from, int to) const {
        const auto& gs = gadgets[cand.steps[step_idx].in_dir][cand.steps[step_idx].out_dir];
        const auto& entry_perm = perms[from].p;

        ll best_score = -(1LL << 60);
        int best_gid = -1;

        for (int gid = 0; gid < (int)gs.size(); ++gid) {
            const auto& g = gs[gid];
            auto next_perm = apply_gadget_perm(g, entry_perm);
            int nid = get_perm_id(next_perm);
            if (nid != to) continue;

            ll sc = gadget_score_approx(cand, step_idx, g, entry_perm);
            if (sc > best_score) {
                best_score = sc;
                best_gid = gid;
            }
        }
        return best_gid;
    }

    DPResult run_dp(const Candidate& cand) const {
        const int S = (int)cand.steps.size();

        vector<array<ll, STATES>> dp(S + 1);
        vector<array<short, STATES>> prv_state(S + 1);
        vector<array<short, STATES>> prv_choice(S + 1);

        for (int i = 0; i <= S; ++i) {
            for (int pid = 0; pid < STATES; ++pid) {
                dp[i][pid] = -(1LL << 60);
                prv_state[i][pid] = -1;
                prv_choice[i][pid] = -1;
            }
        }

        for (int pid = 0; pid < STATES; ++pid) {
            if (valid_start_perm(perms[pid].p)) {
                dp[0][pid] = 0;
            }
        }

        for (int i = 0; i < S; ++i) {
            if (cand.steps[i].is_straight) {
                auto best = build_straight_step_table(cand, i);

                for (int from = 0; from < STATES; ++from) {
                    if (dp[i][from] <= -(1LL << 50)) continue;
                    for (int to = 0; to < STATES; ++to) {
                        ll sc_local = best[from][to];
                        if (sc_local <= -(1LL << 50)) continue;
                        ll sc = dp[i][from] + sc_local;
                        if (sc > dp[i + 1][to]) {
                            dp[i + 1][to] = sc;
                            prv_state[i + 1][to] = from;
                            prv_choice[i + 1][to] = -2; // compressed straight
                        }
                    }
                }
            } else {
                const auto& gs = gadgets[cand.steps[i].in_dir][cand.steps[i].out_dir];
                for (int from = 0; from < STATES; ++from) {
                    if (dp[i][from] <= -(1LL << 50)) continue;
                    const auto& entry_perm = perms[from].p;

                    for (short gid = 0; gid < (short)gs.size(); ++gid) {
                        const auto& g = gs[gid];
                        auto next_perm = apply_gadget_perm(g, entry_perm);
                        int to = get_perm_id(next_perm);

                        ll sc = dp[i][from] + gadget_score_approx(cand, i, g, entry_perm);
                        if (sc > dp[i + 1][to]) {
                            dp[i + 1][to] = sc;
                            prv_state[i + 1][to] = from;
                            prv_choice[i + 1][to] = gid;
                        }
                    }
                }
            }
        }

        int best_final = -1;
        ll best_score = -(1LL << 60);
        for (int pid = 0; pid < STATES; ++pid) {
            if (!valid_terminal_perm(perms[pid].p)) continue;
            if (dp[S][pid] > best_score) {
                best_score = dp[S][pid];
                best_final = pid;
            }
        }
        if (best_final == -1) return {};

        vector<int> state_trace(S);
        vector<short> choice_trace(S);

        int cur = best_final;
        for (int i = S; i >= 1; --i) {
            int prev = prv_state[i][cur];
            short ch = prv_choice[i][cur];
            if (prev < 0) return {};
            state_trace[i - 1] = prev;
            choice_trace[i - 1] = ch;
            cur = prev;
        }

        DPResult res;
        res.ok = true;
        res.approx_score = best_score;
        res.state_trace = move(state_trace);
        res.choice_trace = move(choice_trace);
        res.terminal_state = best_final;
        return res;
    }

    bool reconstruct_path(const Candidate& cand, const DPResult& dpr, vector<pair<int,int>>& out_path) const {
        const int S = (int)cand.steps.size();
        if (!dpr.ok) return false;
        if ((int)dpr.state_trace.size() != S || (int)dpr.choice_trace.size() != S) return false;

        array<vector<pair<int,int>>,4> streams;

        for (int i = 0; i < S; ++i) {
            int from = dpr.state_trace[i];
            int to = (i + 1 < S ? dpr.state_trace[i + 1] : dpr.terminal_state);
            short ch = dpr.choice_trace[i];

            if (!(0 <= from && from < STATES && 0 <= to && to < STATES)) return false;

            int gid;
            if (ch == -2) {
                gid = best_straight_gadget_for_transition(cand, i, from, to);
                if (gid < 0) return false;
            } else {
                gid = ch;
            }

            const auto& gs = gadgets[cand.steps[i].in_dir][cand.steps[i].out_dir];
            if (!(0 <= gid && gid < (int)gs.size())) return false;

            const auto& entry_perm = perms[from].p;
            const auto& g = gs[gid];

            auto next_perm = apply_gadget_perm(g, entry_perm);
            if (get_perm_id(next_perm) != to) return false;

            for (int entry_lane = 0; entry_lane < 4; ++entry_lane) {
                int stream = entry_perm[entry_lane];
                for (auto local : g.path[entry_lane]) {
                    streams[stream].push_back(to_global(cand.steps[i].macro, local));
                }
            }
        }

        vector<pair<int,int>> path;
        path.reserve(TOTAL);

        for (auto p : streams[0]) path.push_back(p);
        for (int i = (int)streams[1].size() - 1; i >= 0; --i) path.push_back(streams[1][i]);
        for (auto p : streams[2]) path.push_back(p);
        for (int i = (int)streams[3].size() - 1; i >= 0; --i) path.push_back(streams[3][i]);

        if ((int)path.size() != TOTAL) return false;

        vector<vector<unsigned char>> used(N, vector<unsigned char>(N, 0));
        for (auto [r, c] : path) {
            if (!(0 <= r && r < N && 0 <= c && c < N)) return false;
            if (used[r][c]) return false;
            used[r][c] = 1;
        }
        for (int i = 0; i + 1 < TOTAL; ++i) {
            if (!king_adj(path[i], path[i + 1])) return false;
        }

        out_path = move(path);
        return true;
    }

    ll exact_score(const vector<pair<int,int>>& path) const {
        ll s = 0;
        for (int i = 0; i < TOTAL; ++i) {
            s += 1LL * i * A[path[i].first][path[i].second];
        }
        return s;
    }

    vector<pair<int,int>> fallback_simple_snake() const {
        vector<pair<int,int>> path;
        path.reserve(TOTAL);
        for (int r = 0; r < N; ++r) {
            if (r % 2 == 0) {
                for (int c = 0; c < N; ++c) path.push_back({r, c});
            } else {
                for (int c = N - 1; c >= 0; --c) path.push_back({r, c});
            }
        }
        return path;
    }

    void solve() {
        int nin;
        cin >> nin;
        if (nin != N) return;

        const double avg = (1.0 + TOTAL) * 0.5;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cin >> A[i][j];
                C[i][j] = int(llround(A[i][j] - avg));
            }
        }

        auto cands = build_candidates();

        ll best_exact = -(1LL << 60);
        vector<pair<int,int>> best_path;

        for (const auto& cand : cands) {
            auto dpr = run_dp(cand);
            if (!dpr.ok) continue;

            vector<pair<int,int>> path;
            if (!reconstruct_path(cand, dpr, path)) continue;

            ll ex = exact_score(path);
            if (ex > best_exact) {
                best_exact = ex;
                best_path = move(path);
            }
        }

        if (best_path.empty()) {
            best_path = fallback_simple_snake();
        }

        for (auto [r, c] : best_path) {
            cout << r << ' ' << c << '\n';
        }
    }
};

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

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

提出情報

ジャッジ結果