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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: LNG
• 提出日時: 2026-05-02 19:01:26
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,993 ms / 2,000 ms
• コード長: 5,476 bytes
• コンパイル時間: 2,721 ms
• コンパイル使用メモリ: 224,876 KB
• 実行使用メモリ: 6,400 KB
• スコア: 2,185,310
• 最終ジャッジ日時: 2026-05-02 19:03:12
• 合計ジャッジ時間: 105,803 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

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

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <iostream>
#include <chrono>
#include <cmath>
#include <algorithm>

using namespace std;

struct Xorshift {
    uint32_t x = 123456789;
    uint32_t y = 362436069;
    uint32_t z = 521288629;
    uint32_t w = 88675123;
    inline uint32_t next() {
        uint32_t t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
    inline double nextDouble() {
        return next() / 4294967296.0;
    }
    inline int nextInt(int L, int R) {
        return L + next() % (R - L + 1);
    }
};

int N, T_max;
int A[400];
int adj[400][4];
int adj_deg[400];

struct State {
    int path[400];
    int len;
    bool visited[400];
    int score;
    
    inline void init() {
        len = 0;
        score = 0;
        for(int i = 0; i < 400; ++i) visited[i] = false;
    }
    
    inline void push(int u) {
        path[len++] = u;
        visited[u] = true;
        score += A[u];
    }
    
    inline int pop() {
        int u = path[--len];
        visited[u] = false;
        score -= A[u];
        return u;
    }
};

State generate_initial(Xorshift& rnd) {
    State best;
    best.score = -1;
    
    for(int i = 0; i < 5000; ++i) {
        State s;
        s.init();
        int start = rnd.nextInt(0, N * N - 1);
        s.push(start);
        
        while(s.len < T_max) {
            int u = s.path[s.len - 1];
            int best_v = -1;
            int max_a = -1;
            int cands[4];
            int cands_sz = 0;
            
            for(int k = 0; k < adj_deg[u]; ++k) {
                int v = adj[u][k];
                if(!s.visited[v]) {
                    cands[cands_sz++] = v;
                    if(A[v] > max_a) {
                        max_a = A[v];
                        best_v = v;
                    }
                }
            }
            if(cands_sz == 0) break;
            
            int nxt;
            if(rnd.nextDouble() < 0.8 && best_v != -1) {
                nxt = best_v;
            } else {
                nxt = cands[rnd.nextInt(0, cands_sz - 1)];
            }
            s.push(nxt);
        }
        if(s.score > best.score) best = s;
    }
    return best;
}

inline void mutate(State& s, Xorshift& rnd) {
    if(s.len > 1 && rnd.nextDouble() < 0.5) {
        int half = s.len / 2;
        for(int i = 0; i < half; ++i) {
            int tmp = s.path[i];
            s.path[i] = s.path[s.len - 1 - i];
            s.path[s.len - 1 - i] = tmp;
        }
    }
    
    if(s.len > 1) {
        double r = rnd.nextDouble();
        int pop_len = 1 + (int)(r * r * (s.len - 1));
        if(pop_len > s.len - 1) pop_len = s.len - 1;
        
        for(int i = 0; i < pop_len; ++i) {
            s.pop();
        }
    }
    
    while(s.len < T_max) {
        int u = s.path[s.len - 1];
        int best_v = -1;
        int max_a = -1;
        int cands[4];
        int cands_sz = 0;
        
        for(int k = 0; k < adj_deg[u]; ++k) {
            int v = adj[u][k];
            if(!s.visited[v]) {
                cands[cands_sz++] = v;
                if(A[v] > max_a) {
                    max_a = A[v];
                    best_v = v;
                }
            }
        }
        if(cands_sz == 0) break;
        
        int nxt;
        if(rnd.nextDouble() < 0.7 && best_v != -1) {
            nxt = best_v;
        } else {
            nxt = cands[rnd.nextInt(0, cands_sz - 1)];
        }
        s.push(nxt);
    }
}

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

    if (!(cin >> N >> T_max)) return 0;

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

    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            int u = i * N + j;
            adj_deg[u] = 0;
            if(i > 0) adj[u][adj_deg[u]++] = (i - 1) * N + j;
            if(i < N - 1) adj[u][adj_deg[u]++] = (i + 1) * N + j;
            if(j > 0) adj[u][adj_deg[u]++] = i * N + j - 1;
            if(j < N - 1) adj[u][adj_deg[u]++] = i * N + j + 1;
        }
    }

    Xorshift rnd;
    
    auto start_clock = chrono::steady_clock::now();
    double start_time = chrono::duration_cast<chrono::nanoseconds>(start_clock.time_since_epoch()).count() * 1e-9;
    double time_limit = 1.99;

    State cur = generate_initial(rnd);
    State best = cur;

    double T0 = 5000.0;
    double T1 = 10.0;

    int iter = 0;
    double current_time = 0.0;
    
    while(true) {
        if((iter & 1023) == 0) {
            auto now_clock = chrono::steady_clock::now();
            current_time = chrono::duration_cast<chrono::nanoseconds>(now_clock.time_since_epoch()).count() * 1e-9 - start_time;
            if(current_time > time_limit) break;
        }
        iter++;
        
        State nxt = cur;
        mutate(nxt, rnd);
        
        int diff = nxt.score - cur.score;
        
        if(diff >= 0) {
            cur = nxt;
            if(cur.score > best.score) {
                best = cur;
            }
        } else {
            double progress = current_time / time_limit;
            double temp = T0 * pow(T1 / T0, progress);
            if(rnd.nextDouble() < exp(diff / temp)) {
                cur = nxt;
            }
        }
    }

    cout << best.len << "\n";
    for(int i = 0; i < best.len; ++i) {
        cout << best.path[i] / N << " " << best.path[i] % N << "\n";
    }

    return 0;
}