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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: tRue
• 提出日時: 2026-05-02 17:55:37
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,986 ms / 2,000 ms
• コード長: 4,796 bytes
• コンパイル時間: 2,715 ms
• コンパイル使用メモリ: 218,932 KB
• 実行使用メモリ: 6,400 KB
• スコア: 2,127,056
• 最終ジャッジ日時: 2026-05-02 17:59:55
• 合計ジャッジ時間: 109,650 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <random>
using namespace std;

vector<vector<int>> A;

int score(const vector<pair<int, int>>& path) {
    int sum = 0;
    for (const auto& p : path) {
        sum += A[p.first][p.second];
    }
    return sum;
}

int main() {
    double start_time = clock(); // 開始時間を記録

    random_device seed_gen;
    uint32_t seed = seed_gen();
    default_random_engine engine(seed);
    int N, T;
    cin >> N >> T;

    A.assign(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    vector<pair<int, int>> path;

    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            // 左から右へ
            for (int j = 0; j < N; j++) {
                path.push_back(make_pair(i, j));
                if (path.size() == T) {
                    break;
                }
            }
        } else {
            // 右から左へ
            for (int j = N - 1; j >= 0; j--) {
                path.push_back(make_pair(i, j));
                if (path.size() == T) {
                    break;
                }
            }
        }

        if (path.size() == T) {
            break;
        }
    }


    while((clock() - start_time) / CLOCKS_PER_SEC < 1.9) { // 1.9秒以内で繰り返す
        double elapsed_time = (clock() - start_time) / CLOCKS_PER_SEC;
        double elapsed_ratio = elapsed_time / 1.9; // 経過時間の割合
        reverse(path.begin(), path.end()); // パスを反転させる
        int current_score = score(path);
        vector<pair<int, int>> old_path = path;
        // ここでスコアを改善するためのロジックを実装
        // ランダムな長さパスの端を削って，そこからランダムに歩かせる
        double lambda = (double)0.7*T*(1.00001-elapsed_ratio); // 経過時間に応じてlambdaを減少させる
        poisson_distribution<int> dist((int)lambda);
        int length = min(T-1,max(1,dist(engine))); // ポアソン分布に従うランダムな長さ
        

        
        path.erase(path.end() - length, path.end()); // パスの末尾からlength個削除

        vector<vector<bool>>visited(N, vector<bool>(N, false));
        for (const auto& p : path) {
            visited[p.first][p.second] = true;
        }
        
        while(path.size() < T) {
            pair<int, int> last = path.back();
            vector<pair<int, int>> candidates;
            if (last.first > 0) {
                candidates.push_back(make_pair(last.first - 1, last.second)); // 上
            }
            if (last.first < N - 1) {
                candidates.push_back(make_pair(last.first + 1, last.second)); // 下
            }
            if (last.second > 0) {
                candidates.push_back(make_pair(last.first, last.second - 1)); // 左
            }
            if (last.second < N - 1) {
                candidates.push_back(make_pair(last.first, last.second + 1)); // 右
            }
            
            for (auto it = candidates.begin(); it != candidates.end();) {
                if (visited[it->first][it->second]) {
                    it = candidates.erase(it); // 既に訪れた場所は候補から削除
                } else {
                    ++it;
                }
            }
            
            if (candidates.empty()) {
                break; // 移動できる場所がない場合は終了
            }

            double exponent = 2.5 - 0.1 * elapsed_ratio; // 経過時間に応じて指数を増加させる

            double score_sum = 0.0;
            for (const auto& c : candidates) {
                score_sum += pow(A[c.first][c.second], exponent);
            }
            int rv = rand() % (int)score_sum;
            int idx = 0;
            while(idx < candidates.size()) {
                rv -= pow(A[candidates[idx].first][candidates[idx].second], exponent);
                if (rv < 0) {
                    break;
                }
                idx++;
            }
            path.push_back(candidates[idx]);
            visited[candidates[idx].first][candidates[idx].second] = true; // 選択した場所を訪れたとマーク
        }
        
        if (path.size() < T) {
            path = old_path; // パスがTに満たない場合は元に戻す
            continue;
        }

        int new_score = score(path);
        if (new_score < current_score) {
            path = old_path; // スコアが改善しない場合は元に戻す
        }
    }

    cout << path.size() << endl;
    for (int k = 0; k < path.size(); k++) {
        cout << path[k].first << " " << path[k].second << endl;
    }

    return 0;
}