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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: hirakuuuu
• 提出日時: 2026-05-02 18:00:04
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,845 ms / 2,000 ms
• コード長: 12,498 bytes
• コンパイル時間: 4,424 ms
• コンパイル使用メモリ: 366,116 KB
• 実行使用メモリ: 86,656 KB
• スコア: 1,997,698
• 最終ジャッジ日時: 2026-05-02 18:07:56
• 合計ジャッジ時間: 96,366 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_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 = 1800;
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;

template <typename T, int MAX_SIZE>
class StaticPriorityQueue {
private:
    T data[MAX_SIZE];
    int sz;
public:
    StaticPriorityQueue() : sz(0) {}
    inline void clear() { sz = 0; }
    inline bool empty() const { return sz == 0; }
    inline int size() const { return sz; }
    inline void push(const T& val) {
        data[sz] = val;
        std::push_heap(data, data + sz + 1);
        sz++;
    }
    inline const T& top() const { return data[0]; }
    inline void pop() {
        std::pop_heap(data, data + sz);
        sz--;
    }
};

struct State {
    int cur;
    int score;
    int reachable_sum;
    int parent;
    int depth;
    ull hash;
    bitset<400> visited;
};

struct QueueItem {
    int idx;
    static const vector<State> *states;

    bool operator<(const QueueItem &other) const {
        const State &ls = (*states)[idx];
        const State &rs = (*states)[other.idx];
        if(ls.score != rs.score) return ls.score < rs.score;
        if(ls.reachable_sum != rs.reachable_sum) return ls.reachable_sum < rs.reachable_sum;
        return ls.depth < rs.depth;
    }
};
const vector<State> *QueueItem::states = nullptr;

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 NODE_LIMIT = 3000000;
    const int QUEUE_KEEP_LIMIT = 10000;
    const int QUEUE_MAX_SIZE = 20000;
    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);
    };

    array<int, 400> value{};
    rep(i, 0, N) rep(j, 0, N) value[id(i, j)] = A[i][j];

    auto calc_path_score = [&](const vector<int> &path) {
        int score = 0;
        for(int v: path) score += value[v];
        return score;
    };

    vector<int> zigzag_path;
    zigzag_path.reserve(T);
    rep(i, 0, N) {
        if(i % 2 == 0) {
            rep(j, 0, N) {
                if((int)zigzag_path.size() == T) break;
                zigzag_path.push_back(id(i, j));
            }
        }else{
            rrep(j, N - 1, 0) {
                if((int)zigzag_path.size() == T) break;
                zigzag_path.push_back(id(i, j));
            }
        }
        if((int)zigzag_path.size() == T) break;
    }
    int zigzag_score = calc_path_score(zigzag_path);

    array<array<int, 4>, 400> adj;
    array<int, 400> deg{};
    rep(i, 0, N) rep(j, 0, N) {
        int v = id(i, j);
        rep(d, 0, 4) {
            int ni = i + di[d], nj = j + dj[d];
            if(inr(0, ni, N) && inr(0, nj, N)) {
                adj[v][deg[v]++] = id(ni, nj);
            }
        }
    }

    vector<ull> visited_hash(V), cur_hash(V);
    rep(v, 0, V) {
        visited_hash[v] = rng.next_u64();
        cur_hash[v] = rng.next_u64();
    }

    array<int, 400> seen{};
    array<int, 400> dist{};
    array<int, 400> bfs_que{};
    int seen_stamp = 0;
    auto calc_reachable_sum = [&](const State &s, int rest) {
        if(rest <= 0) return 0;

        int sum = 0;
        int head = 0, tail = 0;
        seen_stamp++;
        seen[s.cur] = seen_stamp;
        dist[s.cur] = 0;
        bfs_que[tail++] = s.cur;

        while(head < tail) {
            int v = bfs_que[head++];
            if(dist[v] == rest) continue;

            rep(k, 0, deg[v]) {
                int nv = adj[v][k];
                if(s.visited[nv] || seen[nv] == seen_stamp) continue;
                seen[nv] = seen_stamp;
                dist[nv] = dist[v] + 1;
                sum += value[nv];
                bfs_que[tail++] = nv;
            }
        }
        return sum;
    };

    auto reachable_count = [&](const State &s) {
        int cnt = 0;
        int head = 0, tail = 0;
        seen_stamp++;
        seen[s.cur] = seen_stamp;
        bfs_que[tail++] = s.cur;

        while(head < tail) {
            int v = bfs_que[head++];
            rep(k, 0, deg[v]) {
                int nv = adj[v][k];
                if(s.visited[nv] || seen[nv] == seen_stamp) continue;
                seen[nv] = seen_stamp;
                bfs_que[tail++] = nv;
                cnt++;
            }
        }
        return cnt;
    };

    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.depth > r.depth;
    };

    vector<State> states;
    states.reserve(NODE_LIMIT);
    QueueItem::states = &states;
    using StaticQueue = StaticPriorityQueue<QueueItem, 20000>;
    vector<StaticQueue> que(T + 1);
    vector<unordered_set<ull>> used(T + 1);
    rep(depth, 0, T + 1) used[depth].reserve(8192);

    auto restore_path = [&](int idx) {
        vector<int> path;
        for(int cur_idx = idx; cur_idx != -1; cur_idx = states[cur_idx].parent) {
            path.push_back(states[cur_idx].cur);
        }
        reverse(path.begin(), path.end());
        return path;
    };

    vector<int> best_fill_path;
    int best_fill_score = -1;
    auto update_fill_path = [&](const vector<int> &path, int score) {
        if(score > best_fill_score || (score == best_fill_score && path.size() > best_fill_path.size())) {
            best_fill_score = score;
            best_fill_path = path;
        }
    };

    auto make_fill_path = [&](int idx) {
        const State &base = states[idx];
        vector<int> path = restore_path(idx);
        bitset<400> visited = base.visited;
        int cur = base.cur;
        int score = base.score;

        while((int)path.size() < T) {
            int best_next = -1;
            tuple<int, int, int> best_key = {IINF, -1, -1};

            rep(k, 0, deg[cur]) {
                int nv = adj[cur][k];
                if(visited[nv]) continue;

                int degree = 0;
                rep(kk, 0, deg[nv]) {
                    int nnv = adj[nv][kk];
                    if(!visited[nnv] && nnv != nv) degree++;
                }
                tuple<int, int, int> key = {degree, -value[nv], nv};
                if(key < best_key) {
                    best_key = key;
                    best_next = nv;
                }
            }

            if(best_next == -1) break;

            cur = best_next;
            visited.set(cur);
            path.push_back(cur);
            score += value[cur];
        }

        update_fill_path(path, score);
    };

    rep(v, 0, V) {
        State s;
        s.cur = v;
        s.score = value[v];
        s.parent = -1;
        s.depth = 1;
        s.hash = visited_hash[v] ^ cur_hash[v];
        s.visited.set(v);
        s.reachable_sum = calc_reachable_sum(s, T - 1);
        states.push_back(s);
        int idx = (int)states.size() - 1;
        que[1].push(QueueItem{idx});
        used[1].insert(s.hash);
    }

    int best_idx = 0;
    rep(i, 1, (int)states.size()) {
        if(better(states[i], states[best_idx])) best_idx = i;
    }

    TimeKeeper time_keeper(TIME_LIMIT);
    int time_check_counter = 0;
    auto is_time_over_periodic = [&]() {
        time_check_counter++;
        if((time_check_counter & 255) != 0) return false;
        return time_keeper.isTimeOver();
    };

    while(!time_keeper.isTimeOver()) {
        bool updated = false;

        rrep(depth, T - 1, 1) {
            if((int)states.size() >= NODE_LIMIT || is_time_over_periodic()) break;
            if(que[depth].empty()) continue;

            int idx = que[depth].top().idx;
            que[depth].pop();
            const State &s = states[idx];
            updated = true;

            int rest = T - s.depth;
            if(rest > 0 && reachable_count(s) <= rest) {
                make_fill_path(idx);
            }

            rep(k, 0, deg[s.cur]) {
                int nv = adj[s.cur][k];
                if((int)states.size() >= NODE_LIMIT || is_time_over_periodic()) break;
                if(s.visited[nv]) continue;

                ull next_hash = s.hash ^ cur_hash[s.cur] ^ cur_hash[nv] ^ visited_hash[nv];
                if(used[depth + 1].find(next_hash) != used[depth + 1].end()) continue;

                State ns;
                ns.cur = nv;
                ns.score = s.score + value[nv];
                ns.parent = idx;
                ns.depth = s.depth + 1;
                ns.hash = next_hash;
                ns.visited = s.visited;
                ns.visited.set(nv);
                ns.reachable_sum = calc_reachable_sum(ns, T - ns.depth);

                states.emplace_back(std::move(ns));
                int new_idx = (int)states.size() - 1;
                used[states[new_idx].depth].insert(states[new_idx].hash);
                auto &next_que = que[states[new_idx].depth];
                if(next_que.size() == QUEUE_MAX_SIZE) {
                    vector<QueueItem> kept;
                    kept.reserve(QUEUE_KEEP_LIMIT);
                    rep(i, 0, QUEUE_KEEP_LIMIT) {
                        kept.push_back(next_que.top());
                        next_que.pop();
                    }
                    next_que.clear();
                    for(const QueueItem &item: kept) next_que.push(item);
                }
                next_que.push(QueueItem{new_idx});
                if(better(states[new_idx], states[best_idx])) {
                    best_idx = new_idx;
                }
            }
        }

        if(!updated || (int)states.size() >= NODE_LIMIT) break;
    }

    vector<int> answer = restore_path(best_idx);
    if(best_fill_score > states[best_idx].score ||
       (best_fill_score == states[best_idx].score && best_fill_path.size() > answer.size())) {
        answer = best_fill_path;
    }

    int answer_score = calc_path_score(answer);
    if(zigzag_score > answer_score) {
        answer = zigzag_path;
        answer_score = zigzag_score;
    }
    cerr << "score: " << answer_score << '\n';

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