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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: mono
• 提出日時: 2026-05-02 17:53:31
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,952 ms / 2,000 ms
• コード長: 6,836 bytes
• コンパイル時間: 3,152 ms
• コンパイル使用メモリ: 237,492 KB
• 実行使用メモリ: 6,400 KB
• スコア: 1,996,614
• 最終ジャッジ日時: 2026-05-02 17:55:27
• 合計ジャッジ時間: 105,540 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

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

ソースコード

#pragma GCC optimize ("O3,inline,omit-frame-pointer,no-asynchronous-unwind-tables,fast-math")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = (a); i < (n); i++)
using ll = long long;

template<class T, class U> void chmax(T& a, U b) { if (a < b) a = b; }
template<class T, class U> void chmin(T& a, U b) { if (b < a) a = b; }

struct Timer {
    chrono::steady_clock::time_point st = chrono::steady_clock::now();
    double elapsed() const {
        return chrono::duration<double>(chrono::steady_clock::now() - st).count();
    }
};

int n, t;
vector<vector<int>> a;
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
const int DX[4] = {1, -1, 0, 0};
const int DY[4] = {0, 0, 1, -1};

int id(int x, int y) { return x * n + y; }

ll score_path(const vector<int>& path) {
    ll s = 0;
    for (int v : path) s += a[v / n][v % n];
    return s;
}

bool valid_path(const vector<int>& path) {
    if ((int)path.size() != t) return false;
    vector<int> used(n * n, 0);
    for (int v : path) {
        if (v < 0 || n * n <= v || used[v]) return false;
        used[v] = 1;
    }
    rep(i, 1, (int)path.size()) {
        int x0 = path[i - 1] / n, y0 = path[i - 1] % n;
        int x1 = path[i] / n, y1 = path[i] % n;
        if (abs(x0 - x1) + abs(y0 - y1) != 1) return false;
    }
    return true;
}

vector<int> snake_path(bool vertical, bool rev_x, bool rev_y) {
    vector<int> p;
    p.reserve(n * n);
    if (!vertical) {
        rep(ii, 0, n) {
            int x = rev_x ? n - 1 - ii : ii;
            if (ii % 2 == 0) {
                rep(jj, 0, n) {
                    int y = rev_y ? n - 1 - jj : jj;
                    p.push_back(id(x, y));
                }
            } else {
                for (int jj = n - 1; jj >= 0; jj--) {
                    int y = rev_y ? n - 1 - jj : jj;
                    p.push_back(id(x, y));
                }
            }
        }
    } else {
        rep(jj, 0, n) {
            int y = rev_y ? n - 1 - jj : jj;
            if (jj % 2 == 0) {
                rep(ii, 0, n) {
                    int x = rev_x ? n - 1 - ii : ii;
                    p.push_back(id(x, y));
                }
            } else {
                for (int ii = n - 1; ii >= 0; ii--) {
                    int x = rev_x ? n - 1 - ii : ii;
                    p.push_back(id(x, y));
                }
            }
        }
    }
    return p;
}

void consider_contiguous(const vector<int>& ham, ll& best_score, vector<int>& best_path) {
    if ((int)ham.size() < t) return;
    ll cur = 0;
    rep(i, 0, t) cur += a[ham[i] / n][ham[i] % n];
    if (cur > best_score) {
        best_score = cur;
        best_path.assign(ham.begin(), ham.begin() + t);
    }
    rep(r, t, (int)ham.size()) {
        cur += a[ham[r] / n][ham[r] % n];
        cur -= a[ham[r - t] / n][ham[r - t] % n];
        if (cur > best_score) {
            best_score = cur;
            best_path.assign(ham.begin() + (r - t + 1), ham.begin() + (r + 1));
        }
    }
}

int onward_degree(int v, const vector<unsigned char>& used) {
    int x = v / n, y = v % n, deg = 0;
    rep(k, 0, 4) {
        int nx = x + DX[k], ny = y + DY[k];
        if (0 <= nx && nx < n && 0 <= ny && ny < n && !used[id(nx, ny)]) deg++;
    }
    return deg;
}

bool weighted_dfs_from(int start, vector<int>& path, const Timer& timer, double limit) {
    vector<unsigned char> used(n * n, 0);
    vector<array<int, 4>> order(n * n);
    vector<unsigned char> ptr(n * n, 0);
    path.clear();
    path.reserve(t);
    path.push_back(start);
    used[start] = 1;

    while ((int)path.size() < t && timer.elapsed() < limit) {
        int v = path.back();
        int x = v / n, y = v % n;
        if (ptr[v] == 0) {
            vector<pair<double, int>> cand;
            rep(k, 0, 4) {
                int nx = x + DX[k], ny = y + DY[k];
                if (nx < 0 || n <= nx || ny < 0 || n <= ny) continue;
                int nv = id(nx, ny);
                if (used[nv]) continue;
                int deg = onward_degree(nv, used);
                if ((int)path.size() + 1 < t && deg == 0) continue;
                double w = max(1, a[nx][ny]);
                w *= w;
                w *= 1.0 / (deg + 1);
                w *= uniform_real_distribution<double>(0.70, 1.30)(rng);
                cand.push_back({-w, nv});
            }
            sort(cand.begin(), cand.end());
            rep(i, 0, 4) order[v][i] = -1;
            rep(i, 0, (int)cand.size()) order[v][i] = cand[i].second;
        }

        bool advanced = false;
        while (ptr[v] < 4 && order[v][ptr[v]] != -1) {
            int nv = order[v][ptr[v]++];
            if (used[nv]) continue;
            used[nv] = 1;
            path.push_back(nv);
            advanced = true;
            break;
        }
        if (advanced) continue;

        used[v] = 0;
        path.pop_back();
        if (path.empty()) return false;
    }
    return (int)path.size() == t;
}

vector<int> random_starts_by_score() {
    vector<pair<int, int>> cells;
    cells.reserve(n * n);
    rep(i, 0, n) rep(j, 0, n) cells.push_back({a[i][j], id(i, j)});
    sort(cells.rbegin(), cells.rend());
    int pool = min((int)cells.size(), max(20, n * n / 2));
    vector<int> starts;
    starts.reserve(pool);
    rep(i, 0, pool) starts.push_back(cells[i].second);
    shuffle(starts.begin(), starts.end(), rng);
    return starts;
}

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

    cin >> n >> t;
    a.assign(n, vector<int>(n));
    rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];

    Timer timer;
    const double LIMIT = 1.95;
    ll best_score = LLONG_MIN;
    vector<int> best_path;

    rep(vertical, 0, 2) rep(rx, 0, 2) rep(ry, 0, 2) {
        vector<int> ham = snake_path(vertical, rx, ry);
        consider_contiguous(ham, best_score, best_path);
        reverse(ham.begin(), ham.end());
        consider_contiguous(ham, best_score, best_path);
    }

    vector<int> path;
    int iter = 0;
    while (timer.elapsed() < LIMIT) {
        auto starts = random_starts_by_score();
        for (int st : starts) {
            if (timer.elapsed() >= LIMIT) break;
            if (!weighted_dfs_from(st, path, timer, LIMIT)) continue;
            ll sc = score_path(path);
            if (sc > best_score) {
                best_score = sc;
                best_path = path;
            }
            iter++;
        }
    }

    if (!valid_path(best_path)) {
        best_path.clear();
        vector<int> ham = snake_path(false, false, false);
        best_path.assign(ham.begin(), ham.begin() + t);
    }

    cout << t << '\n';
    for (int v : best_path) cout << v / n << ' ' << v % n << '\n';

    cerr << "score=" << best_score << " iter=" << iter << " time=" << timer.elapsed() << '\n';
    return 0;
}