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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: hakatashi
• 提出日時: 2026-04-24 14:32:58
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,853 ms / 2,000 ms
• コード長: 8,838 bytes
• コンパイル時間: 3,457 ms
• コンパイル使用メモリ: 252,276 KB
• 実行使用メモリ: 7,660 KB
• スコア: 2,171,076
• 最終ジャッジ日時: 2026-05-02 16:33:36
• 合計ジャッジ時間: 102,360 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

コンパイルメッセージ

In function 'int cell(int, int)',
    inlined from 'int extend_greedy(Path&, Vis&, int, int, int, std::mt19937&, double)' at main.cpp:49:21:
main.cpp:21:40: warning: 'nextr' may be used uninitialized [-Wmaybe-uninitialized]
   21 | inline int cell(int r, int c){ return r*20+c; }
      |                                       ~^~~
main.cpp: In function 'int extend_greedy(Path&, Vis&, int, int, int, std::mt19937&, double)':
main.cpp:37:13: note: 'nextr' was declared here
   37 |         int nextr,nextc;
      |             ^~~~~
In function 'int cell(int, int)',
    inlined from 'int extend_greedy(Path&, Vis&, int, int, int, std::mt19937&, double)' at main.cpp:49:21:
main.cpp:21:44: warning: 'nextc' may be used uninitialized [-Wmaybe-uninitialized]
   21 | inline int cell(int r, int c){ return r*20+c; }
      |                                            ^
main.cpp: In function 'int extend_greedy(Path&, Vis&, int, int, int, std::mt19937&, double)':
main.cpp:37:19: note: 'nextc' was declared here
   37 |         int nextr,nextc;
      |                   ^~~~~

ソースコード

// Implementation by Claude Code - v4b_sa_improved.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <climits>
#include <chrono>
#include <random>
#include <cmath>
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;
static const double TIME_LIMIT = 1.85;

int N, T;
int A[20][20];
using Path = vector<pair<int,int>>;
using Vis  = bitset<400>;
inline int cell(int r, int c){ return r*20+c; }

// ---- Greedy building blocks ----
int deg(int r, int c, const Vis& 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.test(cell(nr,nc)))cnt++;}
    return cnt;
}

// Extend path in-place from (r,c); returns score added
int extend_greedy(Path& path, Vis& vis, int r, int c, int target_len, mt19937& rng, double rand_prob){
    int added=0;
    while((int)path.size()<target_len){
        vector<pair<int,int>> nbrs;
        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.test(cell(nr,nc)))nbrs.push_back({nr,nc});}
        if(nbrs.empty()) break;
        int nextr,nextc;
        if(!nbrs.empty() && uniform_real_distribution<>()(rng)<rand_prob){
            // weighted random
            int total=0; for(auto&[nr,nc]:nbrs) total+=A[nr][nc];
            if(total>0){
                int pick=uniform_int_distribution<int>(0,total-1)(rng),acc=0;
                for(auto&[nr,nc]:nbrs){acc+=A[nr][nc];if(pick<acc){nextr=nr;nextc=nc;break;}}
            } else {nextr=nbrs[0].first;nextc=nbrs[0].second;}
        } else {
            int best=INT_MIN; nextr=-1; nextc=-1;
            for(auto&[nr,nc]:nbrs){int fn=A[nr][nc]*4-deg(nr,nc,vis);if(fn>best){best=fn;nextr=nr;nextc=nc;}}
        }
        vis.set(cell(nextr,nextc));
        path.push_back({nextr,nextc});
        added+=A[nextr][nextc];
        r=nextr; c=nextc;
    }
    return added;
}

pair<int,Path> greedy_full(int sr, int sc, int vw, int dw){
    Vis vis; vis.reset(); vis.set(cell(sr,sc));
    Path path={{sr,sc}}; int score=A[sr][sc],r=sr,c=sc;
    while((int)path.size()<T){
        int best=INT_MIN,nextr=-1,nextc=-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.test(cell(nr,nc))){int fn=A[nr][nc]*vw-deg(nr,nc,vis)*dw;if(fn>best){best=fn;nextr=nr;nextc=nc;}}}
        if(nextr<0) break;
        vis.set(cell(nextr,nextc)); path.push_back({nextr,nextc}); score+=A[nextr][nextc]; r=nextr; c=nextc;
    }
    return {score,path};
}

pair<int,Path> zigzag_run(){
    Path 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;Vis visited;};
struct HistEntry{int score;short r,c,parent;};

pair<int,Path> 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(cell(i,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(cell(nr,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(cell(nr,nc));cands.push_back(ns);}}
        if(cands.empty()) break;
        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);
    }
    Path 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};
}

// Compute score and vis from path
pair<int,Vis> compute_score_vis(const Path& path){
    Vis vis; vis.reset(); int s=0;
    for(auto&p:path){vis.set(cell(p.first,p.second));s+=A[p.first][p.second];}
    return {s,vis};
}

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];

    auto t0=chrono::steady_clock::now();
    auto elapsed=[&](){ return chrono::duration<double>(chrono::steady_clock::now()-t0).count(); };

    // Initial solution
    int best_score=-1; Path best_path;
    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_full(i,j,vw,dw);if(sc>best_score){best_score=sc;best_path=path;}}
    }
    {auto[sc,path]=zigzag_run();if(sc>best_score){best_score=sc;best_path=path;}}
    {auto[sc,path]=beam_search();if(sc>best_score){best_score=sc;best_path=path;}}

    // SA
    mt19937 rng(42);
    Path cur_path=best_path;
    int cur_score=best_score;

    // Precompute prefix scores for fast cut evaluation
    auto get_prefix_score=[&](const Path& path, int cut)->pair<int,Vis>{
        Vis vis; vis.reset(); int s=0;
        for(int k=0;k<cut;k++){vis.set(cell(path[k].first,path[k].second));s+=A[path[k].first][path[k].second];}
        return {s,vis};
    };

    long long iters=0;
    while(elapsed()<TIME_LIMIT){
        int L=(int)cur_path.size();
        if(L==0) break;

        double progress=elapsed()/TIME_LIMIT;
        double temp=1.0*pow(1000.0,1.0-progress); // 1000 → 1

        // Decide operation: 0=tail-cut, 1=head-cut, 2=large-restart
        int op;
        double r01=uniform_real_distribution<>()(rng);
        if(r01<0.45) op=0;
        else if(r01<0.90) op=1;
        else op=2;

        double rand_prob=(progress<0.5)?0.2:0.4;

        if(op==2){
            // Large restart: keep only a small random prefix (5-20% of path)
            int cut=max(1,uniform_int_distribution<int>(1,max(1,L/5))(rng));
            auto[ps,vis]=get_prefix_score(cur_path,cut);
            Path new_path(cur_path.begin(),cur_path.begin()+cut);
            int er=cur_path[cut-1].first,ec=cur_path[cut-1].second;
            int added=extend_greedy(new_path,vis,er,ec,T,rng,0.8);
            int new_score=ps+added;
            double delta=new_score-cur_score;
            if(delta>=0||uniform_real_distribution<>()(rng)<exp(delta/temp)){
                cur_score=new_score; cur_path=new_path;
                if(cur_score>best_score){best_score=cur_score;best_path=cur_path;}
            }
        } else {
            // Tail-cut or head-cut
            // For head-cut: reverse path, do tail-cut, reverse result
            Path work_path=(op==1)?Path(cur_path.rbegin(),cur_path.rend()):cur_path;
            int wL=(int)work_path.size();

            // Bias cut toward removing 10-40% from the end
            int min_keep=max(1,(int)(wL*0.6));
            int max_keep=wL-1;
            int cut;
            if(min_keep>=max_keep) cut=min_keep;
            else cut=uniform_int_distribution<int>(min_keep,max_keep)(rng);

            auto[ps,vis]=get_prefix_score(work_path,cut);
            Path new_path(work_path.begin(),work_path.begin()+cut);
            int er=work_path[cut-1].first,ec=work_path[cut-1].second;
            int added=extend_greedy(new_path,vis,er,ec,T,rng,rand_prob);
            int new_score=ps+added;
            if(op==1) reverse(new_path.begin(),new_path.end());

            double delta=new_score-cur_score;
            if(delta>=0||uniform_real_distribution<>()(rng)<exp(delta/temp)){
                cur_score=new_score; cur_path=new_path;
                if(cur_score>best_score){best_score=cur_score;best_path=cur_path;}
            }
        }
        iters++;
    }

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