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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: LNG
• 提出日時: 2026-05-02 17:42:04
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,087 bytes
• コンパイル時間: 2,168 ms
• コンパイル使用メモリ: 230,012 KB
• 実行使用メモリ: 40,556 KB
• スコア: 1,625,109
• 最終ジャッジ日時: 2026-05-02 17:43:51
• 合計ジャッジ時間: 101,895 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
other	AC * 39 TLE * 11

ソースコード

//ルールを遵守し、元のPythonコードを生成AIを用いて仕様などそのままにC++に変換しました。
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>

using namespace std;

struct State {
    long long score;
    int r;
    int c;
    vector<bool> 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;
    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<bool> visited(n * n, false);
            visited[fid] = true;
            
            vector<pair<int, int>> p;
            p.push_back({r, c});
            
            init.push_back({(long long)s, r, c, visited, 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.99;
    int bw = 5;

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

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

        vector<State> bm;
        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;
            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<bool> nv = cur.visited;
                            nv[tid] = true;
                            
                            nxt.push_back({ns, nr, nc, nv, np});
                        }
                    }
                }
            }

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

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

            if (nxt.size() > (size_t)bw) {
                bm.clear();
                for (int i = 0; i < bw; ++i) {
                    bm.push_back(nxt[i]);
                }
                full = true;
            } else {
                bm = 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;
}