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

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

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

ソースコード

// Implementation by Claude Code - v5_chokudai.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 double TIME_BEAM = 0.15;
static const double TIME_SA   = 1.70;
static const int    M_PER_POS = 5;

int N, T;
int A[20][20];
using Path = vector<pair<int,int>>;
using Vis  = bitset<400>;
using Clock = chrono::steady_clock;
using TP    = chrono::time_point<Clock>;

inline int cell(int r,int c){ return r*20+c; }

static TP g_t0;
static double elapsed(){ return chrono::duration<double>(Clock::now()-g_t0).count(); }

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

// ---- Greedy ----
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 (single full pass) ----
struct BSt{int score;short r,c,parent;Vis visited;};
struct HEnt{int score;short r,c,parent;};

pair<int,Path> diversity_beam(){
    vector<BSt> cur;cur.reserve(N*N);
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){BSt 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<HEnt>> 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 bsc=-1,bst=0,bix=0;
    for(int i=0;i<(int)cur.size();i++) if(cur[i].score>bsc){bsc=cur[i].score;bst=0;bix=i;}

    auto prune=[&](vector<BSt>&cands)->vector<BSt>{
        sort(cands.begin(),cands.end(),[](const BSt&a,const BSt&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<BSt> 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++;}
        return nxt;
    };

    vector<BSt> cands;cands.reserve(cur.size()*4);
    for(int step=1;step<T&&elapsed()<TIME_BEAM;step++){
        cands.clear();
        for(int pi=0;pi<(int)cur.size();pi++){const BSt&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;BSt 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;
        auto nxt=prune(cands);
        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>bsc){bsc=nxt[i].score;bst=step;bix=i;}
        cur=nxt;
    }
    Path path;for(int cs=bst,ci=bix;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 {bsc,path};
}

// ---- SA helpers ----
int extend_greedy(Path&path,Vis&vis,int r,int c,int target,mt19937&rng,double rp){
    int added=0;
    while((int)path.size()<target){
        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=nbrs[0].first,nextc=nbrs[0].second;
        if(uniform_real_distribution<double>(0,1)(rng)<rp){
            int total=0;for(auto&q:nbrs)total+=A[q.first][q.second];
            if(total>0){int pick=uniform_int_distribution<int>(0,total-1)(rng),acc=0;for(auto&q:nbrs){acc+=A[q.first][q.second];if(pick<acc){nextr=q.first;nextc=q.second;break;}}}
        } else {
            int best=INT_MIN;nextr=-1;nextc=-1;
            for(auto&q:nbrs){int fn=A[q.first][q.second]*4-deg(q.first,q.second,vis);if(fn>best){best=fn;nextr=q.first;nextc=q.second;}}
        }
        vis.set(cell(nextr,nextc));path.push_back({nextr,nextc});added+=A[nextr][nextc];r=nextr;c=nextc;
    }
    return added;
}

pair<int,Vis> prefix_sv(const Path&path,int cut){
    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};
}

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];
    g_t0=Clock::now();

    // Phase 1: greedy initial
    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;}}

    // Phase 2: diversity beam
    {auto[sc,path]=diversity_beam();if(sc>best_score){best_score=sc;best_path=path;}}

    // Phase 3: SA
    mt19937 rng(42);
    Path cur_path=best_path;int cur_score=best_score;
    double sa_start=elapsed();

    while(elapsed()<sa_start+TIME_SA){
        int L=(int)cur_path.size();if(L==0) break;
        double progress=(elapsed()-sa_start)/TIME_SA;
        double temp=pow(1000.0,1.0-progress);

        double r01=uniform_real_distribution<double>(0,1)(rng);
        int op=(r01<0.45)?0:(r01<0.90)?1:2;
        double rp=(progress<0.5)?0.2:0.4;

        Path work_path=(op==1)?Path(cur_path.rbegin(),cur_path.rend()):cur_path;
        int wL=(int)work_path.size();
        int cut;
        if(op==2) cut=max(1,uniform_int_distribution<int>(1,max(1,wL/5))(rng));
        else{int mk=max(1,(int)(wL*0.6)),xk=wL-1;cut=(mk>=xk)?mk:uniform_int_distribution<int>(mk,xk)(rng);}

        auto[ps,vis]=prefix_sv(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,(op==2)?0.8:rp);
        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<double>(0,1)(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;}
        }
    }

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