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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: Moegi
• 提出日時: 2026-05-02 17:54:26
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,803 ms / 2,000 ms
• コード長: 12,379 bytes
• コンパイル時間: 4,362 ms
• コンパイル使用メモリ: 358,372 KB
• 実行使用メモリ: 6,400 KB
• スコア: 2,176,525
• 最終ジャッジ日時: 2026-05-02 17:57:10
• 合計ジャッジ時間: 98,625 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Timer {
    chrono::steady_clock::time_point start = chrono::steady_clock::now();

    double elapsed() const {
        return chrono::duration<double>(chrono::steady_clock::now() - start).count();
    }
};

struct XorShift {
    uint64_t x = 88172645463325252ull;

    uint32_t next_u32() {
        x ^= x << 7;
        x ^= x >> 9;
        return static_cast<uint32_t>(x);
    }

    int uniform_int(int l, int r) {
        return l + static_cast<int>(next_u32() % static_cast<uint32_t>(r - l + 1));
    }

    double uniform01() {
        return (next_u32() + 0.5) * (1.0 / 4294967296.0);
    }
};

int N, T;
array<int, 400> A;
array<vector<int>, 400> adj_cells;
XorShift rng;

int cell_id(int i, int j) {
    return i * N + j;
}

int cell_i(int id) {
    return id / N;
}

int cell_j(int id) {
    return id % N;
}

bool adjacent_cell(int a, int b) {
    return abs(cell_i(a) - cell_i(b)) + abs(cell_j(a) - cell_j(b)) == 1;
}

long long calc_score(const vector<int>& path) {
    long long score = 0;
    for (int v : path) score += A[v];
    return score;
}

double penalty_coef(double progress) {
    double remain = max(1e-4, 1.0 - progress);
    return 1000.0 * (1.0 + 0.05 * progress / (remain * remain));
}

double objective(long long score, int len, double progress) {
    int over = max(0, len - T);
    if (over == 0) return score;
    if (progress > 0.985) return -1e100 - 1e9 * over;
    return score - penalty_coef(progress) * over;
}

bool valid_path(const vector<int>& path) {
    if (path.empty() || (int)path.size() > T) return false;
    array<char, 400> used{};
    for (int idx = 0; idx < (int)path.size(); ++idx) {
        int v = path[idx];
        if (v < 0 || v >= N * N || used[v]) return false;
        used[v] = true;
        if (idx > 0 && !adjacent_cell(path[idx - 1], v)) return false;
    }
    return true;
}

int bfs_distance(int start, int goal, const array<char, 400>& blocked) {
    if (start == goal) return 0;

    array<int, 400> dist;
    dist.fill(-1);
    queue<int> que;
    dist[start] = 0;
    que.push(start);

    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (int to : adj_cells[v]) {
            if (to != goal && blocked[to]) continue;
            if (dist[to] != -1) continue;
            dist[to] = dist[v] + 1;
            if (to == goal) return dist[to];
            que.push(to);
        }
    }
    return -1;
}

bool make_bridge(const vector<int>& path, int l, int r, int max_intermediate, vector<int>& bridge) {
    bridge.clear();

    const int start = path[l];
    const int goal = path[r];
    array<char, 400> used{};
    for (int i = 0; i < (int)path.size(); ++i) {
        if (l < i && i < r) continue;
        used[path[i]] = true;
    }

    int cur = start;
    used[start] = true;

    for (int step = 0; step <= max_intermediate; ++step) {
        if (adjacent_cell(cur, goal)) return true;
        if ((int)bridge.size() == max_intermediate) return false;

        struct Candidate {
            int v;
            int dist;
            double weight;
        };
        vector<Candidate> cand;
        for (int to : adj_cells[cur]) {
            if (to == goal) return true;
            if (used[to]) continue;

            array<char, 400> next_used = used;
            next_used[to] = true;
            int dist = bfs_distance(to, goal, next_used);
            int rest_intermediate = max_intermediate - (int)bridge.size() - 1;
            if (dist < 0 || dist > rest_intermediate + 1) continue;

            double value_weight = 1.0 + A[to];
            double dist_weight = 1.0 / (1.0 + dist);
            double noise = 0.35 + rng.uniform01();
            cand.push_back({to, dist, value_weight * dist_weight * noise});
        }

        if (cand.empty()) return false;

        double total = 0.0;
        for (const auto& c : cand) total += c.weight;
        double pick = rng.uniform01() * total;
        int chosen = cand.back().v;
        for (const auto& c : cand) {
            pick -= c.weight;
            if (pick <= 0.0) {
                chosen = c.v;
                break;
            }
        }

        bridge.push_back(chosen);
        used[chosen] = true;
        cur = chosen;
    }

    return adjacent_cell(cur, goal);
}

vector<int> make_zigzag_path() {
    vector<int> base;
    base.reserve(N * N);
    for (int i = 0; i < N; ++i) {
        if (i % 2 == 0) {
            for (int j = 0; j < N; ++j) base.push_back(cell_id(i, j));
        } else {
            for (int j = N - 1; j >= 0; --j) base.push_back(cell_id(i, j));
        }
    }

    vector<vector<int>> candidates;
    candidates.reserve(8);
    for (int type = 0; type < 8; ++type) {
        vector<int> full;
        full.reserve(base.size());
        for (int id : base) {
            int i = cell_i(id), j = cell_j(id);
            int ni = i, nj = j;
            if (type == 0) {
                ni = i, nj = j;
            } else if (type == 1) {
                ni = i, nj = N - 1 - j;
            } else if (type == 2) {
                ni = N - 1 - i, nj = j;
            } else if (type == 3) {
                ni = N - 1 - i, nj = N - 1 - j;
            } else if (type == 4) {
                ni = j, nj = i;
            } else if (type == 5) {
                ni = j, nj = N - 1 - i;
            } else if (type == 6) {
                ni = N - 1 - j, nj = i;
            } else {
                ni = N - 1 - j, nj = N - 1 - i;
            }
            full.push_back(cell_id(ni, nj));
        }
        candidates.push_back(full);
    }

    vector<int> best(candidates[0].begin(), candidates[0].begin() + min(T, (int)candidates[0].size()));
    long long best_score = calc_score(best);

    for (const auto& full : candidates) {
        long long cur = 0;
        for (int i = 0; i < (int)full.size(); ++i) {
            cur += A[full[i]];
            if (i >= T) cur -= A[full[i - T]];
            if (i + 1 >= T && cur > best_score) {
                best_score = cur;
                best.assign(full.begin() + i + 1 - T, full.begin() + i + 1);
            }
        }
    }
    return best;
}

int random_start_cell() {
    long long total = 0;
    for (int v = 0; v < N * N; ++v) total += A[v] + 1;
    long long pick = rng.uniform_int(0, (int)min<long long>(total - 1, INT_MAX));
    if (total > INT_MAX) pick = (long long)(rng.uniform01() * total);

    for (int v = 0; v < N * N; ++v) {
        pick -= A[v] + 1;
        if (pick < 0) return v;
    }
    return rng.uniform_int(0, N * N - 1);
}

void random_extend(vector<int>& path, int target_len) {
    array<char, 400> used{};
    for (int v : path) used[v] = true;

    while ((int)path.size() < target_len) {
        int cur = path.back();
        vector<pair<int, double>> cand;
        for (int to : adj_cells[cur]) {
            if (used[to]) continue;
            double noise = 0.25 + rng.uniform01();
            cand.push_back({to, (1.0 + A[to]) * noise});
        }
        if (cand.empty()) break;

        double total = 0.0;
        for (auto [_, w] : cand) total += w;
        double pick = rng.uniform01() * total;
        int chosen = cand.back().first;
        for (auto [v, w] : cand) {
            pick -= w;
            if (pick <= 0.0) {
                chosen = v;
                break;
            }
        }

        path.push_back(chosen);
        used[chosen] = true;
    }
}

bool propose_bridge_move(const vector<int>& path, vector<int>& next_path, double progress) {
    int len = (int)path.size();
    if (len < 2) return false;

    int l = rng.uniform_int(0, len - 2);
    int max_width = min(len - l - 1, 90);
    int width = rng.uniform_int(1, max_width);
    int r = l + width;

    int removed_intermediate = r - l - 1;
    int over_allowance = (int)((1.0 - progress) * 45.0) + 4;
    int max_intermediate = removed_intermediate + over_allowance;
    int kept_len = len - removed_intermediate;
    max_intermediate = min(max_intermediate, N * N - kept_len);
    if (max_intermediate < 0) return false;

    vector<int> bridge;
    if (!make_bridge(path, l, r, max_intermediate, bridge)) return false;
    if ((int)bridge.size() == removed_intermediate) return false;

    next_path.clear();
    next_path.reserve(len - removed_intermediate + bridge.size());
    next_path.insert(next_path.end(), path.begin(), path.begin() + l + 1);
    next_path.insert(next_path.end(), bridge.begin(), bridge.end());
    next_path.insert(next_path.end(), path.begin() + r, path.end());
    return true;
}

bool propose_regrow_move(const vector<int>& path, vector<int>& next_path, double progress) {
    int len = (int)path.size();
    if (len == 0) return false;

    next_path = path;
    if (rng.uniform01() < 0.5) reverse(next_path.begin(), next_path.end());

    int cut;
    if (rng.uniform01() < 0.08) {
        next_path.assign(1, random_start_cell());
        cut = 0;
    } else {
        cut = rng.uniform_int(0, len - 1);
        next_path.resize(cut + 1);
    }

    int over_allowance = (int)((1.0 - progress) * 35.0);
    int target = min(N * N, T + rng.uniform_int(0, max(0, over_allowance)));
    target = max(target, cut + 1);
    random_extend(next_path, target);
    return next_path != path;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int v = cell_id(i, j);
            if (i > 0) adj_cells[v].push_back(cell_id(i - 1, j));
            if (i + 1 < N) adj_cells[v].push_back(cell_id(i + 1, j));
            if (j > 0) adj_cells[v].push_back(cell_id(i, j - 1));
            if (j + 1 < N) adj_cells[v].push_back(cell_id(i, j + 1));
        }
    }

    double time_limit = 1.80;
#ifdef LOCAL
    if (const char* env = getenv("TL")) {
        time_limit = atof(env);
    }
#endif

    Timer timer;
    uint64_t seed = 1469598103934665603ull;
    seed ^= (uint64_t)N + 0x9e3779b97f4a7c15ull + (seed << 6) + (seed >> 2);
    seed ^= (uint64_t)T + 0x9e3779b97f4a7c15ull + (seed << 6) + (seed >> 2);
    for (int v = 0; v < N * N; ++v) {
        seed ^= (uint64_t)(A[v] + 1) + 0x9e3779b97f4a7c15ull + (seed << 6) + (seed >> 2);
    }
    rng.x ^= seed;

    vector<int> cur_path = make_zigzag_path();
    long long cur_score = calc_score(cur_path);
    vector<int> best_path = cur_path;
    long long best_score = cur_score;

    double init_limit = min(0.04, time_limit * 0.08);
    for (int rep = 0; rep < 300 && timer.elapsed() < init_limit; ++rep) {
        vector<int> path(1, random_start_cell());
        random_extend(path, T);
        long long score = calc_score(path);
        if (score > best_score && valid_path(path)) {
            best_path = path;
            best_score = score;
        }
    }
    cur_path = best_path;
    cur_score = best_score;

    vector<int> next_path;
    int iter = 0;
    while (true) {
        double elapsed = timer.elapsed();
        if (elapsed >= time_limit) break;
        double progress = min(1.0, elapsed / time_limit);

        bool ok;
        if (rng.uniform01() < 0.62) {
            ok = propose_bridge_move(cur_path, next_path, progress);
        } else {
            ok = propose_regrow_move(cur_path, next_path, progress);
        }
        if (!ok || next_path.empty()) continue;

        long long next_score = calc_score(next_path);
        double cur_obj = objective(cur_score, (int)cur_path.size(), progress);
        double next_obj = objective(next_score, (int)next_path.size(), progress);
        double temp = 4000.0 * pow(0.004, progress) + 5.0;
        double diff = next_obj - cur_obj;

        if (diff >= 0.0 || exp(diff / temp) > rng.uniform01()) {
            cur_path.swap(next_path);
            cur_score = next_score;

            if ((int)cur_path.size() <= T && cur_score > best_score && valid_path(cur_path)) {
                best_path = cur_path;
                best_score = cur_score;
            }
        }

        ++iter;
    }

    if (!valid_path(best_path)) {
        best_path = make_zigzag_path();
    }

    cout << best_path.size() << '\n';
    for (int v : best_path) {
        cout << cell_i(v) << ' ' << cell_j(v) << '\n';
    }

    return 0;
}