#1161223 (C++17(clang)) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: shell_mug
• 提出日時: 2026-04-24 16:07:08
• 言語: C++17(clang) (clang++ 22.1.2 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,852 ms / 2,000 ms
• コード長: 14,829 bytes
• コンパイル時間: 6,250 ms
• コンパイル使用メモリ: 180,532 KB
• 実行使用メモリ: 6,400 KB
• スコア: 2,236,075
• 最終ジャッジ日時: 2026-05-02 16:36:59
• 合計ジャッジ時間: 102,303 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
other	AC * 50

ソースコード

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

struct XorShift64 {
    uint64_t x;
    XorShift64(uint64_t seed = 88172645463393265ull) : x(seed) {}
    uint64_t next_u64() {
        x ^= x << 7;
        x ^= x >> 9;
        return x;
    }
    int next_int(int n) { return (int)(next_u64() % (uint64_t)n); }
    double next_double() { return (next_u64() >> 11) * (1.0 / 9007199254740992.0); }
};

struct Timer {
    chrono::steady_clock::time_point st;
    Timer() : st(chrono::steady_clock::now()) {}
    double elapsed() const {
        return chrono::duration<double>(chrono::steady_clock::now() - st).count();
    }
};

int N, T;
vector<long long> A;
vector<vector<int>> adjList;

inline int vid(int i, int j) { return i * N + j; }
inline pair<int,int> coord(int v) { return {v / N, v % N}; }

void build_adj() {
    adjList.assign(N * N, {});
    const int di[4] = {-1, 1, 0, 0};
    const int dj[4] = {0, 0, -1, 1};
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int v = vid(i, j);
            for (int d = 0; d < 4; ++d) {
                int ni = i + di[d], nj = j + dj[d];
                if (0 <= ni && ni < N && 0 <= nj && nj < N) adjList[v].push_back(vid(ni, nj));
            }
        }
    }
}

vector<int> base_snake() {
    vector<int> p;
    p.reserve(N * N);
    for (int i = 0; i < N; ++i) {
        if (i % 2 == 0) for (int j = 0; j < N; ++j) p.push_back(vid(i, j));
        else for (int j = N - 1; j >= 0; --j) p.push_back(vid(i, j));
    }
    return p;
}

pair<int,int> transform_cell(int sym, int i, int j) {
    switch (sym) {
        case 0: return {i, j};
        case 1: return {i, N - 1 - j};
        case 2: return {N - 1 - i, j};
        case 3: return {N - 1 - i, N - 1 - j};
        case 4: return {j, i};
        case 5: return {j, N - 1 - i};
        case 6: return {N - 1 - j, i};
        default: return {N - 1 - j, N - 1 - i};
    }
}

vector<int> make_sym_path(const vector<int>& base, int sym) {
    vector<int> p;
    p.reserve((int)base.size());
    for (int v : base) {
        auto [i, j] = coord(v);
        auto [ni, nj] = transform_cell(sym, i, j);
        p.push_back(vid(ni, nj));
    }
    return p;
}

pair<long long,int> best_window_score(const vector<int>& path) {
    int L = (int)path.size();
    vector<long long> pref(L + 1, 0);
    for (int i = 0; i < L; ++i) pref[i + 1] = pref[i] + A[path[i]];
    long long best = -1;
    int bestL = 0;
    for (int l = 0; l + T <= L; ++l) {
        long long s = pref[l + T] - pref[l];
        if (s > best) best = s, bestL = l;
    }
    return {best, bestL};
}

void rebuild_pos(const vector<int>& path, vector<int>& pos) {
    fill(pos.begin(), pos.end(), -1);
    for (int i = 0; i < (int)path.size(); ++i) pos[path[i]] = i;
}

bool valid_path(const vector<int>& path) {
    vector<int> seen(N * N, 0);
    for (int i = 0; i < (int)path.size(); ++i) {
        if (seen[path[i]]) return false;
        seen[path[i]] = 1;
        if (i + 1 < (int)path.size()) {
            bool ok = false;
            for (int to : adjList[path[i]]) if (to == path[i + 1]) { ok = true; break; }
            if (!ok) return false;
        }
    }
    return true;
}

// ---------- exact DFS for small T ----------
long long exactBestScore;
vector<int> exactBestPath, exactCurPath;
vector<char> exactUsed;
vector<long long> globalTopPref;

void exact_dfs(int depth, int v, long long score) {
    if (depth == T) {
        if (score > exactBestScore) exactBestScore = score, exactBestPath = exactCurPath;
        return;
    }
    long long ub = score + globalTopPref[T - depth];
    if (ub <= exactBestScore) return;

    array<pair<long long,int>, 4> cand;
    int m = 0;
    for (int to : adjList[v]) if (!exactUsed[to]) cand[m++] = {A[to], to};
    sort(cand.begin(), cand.begin() + m, greater<>());
    for (int idx = 0; idx < m; ++idx) {
        int to = cand[idx].second;
        exactUsed[to] = 1;
        exactCurPath.push_back(to);
        exact_dfs(depth + 1, to, score + A[to]);
        exactCurPath.pop_back();
        exactUsed[to] = 0;
    }
}

vector<int> solve_exact_small() {
    vector<int> order(N * N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) { return A[a] > A[b]; });

    vector<long long> sortedA = A;
    sort(sortedA.begin(), sortedA.end(), greater<long long>());
    globalTopPref.assign(T + 1, 0);
    for (int i = 0; i < T; ++i) globalTopPref[i + 1] = globalTopPref[i] + sortedA[i];

    exactBestScore = -1;
    exactBestPath.clear();
    exactCurPath.clear();
    exactUsed.assign(N * N, 0);

    for (int s : order) {
        long long ub = A[s] + globalTopPref[T - 1];
        if (ub <= exactBestScore) break;
        exactUsed[s] = 1;
        exactCurPath = {s};
        exact_dfs(1, s, A[s]);
        exactUsed[s] = 0;
    }
    return exactBestPath;
}

// ---------- Hamiltonian-path randomization ----------
bool backbite_full(vector<int>& path, vector<int>& pos, bool chooseHead, XorShift64& rng) {
    int L = (int)path.size();
    if (chooseHead) {
        int e = path[0];
        int cand[4], m = 0;
        for (int to : adjList[e]) if (pos[to] > 1) cand[m++] = to;
        if (!m) return false;
        int idx = pos[cand[rng.next_int(m)]];
        reverse(path.begin(), path.begin() + idx);
    } else {
        int e = path[L - 1];
        int cand[4], m = 0;
        for (int to : adjList[e]) if (0 <= pos[to] && pos[to] < L - 2) cand[m++] = to;
        if (!m) return false;
        int idx = pos[cand[rng.next_int(m)]];
        reverse(path.begin() + idx + 1, path.end());
    }
    for (int i = 0; i < L; ++i) pos[path[i]] = i;
    return true;
}

inline bool accept_move(long long delta, long double temp, XorShift64& rng) {
    if (delta >= 0) return true;
    if (temp <= 1e-18L) return false;
    long double x = (long double)delta / temp;
    if (x < -50.0L) return false;
    return rng.next_double() < (double)expl(x);
}

int other_corner(int a, int b, int c) {
    auto [ai, aj] = coord(a);
    auto [bi, bj] = coord(b);
    auto [ci, cj] = coord(c);
    int xi = ai + ci - bi;
    int xj = aj + cj - bj;
    if (!(0 <= xi && xi < N && 0 <= xj && xj < N)) return -1;
    int x = vid(xi, xj);
    bool ok1 = false, ok2 = false;
    for (int to : adjList[a]) if (to == x) { ok1 = true; break; }
    for (int to : adjList[c]) if (to == x) { ok2 = true; break; }
    return (ok1 && ok2) ? x : -1;
}

vector<int> solve_heuristic() {
    XorShift64 rng((uint64_t)chrono::high_resolution_clock::now().time_since_epoch().count());
    Timer timer;
    const double TIME_LIMIT = 1.85;

    vector<int> base = base_snake();
    vector<vector<int>> initPaths;
    for (int s = 0; s < 8; ++s) initPaths.push_back(make_sym_path(base, s));

    long long bestScore = -1;
    vector<int> bestPath;
    vector<int> bestFull = initPaths[0];
    for (auto &p : initPaths) {
        auto [sc, l] = best_window_score(p);
        if (sc > bestScore) {
            bestScore = sc;
            bestPath.assign(p.begin() + l, p.begin() + l + T);
            bestFull = p;
        }
    }
    if (T == N * N) return bestFull;

    // Phase 1: random walk on Hamiltonian paths of all 400 cells.
    double phase1End = min(TIME_LIMIT * 0.35, 0.70);
    vector<int> curFull = bestFull;
    vector<int> posFull(N * N, -1);
    rebuild_pos(curFull, posFull);
    int sinceRestart = 0;
    while (timer.elapsed() < phase1End) {
        if (sinceRestart >= 5000) {
            curFull = initPaths[rng.next_int((int)initPaths.size())];
            rebuild_pos(curFull, posFull);
            for (int k = 0; k < 64; ++k) backbite_full(curFull, posFull, rng.next_int(2), rng);
            sinceRestart = 0;
        }
        if (backbite_full(curFull, posFull, rng.next_int(2), rng)) {
            auto [sc, l] = best_window_score(curFull);
            if (sc > bestScore) {
                bestScore = sc;
                bestPath.assign(curFull.begin() + l, curFull.begin() + l + T);
                bestFull = curFull;
            }
        }
        ++sinceRestart;
    }

    // Phase 2: local search on the T-path itself.
    vector<int> cur = bestPath, best = bestPath;
    vector<int> pos(N * N, -1);
    rebuild_pos(cur, pos);
    long long curScore = 0;
    for (int v : cur) curScore += A[v];
    long long bestLocalScore = curScore;
    long long minA = *min_element(A.begin(), A.end());
    long long maxA = *max_element(A.begin(), A.end());
    long double temp0 = max(1000.0L, (long double)(maxA - minA) / 5.0L);
    long double temp1 = 1.0L;
    double phase2Start = timer.elapsed();
    int stagnation = 0;

    while (timer.elapsed() < TIME_LIMIT) {
        double prog = (timer.elapsed() - phase2Start) / max(1e-9, TIME_LIMIT - phase2Start);
        prog = min(1.0, max(0.0, prog));
        long double temp = temp0 * pow(temp1 / temp0, prog);
        int op = rng.next_int(100);

        if (op < 28) {
            // reptation: add at one end, remove opposite end
            bool front = rng.next_int(2) == 0;
            if (front) {
                int cand[4], m = 0;
                for (int to : adjList[cur.front()]) if (pos[to] == -1) cand[m++] = to;
                if (m) {
                    int to = cand[rng.next_int(m)];
                    long long delta = A[to] - A[cur.back()];
                    if (accept_move(delta, temp, rng)) {
                        cur.pop_back();
                        cur.insert(cur.begin(), to);
                        rebuild_pos(cur, pos);
                        curScore += delta;
                    }
                }
            } else {
                int cand[4], m = 0;
                for (int to : adjList[cur.back()]) if (pos[to] == -1) cand[m++] = to;
                if (m) {
                    int to = cand[rng.next_int(m)];
                    long long delta = A[to] - A[cur.front()];
                    if (accept_move(delta, temp, rng)) {
                        cur.erase(cur.begin());
                        cur.push_back(to);
                        rebuild_pos(cur, pos);
                        curScore += delta;
                    }
                }
            }
        } else if (op < 56) {
            // endpoint replacement
            if (T >= 2) {
                bool front = rng.next_int(2) == 0;
                if (front) {
                    int cand[4], m = 0;
                    for (int to : adjList[cur[1]]) if (to != cur[0] && pos[to] == -1) cand[m++] = to;
                    if (m) {
                        int to = cand[rng.next_int(m)];
                        long long delta = A[to] - A[cur[0]];
                        if (accept_move(delta, temp, rng)) {
                            cur[0] = to;
                            rebuild_pos(cur, pos);
                            curScore += delta;
                        }
                    }
                } else {
                    int cand[4], m = 0;
                    for (int to : adjList[cur[T - 2]]) if (to != cur[T - 1] && pos[to] == -1) cand[m++] = to;
                    if (m) {
                        int to = cand[rng.next_int(m)];
                        long long delta = A[to] - A[cur[T - 1]];
                        if (accept_move(delta, temp, rng)) {
                            cur[T - 1] = to;
                            rebuild_pos(cur, pos);
                            curScore += delta;
                        }
                    }
                }
            }
        } else if (op < 80) {
            // corner flip
            if (T >= 3) {
                int i = 1 + rng.next_int(T - 2);
                int x = other_corner(cur[i - 1], cur[i], cur[i + 1]);
                if (x != -1 && pos[x] == -1) {
                    long long delta = A[x] - A[cur[i]];
                    if (accept_move(delta, temp, rng)) {
                        cur[i] = x;
                        rebuild_pos(cur, pos);
                        curScore += delta;
                    }
                }
            }
        } else {
            // neutral backbite
            bool front = rng.next_int(2) == 0;
            if (front) {
                int cand[4], m = 0;
                for (int to : adjList[cur.front()]) if (pos[to] > 1) cand[m++] = to;
                if (m) {
                    int idx = pos[cand[rng.next_int(m)]];
                    reverse(cur.begin(), cur.begin() + idx);
                    rebuild_pos(cur, pos);
                }
            } else {
                int cand[4], m = 0;
                for (int to : adjList[cur.back()]) if (0 <= pos[to] && pos[to] < T - 2) cand[m++] = to;
                if (m) {
                    int idx = pos[cand[rng.next_int(m)]];
                    reverse(cur.begin() + idx + 1, cur.end());
                    rebuild_pos(cur, pos);
                }
            }
        }

        if (curScore > bestLocalScore) {
            bestLocalScore = curScore;
            best = cur;
            stagnation = 0;
        } else {
            ++stagnation;
        }

        if (stagnation > 30000) {
            cur = best;
            curScore = bestLocalScore;
            rebuild_pos(cur, pos);
            for (int k = 0; k < 32; ++k) {
                bool front = rng.next_int(2) == 0;
                if (front) {
                    int cand[4], m = 0;
                    for (int to : adjList[cur.front()]) if (pos[to] > 1) cand[m++] = to;
                    if (m) {
                        int idx = pos[cand[rng.next_int(m)]];
                        reverse(cur.begin(), cur.begin() + idx);
                        rebuild_pos(cur, pos);
                    }
                } else {
                    int cand[4], m = 0;
                    for (int to : adjList[cur.back()]) if (0 <= pos[to] && pos[to] < T - 2) cand[m++] = to;
                    if (m) {
                        int idx = pos[cand[rng.next_int(m)]];
                        reverse(cur.begin() + idx + 1, cur.end());
                        rebuild_pos(cur, pos);
                    }
                }
            }
            stagnation = 0;
        }
    }
    return best;
}

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

    cin >> N >> T;
    A.resize(N * N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) cin >> A[vid(i, j)];
    }
    build_adj();

    vector<int> ans;
    if (T <= 12) ans = solve_exact_small();
    else ans = solve_heuristic();

    if ((int)ans.size() != T || !valid_path(ans)) {
        vector<int> p = base_snake();
        auto [sc, l] = best_window_score(p);
        ans.assign(p.begin() + l, p.begin() + l + T);
    }

    cout << ans.size() << '\n';
    for (int v : ans) {
        auto [i, j] = coord(v);
        cout << i << ' ' << j << '\n';
    }
    return 0;
}