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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: FplusFplusF
• 提出日時: 2026-05-02 18:23:30
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,908 ms / 2,000 ms
• コード長: 18,055 bytes
• コンパイル時間: 3,930 ms
• コンパイル使用メモリ: 365,320 KB
• 実行使用メモリ: 21,776 KB
• スコア: 2,017,461
• 最終ジャッジ日時: 2026-05-02 18:25:15
• 合計ジャッジ時間: 103,335 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin_ref(T &a,const T &b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax_ref(T &a,const T &b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

namespace Timer{
    chrono::steady_clock::time_point program_start,start;
    void program_start_snap(){
        program_start=start=chrono::steady_clock::now();
    }
    void snap(){
        start=chrono::steady_clock::now();
    }
    int get_ms(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
        return ms;
    }
    int get_ms_all_program(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
        return ms;
    }
}

mt19937 mt;
uint32_t rand_int(uint32_t r){  //[0,r)
    assert(r!=0);
    return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){  //[l,r)
    assert(l<r);
    return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){  //[0.0,1.0]
    return mt()*one_div_mt_max;
}
double rand_double(double l,double r){  //[l,r]
    return l+rand_double()*(r-l);
}
template<class T> T get_random_element(const vector<T> &v){
    assert(!v.empty());
    return v[rand_int(len(v))];
}

template<class T> void add(vector<T> &a,vector<T> b){
    for(auto i:b) a.push_back(i);
}

struct union_find{
    int n,now_comp_cnt;
    vector<int> par,sz,min_v;
    union_find(int n_):n(n_),now_comp_cnt(n_),par(n),sz(n,1),min_v(n){
        for(int i=0;i<n;i++){
            par[i]=i;
            min_v[i]=i;
        }
    }
    int root(int x){
        if(par[x]==x) return x;
        return par[x]=root(par[x]);
    }
    bool unite(int x,int y){
        x=root(x);
        y=root(y);
        if(x==y) return false;
        if(sz[x]<sz[y]) swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
        min_v[x]=min_v[y]=min(min_v[x],min_v[y]);
        now_comp_cnt--;
        return true;
    }
    bool same(int x,int y){
        int rx=root(x);
        int ry=root(y);
        return rx==ry;
    }
    int leader(int x){
        return min_v[root(x)];
    }
    int size(int x){
        return sz[root(x)];
    }
    int comp_cnt(){
        return now_comp_cnt;
    }
    vector<int> all_size(){
        vector<int> cnt(n,0);
        for(int i=0;i<n;i++){
            cnt[root(i)]++;
        }
        vector<int> ret;
        for(int i=0;i<n;i++){
            if(0<cnt[i]) ret.push_back(cnt[i]);
        }
        return ret;
    }
    vector<vector<int>> all_comp(){
        vector<vector<int>> comp(n);
        for(int i=0;i<n;i++){
            comp[root(i)].push_back(i);
        }
        int comp_idx=0;
        vector<vector<int>> ret(now_comp_cnt);
        for(int i=0;i<n;i++){
            if(!comp[i].empty()){
                swap(ret[comp_idx],comp[i]);
                comp_idx++;
            }
        }
        return ret;
    }
};


constexpr int N=20;

int T;

array<int,N*N> P;

array<array<int,4>,N*N> G;

array<bool,1<<9> B;
array<array<int,9>,N*N> A;

int one(int i,int j){
    return i*N+j;
}
pii two(int x){
    return {x/N,x%N};
}

namespace Solver{
    
    
    
    //https://eijirou-kyopro.hatenablog.com/entry/2024/02/01/115639
    
    constexpr int W=10000,tour_capacity=-1,hash_map_capacity=50*W;
    
    using Hash=uint32_t;
    using Score=int;
    
    array<Hash,N*N> grid_hash;

    template<class Key,class T> struct Hash_Map{
        uint32_t n;
        vector<bool> valid;
        vector<pair<Key,T>> data;
        Hash_Map(int n_):n(n_),valid(n,false),data(n){}

        pair<bool,int> get_index(Key key) const{
            Key i=key%n;
            while(valid[i]){
                if(data[i].first==key){
                    return {true,i};
                }
                i++;
                if(i==n) i=0;
            }
            return {false,i};
        }
        void set(int i,Key key,T value){
            assert(0<=i&&i<(int)n);
            valid[i]=true;
            data[i]={key,value};
        }
        T get(int i) const{
            assert(valid[i]);
            return data[i].second;
        }
        void clear(){
            fill(all(valid),false);
        }
    };

    
    struct Action{
        
        int dir=0;

        auto operator==(const Action &other) const{
            return dir==other.dir;
        }
    };

    struct Evaluator{
        int score=0;
        Hash hash=0;

        Evaluator(int score_,Hash hash_):score(score_),hash(hash_){}

        Score get_score() const{
            return -score;
        }

        /*auto operator<=>(const Evaluator &other) const{
            return this->get_score()<=>other.get_score();
        }*/
    };

    struct Candidate{
        int parent=-1;
        Action action;
        Evaluator evaluator;

        Candidate(int parent_,const Action action_,Evaluator evaluator_):parent(parent_),action(action_),evaluator(evaluator_){}

    };

    #include <atcoder/segtree>

    using max_segtree=atcoder::segtree<pair<Score,int>,[](pair<Score,int> a,pair<Score,int> b){return max(a,b);},[](){return pair<Score,int>{numeric_limits<Score>::lowest(),-INF};}>;

    struct Selector{
        bool fill=false;
        vector<Candidate> candidate_v;
        max_segtree seg;
        vector<pair<Score,int>> score_v;  //{score,index}を管理
        Hash_Map<Hash,int> hash_to_index;

        Selector():seg(W),score_v(W),hash_to_index(hash_map_capacity){
            rep(i,W) score_v[i]={-INF,i};
        }

        void push(const Candidate &candidate){

            const Hash hash=candidate.evaluator.hash;
            const Score score=candidate.evaluator.get_score();
            if(fill&&seg.all_prod().first<=score) return;
            auto [valid,i]=hash_to_index.get_index(hash);
            if(valid){
                int j=hash_to_index.get(i);
                if(hash==candidate_v[j].evaluator.hash){
                    if(fill){
                        if(score<seg.get(j).first){
                            candidate_v[j]=candidate;
                            seg.set(j,{score,j});
                        }
                    }else{
                        if(score<score_v[j].first){
                            candidate_v[j]=candidate;
                            score_v[j].first=score;
                        }
                    }
                    return;
                }
            }
            if(fill){
                int j=seg.all_prod().second;
                assert(0<=j&&j<W);
                hash_to_index.set(i,hash,j);
                candidate_v[j]=candidate;
                seg.set(j,{score,j});
            }else{
                int j=len(candidate_v);
                hash_to_index.set(i,hash,len(candidate_v));
                candidate_v.push_back(candidate);
                score_v[j].first=score;
                
                if(len(candidate_v)==W){
                    seg=max_segtree(score_v);
                    fill=true;
                }
            }
        }

        vector<Candidate> get_candidate_v(){
            return candidate_v;
        }

        Candidate get_best_candidate(){
            int best_idx=0;

            if(fill){
                rep(i,W){
                    if(seg.get(i).first<seg.get(best_idx).first){
                        best_idx=i;
                    }
                }
            }else{
                rep(i,len(candidate_v)){
                    if(score_v[i].first<score_v[best_idx].first){
                        best_idx=i;
                    }
                }
            }

            return candidate_v[best_idx];
        }
        
        void clear(){
            fill=false;
            candidate_v.clear();
            hash_to_index.clear();
        }
    };
    
    int start_pos=0;

    struct State{
        
        int pos=0,score=0;

        Hash hash=0;
        
        array<bool,N*N> vis;

        State(){
            vis.fill(false);
            vis[start_pos]=true;
            pos=start_pos;
            score=P[start_pos];
        }

        Evaluator calc_first_evaluator(){
            return Evaluator(0,0);
        }

        void push_candidates(Selector &selector,const Evaluator &parent_evaluator,int parent){
            
            rep(k,4){
                
                int to=G[pos][k];
                
                if(to==-1) continue;
                
                if(vis[to]) continue;
                
                
                vis[to]^=1;
            
                int b=0,cnt=0;
                
                rep(i,9){
                    if(A[to][i]!=-1&&!vis[A[to][i]]){
                        b|=1<<i;
                        cnt++;
                    }
                }
                int new_score=score+P[to];
                
                vis[to]^=1;
                if(cnt-vis[to]==0||!B[b]){
                    new_score-=10000;
                }
                
                
                
                Hash new_hash=hash^grid_hash[to];
                
                selector.push(Candidate(parent,Action(k),Evaluator(new_score,new_hash)));
                
            }
            
            
        }

        void advance(Action action){
            
            int k=action.dir;

            int to=G[pos][k];
            
            assert(to!=-1);
            
            assert(!vis[to]);
            
            vis[to]=true;
            score+=P[to];
            hash^=grid_hash[to];
            
            pos=to;
        }

        void undo(Action action){
            
            int k=action.dir^1;
            
            assert(vis[pos]);
            
            vis[pos]=false;
            score-=P[pos];
            hash^=grid_hash[pos];

            int to=G[pos][k];
            
            assert(to!=-1);
            
            
            pos=to;
        }
    };

    
    
    struct Tree{
        State state;
        Evaluator first_evaluator=state.calc_first_evaluator();
        vector<pair<int,Action>> pre_tour,new_tour;
        vector<Evaluator> leaf_eval_v;
        vector<vector<pair<Action,Evaluator>>> bucket_v;
        vector<Action> direct_load;

        Tree(){
            if(tour_capacity!=-1){
                pre_tour.reserve(tour_capacity);
                new_tour.reserve(tour_capacity);
            }
            leaf_eval_v.reserve(W);
            bucket_v.assign(W,{});
        }


        void dfs(Selector &selector){
            if(pre_tour.empty()){
                state.push_candidates(selector,first_evaluator,-1);
                return;
            }
            for(auto [leaf_idx,action]:pre_tour){
                if(0<=leaf_idx){
                    state.advance(action);
                    state.push_candidates(selector,leaf_eval_v[leaf_idx],leaf_idx);
                    state.undo(action);
                }else if(leaf_idx==-1){
                    state.advance(action);
                }else{
                    state.undo(action);
                }
            }
        }
        
        void update(const vector<Candidate> &candidate_v){
            leaf_eval_v.clear();
            if(pre_tour.empty()){
                for(const auto &candidate:candidate_v){
                    pre_tour.emplace_back(len(leaf_eval_v),candidate.action);
                    leaf_eval_v.emplace_back(candidate.evaluator);
                }
                return;
            }
            for(const auto &candidate:candidate_v){
                bucket_v[candidate.parent].emplace_back(candidate.action,candidate.evaluator);
            }
            
            int idx=0;

            for(;pre_tour[idx].first==-1&&pre_tour[idx].second==pre_tour.back().second;idx++){
                assert(pre_tour.back().first==-2);
                
                state.advance(pre_tour[idx].second);
                direct_load.push_back(pre_tour[idx].second);
                pre_tour.pop_back();
            }

            for(;idx<len(pre_tour);idx++){
                auto [leaf_idx,action]=pre_tour[idx];

                if(0<=leaf_idx){
                    if(bucket_v[leaf_idx].empty()) continue;
                    new_tour.emplace_back(-1,action);
                    for(const auto &[bucket_action,bucket_evaluator]:bucket_v[leaf_idx]){
                        int new_leaf_idx=len(leaf_eval_v);
                        new_tour.emplace_back(new_leaf_idx,bucket_action);
                        leaf_eval_v.push_back(bucket_evaluator);
                    }
                    bucket_v[leaf_idx].clear();
                    new_tour.emplace_back(-2,action);
                }else if(leaf_idx==-1){
                    new_tour.emplace_back(-1,action);
                }else{
                    assert(pre_tour[idx].first==-2);
                    assert(!new_tour.empty());
                    if(new_tour.back().first==-1) new_tour.pop_back();
                    else new_tour.emplace_back(-2,action);
                }
            }

            swap(pre_tour,new_tour);
            new_tour.clear();
        }

        vector<Action> get_action_path(int parent){
            vector<Action> ret=direct_load;
            for(auto [leaf_idx,action]:pre_tour){
                if(0<=leaf_idx){
                    if(leaf_idx==parent){
                        ret.push_back(action);
                        return ret;
                    }
                }else if(leaf_idx==-1){
                    ret.push_back(action);
                }else{
                    ret.pop_back();
                }
            }
            assert(0);
        }

    };
    
    pair<int,vector<Action>> beam_search(){

        
        vector<Action> ret;
        
        int best_score=0,best_start_pos=-1;
        
        
        while(true){
        
            Tree tree;
            Selector selector;
            rep(t,T-1){
                
                if(1900<Timer::get_ms()) break;

                tree.dfs(selector);

                vector<Candidate> candidate_v=selector.get_candidate_v();
                
                if(candidate_v.empty()) break;
                
                Candidate best_candidate=selector.get_best_candidate();

                //cerr << t << " " << len(selector.candidate_v) << " " << best_candidate.evaluator.get_score() << endl;

                
                if(1<=t){
                    vector<Action> action_v=tree.get_action_path(best_candidate.parent);
                    action_v.push_back(best_candidate.action);
                    if(chmax(best_score,best_candidate.evaluator.score)){
                        ret=action_v;
                        best_start_pos=start_pos;
                    }
                }
                

                tree.update(candidate_v);
                selector.clear();
            }
            if(1900<Timer::get_ms()) break;
            
            start_pos=rand_int(N*N);
        }
        
        cerr << best_score << ' ' << Timer::get_ms() << endl;

        return {best_start_pos,ret};
    }

    
    
    void solve(){
        rep(i,N*N) grid_hash[i]=mt();
        
        auto [pos,ans]=beam_search();
        
        cout << len(ans)+1 << '\n';
        
        
        auto [pi,pj]=two(pos);
        
        cout << pi << ' ' << pj << '\n';
        
        
        
        for(auto action:ans){
            
            pos=G[pos][action.dir];
            
            auto [i,j]=two(pos);
            
            cout << i << ' ' << j  << '\n';
        }
        
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Timer::program_start_snap();
    
    int n;
    
    cin >> n >> T;
    
    assert(n==N);
    
    rep(i,N*N){
        cin >> P[i];
    }
    
    
    rep(i,N*N) G[i].fill(-1);
    
    rep(i,N){
        rep(j,N){
            if(j+1<N){
                G[one(i,j)][3]=one(i,j+1);
                G[one(i,j+1)][2]=one(i,j);
            }
            if(i+1<N){
                G[one(i,j)][1]=one(i+1,j);
                G[one(i+1,j)][0]=one(i,j);
            }
        }
    }
    
    B.fill(false);
    
    rep(b,1<<9){
        
        vector<bool> grid(9);
        
        
        rep(i,9) grid[i]=b&(1<<i);
        
        union_find uf(9);
        
        rep(i,3){
            if(grid[3*i+0]&&grid[3*i+1]) uf.unite(3*i+0,3*i+1);
            if(grid[3*i+1]&&grid[3*i+2]) uf.unite(3*i+1,3*i+2);
        }
        
        rep(j,3){
            if(grid[3*0+j]&&grid[3*1+j]) uf.unite(3*0+j,3*1+j);
            if(grid[3*1+j]&&grid[3*2+j]) uf.unite(3*1+j,3*2+j);
        }
        
        int cnt=0,r=0;
        rep(i,9){
            if(grid[i]){
                cnt++;
                r=i;
            }
        }
        
        if(cnt==0) continue;
        
        if(uf.size(r)==cnt) B[b]=true;
    }
    
    vector<int> pi={-1,-1,-1,0,0,0,1,1,1},pj={-1,0,1,-1,0,1,-1,0,1};
    
    rep(i,N){
        rep(j,N){
            
            A[one(i,j)].fill(-1);
            
            rep(k,9){
                int ti=i+pi[k],tj=j+pj[k];
                if(ti<0||N<=ti||tj<0||N<=tj) continue;
                A[one(i,j)][k]=one(ti,tj);
            }
        }
    }



    Solver::solve();
    exit(0);
}