#1162507 (C++23(gnu拡張)) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: Rho
• 提出日時: 2026-05-02 17:13:11
• 言語: C++23(gnu拡張) (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,903 ms / 2,000 ms
• コード長: 8,616 bytes
• コンパイル時間: 3,290 ms
• コンパイル使用メモリ: 376,220 KB
• 実行使用メモリ: 6,400 KB
• スコア: 1,132,180
• 最終ジャッジ日時: 2026-05-02 17:14:54
• 合計ジャッジ時間: 102,915 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

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

ソースコード

//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
using namespace std;
#define all(a) a.begin(),a.end()
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
#define compress(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
constexpr ll inf=3e18;

ll N,T;
ll A [20][20];

void input(){
    cin>>N>>T;
    rep(i,N)rep(j,N)cin>>A[i][j];
}

// =========================================================
// 焼きなまし法による単純パス最大化
// =========================================================

mt19937 rng(20260502);
const int dx4[4] = {-1, 1, 0, 0};
const int dy4[4] = {0, 0, -1, 1};

inline bool in_bounds(int x, int y) {
    return 0 <= x && x < N && 0 <= y && y < N;
}
inline bool adj(const P& a, const P& b) {
    return abs((int)(a.first - b.first)) + abs((int)(a.second - b.second)) == 1;
}

vector<P> path;
bool used[20][20];
ll score_cur = 0;

vector<P> best_path;
ll best_score = LLONG_MIN;

inline void push_cell(int x, int y) {
    path.emplace_back(x, y);
    used[x][y] = true;
    score_cur += A[x][y];
}
inline void pop_cell() {
    auto [x, y] = path.back();
    used[x][y] = false;
    score_cur -= A[x][y];
    path.pop_back();
}
void clear_path() {
    for (auto [x, y] : path) used[x][y] = false;
    path.clear();
    score_cur = 0;
}

// 末尾からランダムウォークで延伸（長さ max_len まで or 行き詰まりまで）
void extend_random(int max_len) {
    while ((int)path.size() < max_len) {
        auto [x, y] = path.back();
        int nxs[4], nys[4], cnt = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx4[k], ny = y + dy4[k];
            if (in_bounds(nx, ny) && !used[nx][ny]) {
                nxs[cnt] = nx; nys[cnt] = ny; cnt++;
            }
        }
        if (cnt == 0) break;
        int c = rng() % cnt;
        push_cell(nxs[c], nys[c]);
    }
}

void initial_solution() {
    vector<P> best_init;
    ll best_init_score = LLONG_MIN;
    int best_init_len = 0;

    rep(trial, 50) {
        clear_path();
        int sx = rng() % N, sy = rng() % N;
        push_cell(sx, sy);
        extend_random(T);
        int len = path.size();
        if (len > best_init_len ||
            (len == best_init_len && score_cur > best_init_score)) {
            best_init = path;
            best_init_score = score_cur;
            best_init_len = len;
        }
    }
    clear_path();
    for (auto [x, y] : best_init) push_cell(x, y);
    best_path = path;
    best_score = score_cur;
}

// === 近傍 1: 末尾 k 削除 → 再延伸 ===
struct TailMove {
    bool reversed;
    int prefix_len;
    vector<P> popped;
};
bool tr_apply(TailMove& m) {
    int len = path.size();
    if (len < 2) return false;
    m.reversed = (rng() & 1);
    if (m.reversed) reverse(path.begin(), path.end());
    int kmax = min(len - 1, 6);
    int k = 1 + (int)(rng() % kmax);
    m.prefix_len = len - k;
    m.popped.clear();
    m.popped.reserve(k);
    for (int i = 0; i < k; i++) {
        m.popped.push_back(path.back());
        pop_cell();
    }
    extend_random(T);
    return true;
}
void tr_rollback(TailMove& m) {
    while ((int)path.size() > m.prefix_len) pop_cell();
    for (int i = (int)m.popped.size() - 1; i >= 0; i--) {
        push_cell(m.popped[i].first, m.popped[i].second);
    }
    if (m.reversed) reverse(path.begin(), path.end());
}

// === 近傍 2: 挿入（path[i] と path[i+1] の共通隣接セルを差し込む）===
struct InsertMove {
    int pos;
    P cell;
};
bool ins_apply(InsertMove& m) {
    int len = path.size();
    if (len < 2 || len >= T) return false;
    for (int trial = 0; trial < 10; trial++) {
        int i = rng() % (len - 1);
        auto [x1, y1] = path[i];
        auto [x2, y2] = path[i + 1];
        P cands[4]; int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int cx = x1 + dx4[k], cy = y1 + dy4[k];
            if (!in_bounds(cx, cy)) continue;
            if (used[cx][cy]) continue;
            if (abs(cx - x2) + abs(cy - y2) != 1) continue;
            cands[cnt++] = P(cx, cy);
        }
        if (cnt == 0) continue;
        P c = cands[rng() % cnt];
        m.pos = i + 1;
        m.cell = c;
        path.insert(path.begin() + m.pos, c);
        used[c.first][c.second] = true;
        score_cur += A[c.first][c.second];
        return true;
    }
    return false;
}
void ins_rollback(InsertMove& m) {
    used[m.cell.first][m.cell.second] = false;
    score_cur -= A[m.cell.first][m.cell.second];
    path.erase(path.begin() + m.pos);
}

// === 近傍 3: 削除（path[i-1] と path[i+1] が隣接していれば path[i] を削除）===
struct DeleteMove {
    int pos;
    P cell;
};
bool del_apply(DeleteMove& m) {
    int len = path.size();
    if (len < 3) return false;
    for (int trial = 0; trial < 10; trial++) {
        int i = 1 + (int)(rng() % (len - 2));
        if (!adj(path[i - 1], path[i + 1])) continue;
        m.pos = i;
        m.cell = path[i];
        used[m.cell.first][m.cell.second] = false;
        score_cur -= A[m.cell.first][m.cell.second];
        path.erase(path.begin() + i);
        return true;
    }
    return false;
}
void del_rollback(DeleteMove& m) {
    path.insert(path.begin() + m.pos, m.cell);
    used[m.cell.first][m.cell.second] = true;
    score_cur += A[m.cell.first][m.cell.second];
}

const double TIME_LIMIT_MS = 1900.0;

inline double elapsed_ms(chrono::steady_clock::time_point st) {
    return chrono::duration<double, milli>(chrono::steady_clock::now() - st).count();
}

int main(){
    input();
    auto t_input = chrono::steady_clock::now();
    auto start = t_input;

    // 温度スケールは A の値域から決める
    ll amax = LLONG_MIN, amin = LLONG_MAX;
    rep(i, N) rep(j, N) { amax = max(amax, A[i][j]); amin = min(amin, A[i][j]); }
    double T_start = max(1.0, (double)(amax - amin));
    double T_end = max(0.1, T_start * 0.001);

    initial_solution();
    double t_init_ms = elapsed_ms(start);
    ll initial_score = best_score;

    ll iter = 0, accepted = 0, improved = 0;
    double now_ms = 0;
    while (true) {
        if ((iter & 1023) == 0) {
            now_ms = elapsed_ms(start);
            if (now_ms > TIME_LIMIT_MS) break;
        }
        iter++;

        double progress = now_ms / TIME_LIMIT_MS;
        double temp = T_start * pow(T_end / T_start, progress);

        ll old_score = score_cur;
        int op = rng() % 100;
        bool applied = false;
        TailMove tm; InsertMove im; DeleteMove dm;
        int kind = -1;

        if (op < 60) { applied = tr_apply(tm); kind = 0; }
        else if (op < 80) { applied = ins_apply(im); kind = 1; }
        else              { applied = del_apply(dm); kind = 2; }

        if (!applied) continue;

        ll delta = score_cur - old_score;
        bool accept;
        if (delta >= 0) accept = true;
        else {
            double prob = exp((double)delta / temp);
            double r = (double)(rng() & 0xFFFFFF) / (double)0x1000000;
            accept = r < prob;
        }

        if (accept) {
            accepted++;
            if (score_cur > best_score) {
                improved++;
                best_score = score_cur;
                best_path = path;
            }
        } else {
            if (kind == 0) tr_rollback(tm);
            else if (kind == 1) ins_rollback(im);
            else del_rollback(dm);
        }
    }

    double t_total_ms = elapsed_ms(start);
    double t_sa_ms = t_total_ms - t_init_ms;
    cerr << fixed << setprecision(2);
    cerr << "[time] init=" << t_init_ms << "ms"
         << " sa=" << t_sa_ms << "ms"
         << " total=" << t_total_ms << "ms"
         << " (limit=" << TIME_LIMIT_MS << "ms)" << endl;
    cerr << "[stat] iter=" << iter
         << " iter/s=" << (iter * 1000.0 / max(1.0, t_sa_ms))
         << " accepted=" << accepted
         << " (" << (accepted * 100.0 / max((ll)1, iter)) << "%)"
         << " improved=" << improved << endl;
    cerr << "[score] init=" << initial_score
         << " best=" << best_score
         << " gain=" << (best_score - initial_score)
         << " len=" << best_path.size() << "/" << T << endl;

    // 出力（フォーマットは問題に合わせて要調整）
    cout << best_path.size() << "\n";
    for (auto [x, y] : best_path) cout << x << " " << y << "\n";

    return 0;
}