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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: hakatashi
• 提出日時: 2026-04-24 14:28:39
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 79 ms / 2,000 ms
• コード長: 5,490 bytes
• コンパイル時間: 1,866 ms
• コンパイル使用メモリ: 199,132 KB
• 実行使用メモリ: 7,424 KB
• スコア: 2,009,717
• 最終ジャッジ日時: 2026-05-02 16:32:00
• 合計ジャッジ時間: 7,596 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_1

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

ソースコード

// Implementation by Claude Code - v3_combined.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <climits>
using namespace std;

static const int dx[] = {-1, 1, 0, 0};
static const int dy[] = {0, 0, -1, 1};
static const int M_PER_POS = 5; // diversity beam: paths per end-position

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

// ---- Greedy helper ----
int deg(int r, int c, const vector<vector<bool>>& vis) {
    int cnt = 0;
    for (int d = 0; d < 4; d++) {
        int nr = r + dx[d], nc = c + dy[d];
        if (nr >= 0 && nr < N && nc >= 0 && nc < N && !vis[nr][nc]) cnt++;
    }
    return cnt;
}

pair<int, vector<pair<int,int>>> greedy_run(int sr, int sc, int vw, int dw) {
    vector<vector<bool>> vis(N, vector<bool>(N, false));
    vector<pair<int,int>> path;
    vis[sr][sc] = true;
    path.push_back({sr, sc});
    int score = A[sr][sc];
    int r = sr, c = sc;
    while ((int)path.size() < T) {
        int best = INT_MIN, nr2 = -1, nc2 = -1;
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr >= 0 && nr < N && nc >= 0 && nc < N && !vis[nr][nc]) {
                int fn = A[nr][nc] * vw - deg(nr, nc, vis) * dw;
                if (fn > best) { best = fn; nr2 = nr; nc2 = nc; }
            }
        }
        if (nr2 < 0) break;
        vis[nr2][nc2] = true;
        path.push_back({nr2, nc2});
        score += A[nr2][nc2];
        r = nr2; c = nc2;
    }
    return {score, path};
}

pair<int, vector<pair<int,int>>> zigzag_run() {
    vector<pair<int,int>> path;
    for (int i = 0; i < N && (int)path.size() < T; i++) {
        if (i % 2 == 0)
            for (int j = 0; j < N && (int)path.size() < T; j++) path.push_back({i,j});
        else
            for (int j = N-1; j >= 0 && (int)path.size() < T; j--) path.push_back({i,j});
    }
    int s = 0; for (auto& p : path) s += A[p.first][p.second];
    return {s, path};
}

// ---- Diversity beam ----
struct BState {
    int score;
    short r, c, parent;
    bitset<400> visited;
};

struct HistEntry { int score; short r, c, parent; };

pair<int, vector<pair<int,int>>> beam_search() {
    vector<BState> cur;
    cur.reserve(N * N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            BState s; s.score=A[i][j]; s.r=i; s.c=j; s.parent=-1;
            s.visited.reset(); s.visited.set(i*N+j);
            cur.push_back(s);
        }

    vector<vector<HistEntry>> hist(T);
    hist[0].resize(cur.size());
    for (int i = 0; i < (int)cur.size(); i++)
        hist[0][i] = {cur[i].score, cur[i].r, cur[i].c, -1};

    int bscore = -1, bstep = 0, bidx = 0;
    for (int i = 0; i < (int)cur.size(); i++)
        if (cur[i].score > bscore) { bscore=cur[i].score; bstep=0; bidx=i; }

    vector<BState> cands;
    cands.reserve(cur.size() * 4);

    for (int step = 1; step < T; step++) {
        cands.clear();
        for (int pi = 0; pi < (int)cur.size(); pi++) {
            const BState& s = cur[pi];
            for (int d = 0; d < 4; d++) {
                int nr = s.r+dx[d], nc = s.c+dy[d];
                if (nr<0||nr>=N||nc<0||nc>=N||s.visited.test(nr*N+nc)) continue;
                BState ns; ns.score=s.score+A[nr][nc]; ns.r=(short)nr; ns.c=(short)nc;
                ns.parent=(short)pi; ns.visited=s.visited; ns.visited.set(nr*N+nc);
                cands.push_back(ns);
            }
        }
        if (cands.empty()) break;

        // Diversity: sort by position, keep top-M per position
        sort(cands.begin(), cands.end(), [](const BState& a, const BState& b){
            if (a.r!=b.r) return a.r<b.r;
            if (a.c!=b.c) return a.c<b.c;
            return a.score>b.score;
        });
        vector<BState> nxt; nxt.reserve(N*N*M_PER_POS);
        for (int i=0,sz=(int)cands.size(); i<sz;) {
            int r=cands[i].r, c=cands[i].c;
            for (int k=0; k<M_PER_POS && i<sz && cands[i].r==r && cands[i].c==c; k++,i++)
                nxt.push_back(cands[i]);
            while (i<sz && cands[i].r==r && cands[i].c==c) i++;
        }

        hist[step].resize(nxt.size());
        for (int i=0;i<(int)nxt.size();i++)
            hist[step][i]={nxt[i].score,nxt[i].r,nxt[i].c,nxt[i].parent};

        for (int i=0;i<(int)nxt.size();i++)
            if (nxt[i].score>bscore) { bscore=nxt[i].score; bstep=step; bidx=i; }

        cur.swap(nxt);
    }

    // Reconstruct
    vector<pair<int,int>> path;
    for (int cs=bstep,ci=bidx; cs>=0&&ci>=0;) {
        auto& h = hist[cs][ci];
        path.push_back({h.r,h.c});
        ci=h.parent; cs--;
    }
    reverse(path.begin(), path.end());
    return {bscore, 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[i][j];

    int best = -1;
    vector<pair<int,int>> best_path;

    // Greedy hybrid
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            for (auto [vw,dw] : vector<pair<int,int>>{{1,0},{4,1}}) {
                auto [sc,path] = greedy_run(i,j,vw,dw);
                if (sc > best) { best=sc; best_path=path; }
            }
        }
    { auto [sc,path]=zigzag_run(); if(sc>best){best=sc;best_path=path;} }

    // Diversity beam
    { auto [sc,path]=beam_search(); if(sc>best){best=sc;best_path=path;} }

    cout << best_path.size() << "\n";
    for (auto& p : best_path) cout << p.first << " " << p.second << "\n";
    return 0;
}