#929601 (C++23) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	FplusFplusF
提出日時	2023-11-19 15:28:35
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,793 ms / 3,000 ms
コード長	15,319 bytes
コンパイル時間	6,044 ms
コンパイル使用メモリ	317,360 KB
実行使用メモリ	6,676 KB
スコア	2,802,506,807
最終ジャッジ日時	2023-11-19 15:31:04
合計ジャッジ時間	147,775 ms
ジャッジサーバーID （参考情報）	judge14 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,751 ms 6,676 KB
testcase_01	AC	2,687 ms 6,676 KB
testcase_02	AC	2,647 ms 6,676 KB
testcase_03	AC	2,672 ms 6,676 KB
testcase_04	AC	2,609 ms 6,676 KB
testcase_05	AC	2,591 ms 6,676 KB
testcase_06	AC	2,701 ms 6,676 KB
testcase_07	AC	2,793 ms 6,676 KB
testcase_08	AC	2,681 ms 6,676 KB
testcase_09	AC	2,770 ms 6,676 KB
testcase_10	AC	2,610 ms 6,676 KB
testcase_11	AC	2,663 ms 6,676 KB
testcase_12	AC	2,687 ms 6,676 KB
testcase_13	AC	2,631 ms 6,676 KB
testcase_14	AC	2,670 ms 6,676 KB
testcase_15	AC	2,607 ms 6,676 KB
testcase_16	AC	2,591 ms 6,676 KB
testcase_17	AC	2,591 ms 6,676 KB
testcase_18	AC	2,788 ms 6,676 KB
testcase_19	AC	2,657 ms 6,676 KB
testcase_20	AC	2,656 ms 6,676 KB
testcase_21	AC	2,685 ms 6,676 KB
testcase_22	AC	2,625 ms 6,676 KB
testcase_23	AC	2,703 ms 6,676 KB
testcase_24	AC	2,712 ms 6,676 KB
testcase_25	AC	2,704 ms 6,676 KB
testcase_26	AC	2,674 ms 6,676 KB
testcase_27	AC	2,635 ms 6,676 KB
testcase_28	AC	2,571 ms 6,676 KB
testcase_29	AC	2,606 ms 6,676 KB
testcase_30	AC	2,673 ms 6,676 KB
testcase_31	AC	2,672 ms 6,676 KB
testcase_32	AC	2,721 ms 6,676 KB
testcase_33	AC	2,653 ms 6,676 KB
testcase_34	AC	2,775 ms 6,676 KB
testcase_35	AC	2,718 ms 6,676 KB
testcase_36	AC	2,637 ms 6,676 KB
testcase_37	AC	2,685 ms 6,676 KB
testcase_38	AC	2,676 ms 6,676 KB
testcase_39	AC	2,607 ms 6,676 KB
testcase_40	AC	2,770 ms 6,676 KB
testcase_41	AC	2,729 ms 6,676 KB
testcase_42	AC	2,632 ms 6,676 KB
testcase_43	AC	2,608 ms 6,676 KB
testcase_44	AC	2,710 ms 6,676 KB
testcase_45	AC	2,684 ms 6,676 KB
testcase_46	AC	2,711 ms 6,676 KB
testcase_47	AC	2,647 ms 6,676 KB
testcase_48	AC	2,601 ms 6,676 KB
testcase_49	AC	2,712 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 ld=long double;
const int INF=1e9;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
template<class T> void chmin(T &a,T b){
    if(a>b){
        a=b;
    }
}
template<class T> void chmax(T &a,T b){
    if(a<b){
        a=b;
    }
}
auto start=chrono::system_clock::now();
mt19937 mt;

int N,M;
vector<string> A;
struct bomb_info{
    int C,L;
    vector<int> a,b;
};
vector<bomb_info> bomb;
int to(int i,int j){
    return i*N+j;
}
int to(pii x){
    return to(x.first,x.second);
}
pii back(int x){
    int i=x/N;
    return {i,x-i*N};
}
bool outside(int i,int j){
    if(i<0||N<=i||j<0||N<=j) return true;
    return false;
}


void output_answer(vector<pii> &ans){
    cout << (int)ans.size() << '\n';
    for(auto &[s,t]:ans){
        if(s==1) cout << s << ' ' << char(t) << '\n';
        else cout << s << ' ' << t+1 << '\n';
    }
}

struct Solver{
    vector<int> bomb_v;
    vector<int> shop_idx;
    int can_bomb=5;
    vector<vector<double>> near_shop_dist(int k_th){
        vector<vector<double>> ave(N,vector<double>(N));
        rep(si,N){
            rep(sj,N){
                vector<int> v;
                for(auto &ij:bomb_v){
                    int i,j;
                    tie(i,j)=back(ij);
                    v.push_back(abs(i-si)+abs(j-sj));
                }
                sort(all(v));
                int sum=0;
                rep(i,k_th) sum+=v[i];
                ave[si][sj]=double(sum)/double(k_th);
            }
        }
        return ave;
    }
    vector<int> ok_bomb;
    vector<pii> bomb_cover(vector<vector<double>> ave){
        vector<pair<double,int>> bomb_sort(M);
        rep(i,M){
            bomb_sort[i]={double(bomb[i].C)/double(bomb[i].L),i};
        }
        sort(all(bomb_sort));
        ok_bomb.resize(M,0);
        rep(i,can_bomb) ok_bomb[bomb_sort[i].second]=1;
        vector<string> now_grid=A;
        vector<pii> ret;
        while(true){
            double min_score=INF;
            pii max_cover={-1,-1};
            rep(i,N){
                rep(j,N){
                    rep(bomb_idx,M){
                        if(ok_bomb[bomb_idx]==0) continue;
                        int cnt=0;
                        rep(k,bomb[bomb_idx].L){
                            int ti=i+bomb[bomb_idx].a[k],tj=j+bomb[bomb_idx].b[k];
                            if(outside(ti,tj)) continue;
                            if(now_grid[ti][tj]!='.') cnt++;
                        }
                        double now_score=INF;
                        if(0<cnt) now_score=double(bomb[bomb_idx].C+ave[i][j]*5.0)/double(cnt);
                        if(now_score<min_score){
                            min_score=now_score;
                            max_cover={to(i,j),bomb_idx};
                        }
                    }
                    
                }
            }
            if(max_cover.first==-1) break;
            ret.push_back(max_cover);
            int ni,nj;
            tie(ni,nj)=back(max_cover.first);
            rep(k,bomb[max_cover.second].L){
                int ti=ni+bomb[max_cover.second].a[k],tj=nj+bomb[max_cover.second].b[k];
                if(outside(ti,tj)) continue;
                now_grid[ti][tj]='.';
            }
        }
        return ret;
    }
    vector<int> pi={0,1,0,-1},pj={1,0,-1,0};
    int root_cost(int a,int b,vector<string> &grid,int bomb_cnt){
        int ai,aj,bi,bj;
        tie(ai,aj)=back(a);
        tie(bi,bj)=back(b);
        vector<vector<int>> dist(N,vector<int>(N,INF));
        dist[ai][aj]=0;
        priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> pq;
        pq.push({0,{ai,aj}});
        while(!pq.empty()){
            int d;
            pii ij;
            tie(d,ij)=pq.top();
            pq.pop();
            int i,j;
            tie(i,j)=ij;
            if(dist[i][j]<d) continue;
            if(i==bi&&j==bj) break;
            rep(k,4){
                int ti=i+pi[k],tj=j+pj[k];
                if(outside(ti,tj)) continue;
                int cost=(bomb_cnt+1)*(bomb_cnt+1);
                if(grid[ti][tj]!='.') cost*=2;
                if(dist[i][j]+cost<dist[ti][tj]){
                    dist[ti][tj]=d+cost;
                    pq.push({dist[ti][tj],{ti,tj}});
                }
            }
        }
        return dist[bi][bj];
    }
    string root(int a,int b,vector<string> &grid,int bomb_cnt){
        int ai,aj,bi,bj;
        tie(ai,aj)=back(a);
        tie(bi,bj)=back(b);
        vector<vector<int>> dist(N,vector<int>(N,INF));
        dist[ai][aj]=0;
        vector<vector<pii>> prev(N,vector<pii>(N));
        priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> pq;
        pq.push({0,{ai,aj}});
        while(!pq.empty()){
            int d;
            pii ij;
            tie(d,ij)=pq.top();
            pq.pop();
            int i,j;
            tie(i,j)=ij;
            if(dist[i][j]<d) continue;
            if(i==bi&&j==bj) break;
            rep(k,4){
                int ti=i+pi[k],tj=j+pj[k];
                if(outside(ti,tj)) continue;
                int cost=(bomb_cnt+1)*(bomb_cnt+1);
                if(grid[ti][tj]!='.') cost*=2;
                if(dist[i][j]+cost<dist[ti][tj]){
                    dist[ti][tj]=d+cost;
                    prev[ti][tj]={i,j};
                    pq.push({dist[ti][tj],{ti,tj}});
                }
            }
        }
        string ret;
        int ni=bi,nj=bj;
        while(!(ni==ai&&nj==aj)){
            int ti,tj;
            tie(ti,tj)=prev[ni][nj];
            if(ti==ni&&tj<nj) ret.push_back('R');
            if(ti==ni&&nj<tj) ret.push_back('L');
            if(tj==nj&&ti<ni) ret.push_back('D');
            if(tj==nj&&ni<ti) ret.push_back('U');
            ni=ti;
            nj=tj;
        }
        reverse(all(ret));
        return ret;
    }
    int calc_score(vector<pii> &ans){
        int ni=0,nj=0;
        vector<int> bomb_cnt(M,0);
        int b=0;
        vector<string> now_grid=A;
        int c=0;
        for(auto &[s,t]:ans){
            if(s==1){
                if(char(t)=='L') nj--;
                else if(char(t)=='R') nj++;
                else if(char(t)=='U') ni--;
                else if(char(t)=='D') ni++;
                else assert(0);
                assert(!outside(ni,nj));
                if(now_grid[ni][nj]=='.') c+=(b+1)*(b+1);
                else c+=2*(b+1)*(b+1);
            }else if(s==2){
                assert(now_grid[ni][nj]=='@');
                int y=t;
                assert(0<=y&&y<=M-1);
                bomb_cnt[y]++;
                b++;
                c+=bomb[y].C;
            }else if(s==3){
                int z=t;
                assert(0<=z&&z<=M-1);
                assert(1<=bomb_cnt[z]);
                bomb_cnt[z]--;
                b--;
                rep(k,bomb[z].L){
                    int ti=ni+bomb[z].a[k],tj=nj+bomb[z].b[k];
                    if(outside(ti,tj)) continue;
                    now_grid[ti][tj]='.';
                }
            }else{
                assert(0);
            }
        }
        rep(i,N){
            rep(j,N){
                if(now_grid[i][j]!='.'){
                    return 1;
                }
            }
        }
        return max(10ll,1000000000000ll/(10000+c));
    }
    vector<pii> cover_to_ans(vector<pii> &cover_v){
        vector<string> now_grid=A;
        vector<pii> now_ans;
        int now=0;
        int shop_cnt=0;
        rep(i,N){
            rep(j,N){
                if(A[i][j]=='@') shop_cnt++;
            }
        }
        int bomb_cnt=0;
        set<pii> last_shop_set;
        rep(t,int(cover_v.size())){
            int idx,now_bomb_idx;
            tie(idx,now_bomb_idx)=cover_v[t];
            int idx_i,idx_j;
            tie(idx_i,idx_j)=back(idx);
            int before_shop_cnt=shop_cnt;
            rep(k,bomb[now_bomb_idx].L){
                int ti=idx_i+bomb[now_bomb_idx].a[k],tj=idx_j+bomb[now_bomb_idx].b[k];
                if(outside(ti,tj)) continue;
                if(now_grid[ti][tj]=='@') shop_cnt--;
            }
            if(shop_cnt==0&&!last_shop_set.count(cover_v[t])){
                last_shop_set.insert(cover_v[t]);
                shop_cnt=before_shop_cnt;
                cover_v.push_back(cover_v[t]);
                cover_v.erase(cover_v.begin()+t);
                t--;
                continue;
            }
            pii mn={INF,INF};
            for(auto &x:bomb_v){
                int i,j;
                tie(i,j)=back(x);
                if(now_grid[i][j]=='@') chmin(mn,{root_cost(now,x,now_grid,bomb_cnt),x});
            }
            if(mn.first!=INF){
                for(auto &i:root(now,mn.second,now_grid,bomb_cnt)){
                    now_ans.push_back({1,i});
                }
                now=mn.second;
                int i,j;
                tie(i,j)=back(mn.second);
                if(shop_cnt==0){
                    for(int k=t;k<int(cover_v.size());k++){
                        now_ans.push_back({2,cover_v[k].second});
                        bomb_cnt++;
                    }
                }else{
                    now_ans.push_back({2,now_bomb_idx});
                    bomb_cnt++;
                }
            }
            for(auto &j:root(now,idx,now_grid,bomb_cnt)){
                now_ans.push_back({1,j});
            }
            now=idx;
            now_ans.push_back({3,now_bomb_idx});
            bomb_cnt--;
            rep(k,bomb[now_bomb_idx].L){
                int ti=idx_i+bomb[now_bomb_idx].a[k],tj=idx_j+bomb[now_bomb_idx].b[k];
                if(outside(ti,tj)) continue;
                now_grid[ti][tj]='.';
            }
        }
        return now_ans;
    }
    int fake_root_cost(int a,int b,int bomb_cnt){
        int ai,aj,bi,bj;
        tie(ai,aj)=back(a);
        tie(bi,bj)=back(b);
        return (abs(ai-bi)+abs(aj-bj))*(bomb_cnt+1)*(bomb_cnt+1);
    }
    int fake_cost(vector<pii> cover_v,vector<vector<vector<int>>> &shop_explosion){
        vector<int> shop_ok(int(bomb_v.size()),1);
        int now=0;
        int shop_cnt=int(bomb_v.size());
        int bomb_cnt=0;
        set<pii> last_shop_set;
        int ret=0;
        rep(t,int(cover_v.size())){
            int idx,now_bomb_idx;
            tie(idx,now_bomb_idx)=cover_v[t];
            int idx_i,idx_j;
            tie(idx_i,idx_j)=back(idx);
            int before_shop_cnt=shop_cnt;
            for(auto &ij:shop_explosion[idx][now_bomb_idx]){
                if(shop_ok[shop_idx[ij]]==1){
                    shop_cnt--;
                }
            }
            if(shop_cnt==0&&!last_shop_set.count(cover_v[t])){
                last_shop_set.insert(cover_v[t]);
                shop_cnt=before_shop_cnt;
                cover_v.push_back(cover_v[t]);
                cover_v.erase(cover_v.begin()+t);
                t--;
                continue;
            }
            pii mn={INF,INF};
            for(auto &x:bomb_v){
                if(shop_ok[shop_idx[x]]==1) chmin(mn,{fake_root_cost(now,x,bomb_cnt),x});
            }
            if(mn.first!=INF){
                ret+=mn.first;
                now=mn.second;
                int i,j;
                tie(i,j)=back(mn.second);
                if(shop_cnt==0){
                    for(int k=t;k<int(cover_v.size());k++){
                        ret+=bomb[cover_v[k].second].C;
                        bomb_cnt++;
                    }
                }else{
                    ret+=bomb[now_bomb_idx].C;
                    bomb_cnt++;
                }
            }
            ret+=fake_root_cost(now,idx,bomb_cnt);
            now=idx;
            bomb_cnt--;
            for(auto &ij:shop_explosion[idx][now_bomb_idx]){
                shop_ok[shop_idx[ij]]=0;
            }
        }
        return ret;
    }
    void solve(){
        shop_idx.resize(N*N);
        int cnt_b=0;
        rep(i,N){
            rep(j,N){
                if(A[i][j]=='@'){
                    bomb_v.push_back(to(i,j));
                    shop_idx[to(i,j)]=cnt_b;
                    cnt_b++;
                }
            }
        }
        vector<pii> cover_v=bomb_cover(near_shop_dist(5));
        int block_size=50/3;
        sort(cover_v.begin(),cover_v.end(),
        [&](pii i,pii j){
            int il,ir,jl,jr;
            tie(il,ir)=back(i.first);
            tie(jl,jr)=back(j.first);
            int block_i=il/block_size,block_j=jl/block_size;
            if(block_i!=block_j) return il<jl;
            if(block_i&1) return ir>jr;
            else return ir<jr;
        }
        );
        vector<vector<vector<int>>> shop_explosion(N*N,vector<vector<int>>(M));
        rep(i,N){
            rep(j,N){
                rep(bomb_idx,M){
                    if(ok_bomb[bomb_idx]==0) continue;
                    rep(k,bomb[bomb_idx].L){
                        int ti=i+bomb[bomb_idx].a[k],tj=j+bomb[bomb_idx].b[k];
                        if(outside(ti,tj)) continue;
                        if(A[ti][tj]=='@') shop_explosion[to(i,j)][bomb_idx].push_back(to(ti,tj));
                    }
                }
            }
        }
        vector<pii> min_cost_cover_v=cover_v;
        int min_cost=fake_cost(min_cost_cover_v,shop_explosion);
        int cover_size=min_cost_cover_v.size();
        while(true){
            auto now=chrono::system_clock::now();
            int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
            if(2500<=ms) break;
            if(mt()%2==0){
                int cut_idx=mt()%cover_size,cut_k=mt()%(cover_size-cut_idx);
                vector<pii> new_cover_v=min_cost_cover_v,add_v;
                rep(i,cover_size){
                    if(cut_idx<=i&&i<=cut_idx+cut_k){
                        add_v.push_back(min_cost_cover_v[i]);
                        continue;
                    }
                    new_cover_v.push_back(min_cost_cover_v[i]);
                }
                int insert_idx=mt()%(int(new_cover_v.size())+1);
                new_cover_v.insert(new_cover_v.begin()+insert_idx,all(add_v));
                int new_cost=fake_cost(new_cover_v,shop_explosion);
                if(new_cost<=min_cost){
                    min_cost=new_cost;
                    min_cost_cover_v=new_cover_v;
                }
            }else{
                int a=mt()%cover_size,b=mt()%cover_size;
                if(a==b) continue;
                swap(min_cost_cover_v[a],min_cost_cover_v[b]);
                int new_cost=fake_cost(min_cost_cover_v,shop_explosion);
                if(new_cost<=min_cost) min_cost=new_cost;
                else swap(min_cost_cover_v[a],min_cost_cover_v[b]);
            }
        }
        vector<pii> ans=cover_to_ans(min_cost_cover_v);
        output_answer(ans);
    }
}Solver;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    A.resize(N);
    rep(i,N) cin >> A[i];
    bomb.resize(M);
    rep(i,M){
        cin >> bomb[i].C >> bomb[i].L;
        bomb[i].a.resize(bomb[i].L);
        bomb[i].b.resize(bomb[i].L);
        rep(j,bomb[i].L) cin >> bomb[i].a[j] >> bomb[i].b[j];
    }
    Solver.solve();
}

yukicoder

結果

テストケース

ソースコード