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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: hirakuuuu
• 提出日時: 2026-05-02 17:13:31
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 720 ms / 2,000 ms
• コード長: 5,515 bytes
• コンパイル時間: 4,390 ms
• コンパイル使用メモリ: 359,380 KB
• 実行使用メモリ: 6,696 KB
• スコア: 1,628,245
• 最終ジャッジ日時: 2026-05-02 17:14:09
• 合計ジャッジ時間: 35,610 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define rrep(i, a, n) for(int i = a; i >= n; i--)
#define inr(l, x, r) (l <= x && x < r)
#define ll long long
#define ld long double
#define ull unsigned long long

// using mint = modint1000000007;
// using mint = modint998244353;
constexpr int IINF = 1001001001;
constexpr ll INF = 1e18;

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

const int TIME_LIMIT = 1900;
class TimeKeeper {
private:
    chrono::high_resolution_clock::time_point start_time_;
    ll time_threshold_;
public:
    TimeKeeper(const ll &time_threshold)
        : start_time_(chrono::high_resolution_clock::now()),
          time_threshold_(time_threshold) {}
    bool isTimeOver() const {
        using chrono::duration_cast;
        using chrono::milliseconds;
        auto diff = chrono::high_resolution_clock::now() - this->start_time_;
        return duration_cast<milliseconds>(diff).count() >= time_threshold_;
    }
    double elapsed_time() const {
        using chrono::duration_cast;
        using chrono::milliseconds;
        auto diff = chrono::high_resolution_clock::now() - this->start_time_;
        return static_cast<double>(duration_cast<milliseconds>(diff).count());
    }
    double progress() const {
        using chrono::duration_cast;
        using chrono::milliseconds;
        auto diff = chrono::high_resolution_clock::now() - this->start_time_;
        return static_cast<double>(duration_cast<milliseconds>(diff).count()) / (double)time_threshold_;
    }
};

struct XorShift64 {
    ull x = 88172645463393265ull;
    inline ull next_u64(){ 
        x ^= x << 7; 
        x ^= x >> 9; 
        return x;
    }
    inline uint32_t next_u32(){
        return (uint32_t)next_u64(); 
    }
    // [lo, hi] の整数を一様にランダムに返す
    inline int next_int(int lo, int hi) {
        return lo + (int)(next_u32() % (uint32_t)(hi - lo + 1));
    }
    // [0, 1) の実数を一様にランダムに返す
    inline double next_double01() {
        ull r = next_u64();
        r = (r >> 11) | 1ULL; 
        return (double)r * (1.0 / 9007199254740992.0);
    }
};
XorShift64 rng;

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

    int N, T;
    cin >> N >> T;
    vector<vector<int>> A(N, vector<int>(N));
    rep(i, 0, N) rep(j, 0, N) cin >> A[i][j];

    const int V = N * N;
    const int BEAM_WIDTH = 400;
    const int di[4] = {-1, 1, 0, 0};
    const int dj[4] = {0, 0, -1, 1};

    auto id = [&](int i, int j) {
        return i * N + j;
    };
    auto pos = [&](int v) {
        return pair<int, int>(v / N, v % N);
    };

    vector<vector<int>> adj(V);
    rep(i, 0, N) rep(j, 0, N) {
        rep(d, 0, 4) {
            int ni = i + di[d], nj = j + dj[d];
            if(inr(0, ni, N) && inr(0, nj, N)) {
                adj[id(i, j)].push_back(id(ni, nj));
            }
        }
    }

    struct State {
        int cur;
        int score;
        int reachable_sum;
        bitset<400> visited;
        vector<int> path;
    };

    auto calc_reachable_sum = [&](const State &s, int rest) {
        if(rest <= 0) return 0;

        int sum = 0;
        array<int, 400> dist;
        dist.fill(-1);
        queue<int> que;
        dist[s.cur] = 0;
        que.push(s.cur);

        while(!que.empty()) {
            int v = que.front();
            que.pop();
            if(dist[v] == rest) continue;

            for(int nv: adj[v]) {
                if(s.visited[nv] || dist[nv] != -1) continue;
                dist[nv] = dist[v] + 1;
                sum += A[nv / N][nv % N];
                que.push(nv);
            }
        }
        return sum;
    };

    auto better = [](const State &l, const State &r) {
        if(l.score != r.score) return l.score > r.score;
        if(l.reachable_sum != r.reachable_sum) return l.reachable_sum > r.reachable_sum;
        return l.path.size() > r.path.size();
    };

    vector<State> beam;
    beam.reserve(V);
    rep(v, 0, V) {
        State s;
        s.cur = v;
        s.score = A[v / N][v % N];
        s.visited.set(v);
        s.path.push_back(v);
        s.reachable_sum = calc_reachable_sum(s, T - 1);
        beam.push_back(s);
    }

    State best = *max_element(beam.begin(), beam.end(), better);

    rep(turn, 1, T) {
        vector<State> next_beam;
        next_beam.reserve(min(BEAM_WIDTH * 4, 200000));

        for(const State &s: beam) {
            for(int nv: adj[s.cur]) {
                if(s.visited[nv]) continue;

                State ns = s;
                ns.cur = nv;
                ns.score += A[nv / N][nv % N];
                ns.visited.set(nv);
                ns.path.push_back(nv);
                ns.reachable_sum = calc_reachable_sum(ns, T - (int)ns.path.size());
                next_beam.push_back(std::move(ns));
            }
        }

        if(next_beam.empty()) break;

        sort(next_beam.begin(), next_beam.end(), better);
        if((int)next_beam.size() > BEAM_WIDTH) {
            next_beam.resize(BEAM_WIDTH);
        }

        if(better(next_beam.front(), best)) {
            best = next_beam.front();
        }
        beam = std::move(next_beam);
    }

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