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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: fepic_
• 提出日時: 2026-06-20 19:01:39
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,979 ms / 2,000 ms
• コード長: 5,692 bytes
• コンパイル時間: 1,074 ms
• コンパイル使用メモリ: 131,928 KB
• 実行使用メモリ: 6,400 KB
• スコア: 2,073,695
• 最終ジャッジ日時: 2026-06-20 19:03:28
• 合計ジャッジ時間: 102,757 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

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

ソースコード

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cmath>
#include <algorithm>

using namespace std;

// 高速な符号なし32bit整数乱数 (mt19937より高速なXorshiftを使用)
struct Xorshift {
    uint32_t x = 123456789, y = 362436069, z = 520041723, w = 88675123;
    uint32_t operator()() {
        uint32_t t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
} mt;

int n, t;
int a[20][20];
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct state {
    int sx, sy;
    int dir[20][20]; // 固定長配列にして高速化
};

int cnt = 1;
int vst[20][20]; // 毎回初期化しないようグローバル配置
vector<pair<int, int>> path;

// 範囲内判定のインライン化
inline bool is_valid(int x, int y) {
    return (0 <= x && x < 20 && 0 <= y && y < 20);
}

// 元のシミュレーションロジックを完全維持しつつ高速化
int cal_score(const state &s) {
    int score = 0;
    int sx = s.sx;
    int sy = s.sy;
    path.clear();
    
    for (int i = 0; i < t; i++) {
        path.push_back({sx, sy});
        score += a[sx][sy];
        vst[sx][sy] = cnt;

        int nexdir = s.dir[sx][sy];
        bool mov = false;
        int nx, ny;
        
        for (int d = 0; d < 4; d++) {
            int nd = (nexdir + d) & 3; // % 4 の代わりにビット演算
            nx = sx + dx[nd];
            ny = sy + dy[nd];
            if (!is_valid(nx, ny)) continue;
            if (vst[nx][ny] == cnt) continue;
            mov = true;
            break;
        }

        if (!mov) break;
        sx = nx;
        sy = ny;
    }

    cnt++; // 次の呼び出しのためにカウントを変化（これで前回の訪問ログが実質クリアされる）
    return score;
}

int main() {
    // 入出力の高速化
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    if (!(cin >> n >> t)) return 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    state s;
    s.sx = 0; s.sy = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            s.dir[i][j] = mt() % 4;
        }
    }

    int best_score = cal_score(s);
    auto sa_start_time = chrono::system_clock::now();
    double sa_time_limit = 1950.0; // ミリ秒
    int loop = 0;
    
    // 焼きなましの温度パラメタの適正化
    double start_temp = 35.0, end_temp = 0.1;
    double temp = start_temp;
    int best_score_2 = best_score;
    state best_s = s;

    while (1) {
        // 時間チェックの間引き (8191とのAND演算で8192回に1回だけ実行)
        if ((loop & 8191) == 0) {
            double time = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - sa_start_time).count();
            if (time > sa_time_limit) break;
            temp = start_temp + (end_temp - start_temp) * time / sa_time_limit;
        }
        loop++;

        int mode = mt() % 100;
        int olddir = -1;
        int x, y, sx, sy;

        if (99 <= mode) { // 近傍1: 経路上のマスの方向を変える
            if (path.empty()) continue;
            int idx = mt() % path.size();
            x = path[idx].first;
            y = path[idx].second;
            olddir = s.dir[x][y];

            while (true) {
                s.dir[x][y] = mt() % 4;
                if (s.dir[x][y] != olddir) {
                    int nx = x + dx[s.dir[x][y]];
                    int ny = y + dy[s.dir[x][y]];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    
                    // 元の確率評価ロジックを維持
                    double prob = a[nx][ny] / 300.0;
                    if (prob * 4294967295.0 > (double)mt()) break;
                }
            }
            // スコア計算
            int nsc = cal_score(s);
            double diff = nsc - best_score;
            double prob = exp(diff / temp); // 正しい焼きなまし公式へ修正

            if (diff > 0 || prob * 4294967295.0 > (double)mt()) {
                best_score = nsc;
                if (nsc > best_score_2) {
                    best_score_2 = nsc;
                    best_s = s;
                }
            } else {
                s.dir[x][y] = olddir;
                // ロジック維持のため、現在の状態にパス情報を戻しておく
                cal_score(s);
            }
        } 
        else { // 近傍2: 始点を変える
            sx = s.sx;
            sy = s.sy;

            while (true) {
                x = mt() % n;
                y = mt() % n;
                if (s.sx == x && s.sy == y) continue;

                double prob = a[x][y] / 300.0;
                if (prob * 4294967295.0 > (double)mt()) break;
            }

            s.sx = x;
            s.sy = y;

            int nsc = cal_score(s);
            double diff = nsc - best_score;
            double prob = exp(diff / temp);

            if (diff > 0 || prob * 4294967295.0 > (double)mt()) {
                best_score = nsc;
                if (nsc > best_score_2) {
                    best_score_2 = nsc;
                    best_s = s;
                }
            } else {
                s.sx = sx;
                s.sy = sy;
                cal_score(s);
            }
        }
    }

    // 最善解を復元して出力
    cal_score(best_s);
    cout << path.size() << "\n";
    for (const auto &[px, py] : path) {
        cout << px << " " << py << "\n";
    }

    return 0;
}