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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: hakatashi
• 提出日時: 2026-04-24 14:48:34
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,888 ms / 2,000 ms
• コード長: 6,969 bytes
• コンパイル時間: 3,829 ms
• コンパイル使用メモリ: 274,848 KB
• 実行使用メモリ: 162,504 KB
• スコア: 2,073,355
• 最終ジャッジ日時: 2026-05-02 16:35:19
• 合計ジャッジ時間: 106,057 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

// Implementation by Gemini CLI - v10_final_optimized.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <random>
#include <queue>
#include <unordered_map>

using namespace std;

int N, T;
int A[20][20];
uint64_t zobrist[400];
int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};

struct State {
    int r, c;
    long long score;
    int parent_idx;
    bitset<400> visited;
    uint64_t hash;
    double eval_score;
    bool operator<(const State& other) const { return eval_score < other.eval_score; }
};

struct SavedState { int r, c; int parent_idx; };

vector<pair<int, int>> run_chokudai(chrono::steady_clock::time_point start_time, double time_limit) {
    priority_queue<State> queues[405];
    vector<SavedState> history[405];
    unordered_map<uint64_t, long long> seen[405];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            State s; s.r = i; s.c = j; s.score = A[i][j]; s.parent_idx = -1;
            s.visited.set(i * N + j); s.hash = zobrist[i * N + j];
            int deg = 0;
            for(int d=0; d<4; d++){
                int nr=i+dr[d], nc=j+dc[d];
                if(nr>=0 && nr<N && nc>=0 && nc<N) deg++;
            }
            s.eval_score = s.score + deg * 30.0;
            queues[1].push(s);
        }
    }

    long long best_total_score = -1;
    int best_total_step = -1, best_total_idx = -1;
    int loop = 0;
    while (true) {
        if (++loop % 200 == 0) {
            if (chrono::duration<double>(chrono::steady_clock::now() - start_time).count() > time_limit) break;
        }
        bool pushed = false;
        for (int t = 1; t <= T; t++) {
            if (queues[t].empty()) continue;
            State s = queues[t].top(); queues[t].pop();
            uint64_t state_key = s.hash ^ (uint64_t(s.r * N + s.c) << 32);
            if (seen[t].count(state_key) && seen[t][state_key] >= s.score) continue;
            seen[t][state_key] = s.score;
            int current_idx = history[t].size();
            history[t].push_back({s.r, s.c, s.parent_idx});
            if (s.score > best_total_score) {
                best_total_score = s.score; best_total_step = t; best_total_idx = current_idx;
            }
            if (t >= T) continue;
            for (int d = 0; d < 4; d++) {
                int nr = s.r + dr[d], nc = s.c + dc[d];
                if (nr >= 0 && nr < N && nc >= 0 && nc < N && !s.visited.test(nr * N + nc)) {
                    State next_s; next_s.r = nr; next_s.c = nc; next_s.score = s.score + A[nr][nc];
                    next_s.parent_idx = current_idx; next_s.visited = s.visited;
                    next_s.visited.set(nr * N + nc); next_s.hash = s.hash ^ zobrist[nr * N + nc];
                    int deg = 0;
                    for(int d2=0; d2<4; d2++){
                        int nnr=nr+dr[d2], nnc=nc+dc[d2];
                        if(nnr>=0 && nnr<N && nnc>=0 && nnc<N && !next_s.visited.test(nnr*N+nnc)) deg++;
                    }
                    next_s.eval_score = next_s.score + deg * 60.0;
                    uint64_t next_state_key = next_s.hash ^ (uint64_t(nr * N + nc) << 32);
                    if (!seen[t+1].count(next_state_key) || seen[t+1][next_state_key] < next_s.score) {
                        queues[t+1].push(next_s); pushed = true;
                    }
                }
            }
        }
        if (!pushed) {
            bool any = false;
            for(int t=1; t<=T; t++) if(!queues[t].empty()) any=true;
            if(!any) break;
        }
    }
    vector<pair<int, int>> path;
    int curr_t = best_total_step, curr_idx = best_total_idx;
    while (curr_t >= 1) {
        path.push_back({history[curr_t][curr_idx].r, history[curr_t][curr_idx].c});
        curr_idx = history[curr_t][curr_idx].parent_idx; curr_t--;
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    auto start_time = chrono::steady_clock::now();
    mt19937 rng(42); mt19937_64 rng64(42);
    for (int i = 0; i < 400; i++) zobrist[i] = rng64();
    if (!(cin >> N >> T)) return 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> A[i][j];

    vector<pair<int, int>> best_path = run_chokudai(start_time, 1.2);
    long long best_score = 0;
    for (auto p : best_path) best_score += A[p.first][p.second];

    while (chrono::duration<double>(chrono::steady_clock::now() - start_time).count() < 1.88) {
        int k = uniform_int_distribution<int>(0, (int)best_path.size() - 2)(rng);
        vector<pair<int, int>> current_path;
        bitset<400> visited;
        long long current_score = 0;
        for (int i = 0; i <= k; i++) {
            current_path.push_back(best_path[i]);
            visited.set(best_path[i].first * N + best_path[i].second);
            current_score += A[best_path[i].first][best_path[i].second];
        }

        while (current_path.size() < T) {
            int r = current_path.back().first, c = current_path.back().second;
            vector<pair<int, int>> candidates;
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr >= 0 && nr < N && nc >= 0 && nc < N && !visited.test(nr * N + nc)) {
                    candidates.push_back({nr, nc});
                }
            }
            if (candidates.empty()) break;
            
            // 2-step look-ahead
            vector<pair<double, int>> scores;
            for (int i = 0; i < (int)candidates.size(); i++) {
                int cr = candidates[i].first, cc = candidates[i].second;
                double max_next_val = 0;
                int deg = 0;
                for (int d2 = 0; d2 < 4; d2++) {
                    int nnr = cr + dr[d2], nnc = cc + dc[d2];
                    if (nnr >= 0 && nnr < N && nnc >= 0 && nnc < N && !visited.test(nnr * N + nnc) && (nnr != r || nnc != c)) {
                        max_next_val = max(max_next_val, (double)A[nnr][nnc]);
                        deg++;
                    }
                }
                scores.push_back({A[cr][cc] + max_next_val * 0.5 + deg * 10.0, i});
            }
            sort(scores.rbegin(), scores.rend());
            
            int idx = scores[0].second;
            if (scores.size() > 1 && uniform_real_distribution<double>(0, 1)(rng) < 0.2) {
                idx = scores[uniform_int_distribution<int>(0, min((int)scores.size()-1, 2))(rng)].second;
            }
            
            current_path.push_back(candidates[idx]);
            visited.set(candidates[idx].first * N + candidates[idx].second);
            current_score += A[candidates[idx].first][candidates[idx].second];
        }

        if (current_score > best_score) {
            best_score = current_score;
            best_path = current_path;
        }
    }

    cout << (int)best_path.size() << endl;
    for (auto p : best_path) cout << p.first << " " << p.second << endl;
    return 0;
}