#1162563 (C++17(gnu拡張)) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: Ojun
• 提出日時: 2026-05-02 17:45:29
• 言語: C++17(gnu拡張) (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,957 ms / 2,000 ms
• コード長: 11,123 bytes
• コンパイル時間: 1,576 ms
• コンパイル使用メモリ: 176,572 KB
• 実行使用メモリ: 6,400 KB
• スコア: 1,528,835
• 最終ジャッジ日時: 2026-05-02 17:47:14
• 合計ジャッジ時間: 103,371 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

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

ソースコード

#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <limits>
#include <functional>
#include <random>
#include <vector>
using namespace std;

struct State {
    int start_i;
    int start_j;
    int target_block;
    int cell_w;
    int block_w;
    int dist_w;
    int explore_w;
};

struct Result {
    vector<pair<int, int>> path;
    long long score = -1;
};

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

    int N, T;
    cin >> N >> T;

    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    const int B = 3;
    const int BR = (N + B - 1) / B;
    const int BC = (N + B - 1) / B;
    const int BCNT = BR * BC;

    vector<vector<int>> block_sum(BR, vector<int>(BC, 0));
    vector<vector<pair<int, int>>> block_cells(BR * BC);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int bi = i / B;
            int bj = j / B;
            block_sum[bi][bj] += A[i][j];
            block_cells[bi * BC + bj].push_back({i, j});
        }
    }

    vector<int> block_order(BCNT);
    for (int i = 0; i < BCNT; i++) block_order[i] = i;
    sort(block_order.begin(), block_order.end(), [&](int lhs, int rhs) {
        int lbi = lhs / BC;
        int lbj = lhs % BC;
        int rbi = rhs / BC;
        int rbj = rhs % BC;
        if (block_sum[lbi][lbj] != block_sum[rbi][rbj]) return block_sum[lbi][lbj] > block_sum[rbi][rbj];
        return lhs < rhs;
    });

    vector<pair<int, int>> top_cells;
    top_cells.reserve(N * N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            top_cells.push_back({i, j});
        }
    }
    sort(top_cells.begin(), top_cells.end(), [&](const auto &lhs, const auto &rhs) {
        if (A[lhs.first][lhs.second] != A[rhs.first][rhs.second]) return A[lhs.first][lhs.second] > A[rhs.first][rhs.second];
        int lb = (lhs.first / B) * BC + (lhs.second / B);
        int rb = (rhs.first / B) * BC + (rhs.second / B);
        if (block_sum[lhs.first / B][lhs.second / B] != block_sum[rhs.first / B][rhs.second / B]) {
            return block_sum[lhs.first / B][lhs.second / B] > block_sum[rhs.first / B][rhs.second / B];
        }
        return lb < rb;
    });

    auto evaluate_start = [&](int si, int sj) -> long long {
        bool visited[20][20] = {};
        long long best = A[si][sj];
        const int di[4] = {-1, 1, 0, 0};
        const int dj[4] = {0, 0, -1, 1};

        auto dfs = [&](auto &&self, int ci, int cj, int depth, long long sum) -> void {
            if (sum > best) best = sum;
            if (depth == 7) return;
            for (int dir = 0; dir < 4; dir++) {
                int ni = ci + di[dir];
                int nj = cj + dj[dir];
                if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
                if (visited[ni][nj]) continue;
                visited[ni][nj] = true;
                self(self, ni, nj, depth + 1, sum + A[ni][nj]);
                visited[ni][nj] = false;
            }
        };

        visited[si][sj] = true;
        dfs(dfs, si, sj, 0, A[si][sj]);
        return best;
    };

    int best_start_i = 0;
    int best_start_j = 0;
    long long best_start_score = -1;
    int start_limit = min<int>(40, (int)top_cells.size());
    for (int idx = 0; idx < start_limit; idx++) {
        int i = top_cells[idx].first;
        int j = top_cells[idx].second;
        long long score = evaluate_start(i, j);
        if (score > best_start_score || (score == best_start_score && A[i][j] > A[best_start_i][best_start_j])) {
            best_start_score = score;
            best_start_i = i;
            best_start_j = j;
        }
    }

    mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());

    auto block_dist = [&](int bi, int bj, int ti, int tj) {
        return abs(bi - ti) + abs(bj - tj);
    };

    auto build_path = [&](const State &st) -> Result {
        Result res;
        res.score = 0;
        vector<vector<bool>> visited(N, vector<bool>(N, false));
        vector<vector<bool>> block_used(BR, vector<bool>(BC, false));
        int cur_i = st.start_i;
        int cur_j = st.start_j;
        visited[cur_i][cur_j] = true;
        block_used[cur_i / B][cur_j / B] = true;
        res.path.push_back({cur_i, cur_j});
        res.score += A[cur_i][cur_j];

        int ti = st.target_block / BC;
        int tj = st.target_block % BC;
        const int di[4] = {-1, 1, 0, 0};
        const int dj[4] = {0, 0, -1, 1};

        auto eval_cell = [&](int i, int j) -> long long {
            int bi = i / B;
            int bj = j / B;
            long long val = 1LL * st.cell_w * A[i][j] + 1LL * st.block_w * block_sum[bi][bj] - 1LL * st.dist_w * block_dist(bi, bj, ti, tj);
            if (!block_used[bi][bj]) val += st.explore_w;
            return val;
        };

        while ((int)res.path.size() < T) {
            int best_i = -1;
            int best_j = -1;
            long long best_val = numeric_limits<long long>::min();
            int best_a = -1;
            int best_first_block_sum = -1;
            int remaining = T - (int)res.path.size();
            int max_depth = min(5, remaining);

            auto dfs = [&](auto &&self, int ci, int cj, int depth, long long sum, int first_i, int first_j) -> void {
                if (depth > 0) {
                    if (sum > best_val || (sum == best_val && A[first_i][first_j] > best_a) || (sum == best_val && A[first_i][first_j] == best_a && block_sum[first_i / B][first_j / B] > best_first_block_sum)) {
                        best_val = sum;
                        best_i = first_i;
                        best_j = first_j;
                        best_a = A[first_i][first_j];
                        best_first_block_sum = block_sum[first_i / B][first_j / B];
                    }
                }
                if (depth == max_depth) return;

                bool expanded = false;
                for (int dir = 0; dir < 4; dir++) {
                    int ni = ci + di[dir];
                    int nj = cj + dj[dir];
                    if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
                    if (visited[ni][nj]) continue;
                    expanded = true;
                    visited[ni][nj] = true;
                    int bi = ni / B;
                    int bj = nj / B;
                    bool was_block_used = block_used[bi][bj];
                    block_used[bi][bj] = true;
                    int next_first_i = (depth == 0 ? ni : first_i);
                    int next_first_j = (depth == 0 ? nj : first_j);
                    self(self, ni, nj, depth + 1, sum + eval_cell(ni, nj), next_first_i, next_first_j);
                    block_used[bi][bj] = was_block_used;
                    visited[ni][nj] = false;
                }

                if (!expanded && depth == 0) {
                    return;
                }
            };

            visited[cur_i][cur_j] = true;
            block_used[cur_i / B][cur_j / B] = true;
            dfs(dfs, cur_i, cur_j, 0, 0, -1, -1);

            if (best_i == -1) break;
            cur_i = best_i;
            cur_j = best_j;
            visited[cur_i][cur_j] = true;
            block_used[cur_i / B][cur_j / B] = true;
            res.path.push_back({cur_i, cur_j});
            res.score += A[cur_i][cur_j];
        }

        return res;
    };

    auto make_state = [&](int target_idx, int cell_w, int block_w, int dist_w, int explore_w) {
        State st;
        st.start_i = best_start_i;
        st.start_j = best_start_j;
        st.target_block = target_idx;
        st.cell_w = cell_w;
        st.block_w = block_w;
        st.dist_w = dist_w;
        st.explore_w = explore_w;
        return st;
    };

    auto start_time = chrono::steady_clock::now();
    const double TIME_LIMIT = 1.95;

    Result best_res;
    long long best_score = -1;
    State current_state{};
    long long current_score = -1;

    vector<int> target_candidates;
    for (int i = 0; i < min<int>(30, BCNT); i++) target_candidates.push_back(block_order[i]);

    vector<State> seeds;
    if (!target_candidates.empty()) {
        seeds.push_back(make_state(target_candidates[0], 4, 3, 2, 2));
        seeds.push_back(make_state(target_candidates[0], 3, 4, 2, 1));
        seeds.push_back(make_state(target_candidates[min<int>(3, (int)target_candidates.size() - 1)], 5, 2, 3, 2));
        seeds.push_back(make_state(target_candidates[min<int>(5, (int)target_candidates.size() - 1)], 4, 4, 1, 3));
        seeds.push_back(make_state(target_candidates[min<int>(8, (int)target_candidates.size() - 1)], 6, 2, 2, 2));
    }

    for (const State &st : seeds) {
        Result res = build_path(st);
        if (res.score > best_score || best_res.path.empty()) {
            best_score = res.score;
            best_res = res;
            current_state = st;
            current_score = res.score;
        }
    }

    if (best_res.path.empty()) {
        State st;
        st.start_i = best_start_i;
        st.start_j = best_start_j;
        st.target_block = 0;
        st.cell_w = 4;
        st.block_w = 3;
        st.dist_w = 2;
        st.explore_w = 2;
        best_res = build_path(st);
        current_state = st;
        best_score = best_res.score;
        current_score = best_res.score;
    }

    uniform_real_distribution<double> dist01(0.0, 1.0);
    auto now_sec = [&]() {
        return chrono::duration<double>(chrono::steady_clock::now() - start_time).count();
    };

    while (now_sec() < TIME_LIMIT) {
        State next = current_state;
        int move_type = (int)(rng() % 5);
        if (move_type == 0) {
            next.target_block = target_candidates[rng() % target_candidates.size()];
        } else if (move_type == 1) {
            next.cell_w = max(1, min(8, next.cell_w + (int)(rng() % 3) - 1));
        } else if (move_type == 2) {
            next.block_w = max(0, min(8, next.block_w + (int)(rng() % 3) - 1));
        } else if (move_type == 3) {
            next.dist_w = max(0, min(8, next.dist_w + (int)(rng() % 3) - 1));
        } else {
            next.explore_w = max(0, min(8, next.explore_w + (int)(rng() % 3) - 1));
        }

        Result cand = build_path(next);
        double t = now_sec() / TIME_LIMIT;
        double temp = 300.0 * (1.0 - t) + 1.0;

        if (cand.score > best_score) {
            best_score = cand.score;
            best_res = cand;
        }
        bool accept = false;
        if (cand.score >= current_score) {
            accept = true;
        } else {
            double diff = (double)(cand.score - current_score);
            double prob = exp(diff / temp);
            if (dist01(rng) < prob) accept = true;
        }

        if (accept) {
            current_state = next;
            current_score = cand.score;
        }
    }

    cout << best_res.path.size() << '\n';
    for (const auto &p : best_res.path) {
        cout << p.first << ' ' << p.second << '\n';
    }

    return 0;
}