#1162597 (C++23) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: LNG
• 提出日時: 2026-05-02 17:55:07
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,984 ms / 2,000 ms
• コード長: 4,172 bytes
• コンパイル時間: 3,034 ms
• コンパイル使用メモリ: 233,180 KB
• 実行使用メモリ: 60,248 KB
• スコア: 1,919,700
• 最終ジャッジ日時: 2026-05-02 17:58:57
• 合計ジャッジ時間: 105,601 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

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

ソースコード

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <cstdint>

using namespace std;

struct State {
    long long score;
    int r;
    int c;
    vector<uint8_t> visited;
    vector<pair<int, int>> path;

    bool operator<(const State& other) const {
        return score > other.score; 
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    auto start = chrono::steady_clock::now();

    int n, t;
    if (!(cin >> n >> t)) {
        return 0;
    }

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

    vector<State> init;
    init.reserve(n * n);

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) {
            int s = g[r][c];
            int fid = r * n + c;
            
            vector<uint8_t> visited(n * n, 0);
            visited[fid] = 1;
            
            vector<pair<int, int>> p;
            p.reserve(t);
            p.push_back({r, c});
            
            init.push_back({(long long)s, r, c, move(visited), move(p)});
        }
    }

    vector<pair<int, int>> res_p;
    long long mx = -1;

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    double lim = 1.95;
    int bw = 5;

    sort(init.begin(), init.end());

    while (true) {
        auto now = chrono::steady_clock::now();
        chrono::duration<double> diff = now - start;
        if (diff.count() > lim) {
            break;
        }

        vector<State> bm;
        bm.reserve(bw);
        bool full = false;
        if (init.size() > (size_t)bw) {
            for (int i = 0; i < bw; ++i) {
                bm.push_back(init[i]);
            }
            full = true;
        } else {
            bm = init;
        }

        bool over = false;
        for (int step = 0; step < t - 1; ++step) {
            vector<State> nxt;
            nxt.reserve(bm.size() * 3);

            for (const auto& cur : bm) {
                long long cs = cur.score;
                int cr = cur.r;
                int cc = cur.c;
                
                if (cs > mx) {
                    mx = cs;
                    res_p = cur.path;
                }

                for (int i = 0; i < 4; ++i) {
                    int nr = cr + dr[i];
                    int nc = cc + dc[i];

                    if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                        int tid = nr * n + nc;
                        
                        if (!cur.visited[tid]) {
                            long long ns = cs + g[nr][nc];
                            vector<pair<int, int>> np = cur.path;
                            np.push_back({nr, nc});
                            
                            vector<uint8_t> nv = cur.visited;
                            nv[tid] = 1;
                            
                            nxt.push_back({ns, nr, nc, move(nv), move(np)});
                        }
                    }
                }
            }

            if (nxt.empty()) {
                break;
            }

            if (nxt.size() > (size_t)bw) {
                nth_element(nxt.begin(), nxt.begin() + bw, nxt.end());
                nxt.resize(bw);
                sort(nxt.begin(), nxt.end());
                bm = move(nxt);
                full = true;
            } else {
                sort(nxt.begin(), nxt.end());
                bm = move(nxt);
            }

            auto now_inner = chrono::steady_clock::now();
            chrono::duration<double> diff_inner = now_inner - start;
            if (diff_inner.count() > lim) {
                over = true;
                break;
            }
        }

        for (const auto& fst : bm) {
            if (fst.score > mx) {
                mx = fst.score;
                res_p = fst.path;
            }
        }

        if (over || !full) {
            break;
        }

        bw = (int)(bw * 1.5);
    }

    cout << res_p.size() << "\n";
    for (const auto& pos : res_p) {
        cout << pos.first << " " << pos.second << "\n";
    }

    return 0;
}