#929542 (C++17) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	askr58
提出日時	2023-11-19 06:20:21
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	800 ms / 3,000 ms
コード長	10,455 bytes
コンパイル時間	4,383 ms
コンパイル使用メモリ	275,840 KB
実行使用メモリ	6,676 KB
スコア	2,120,930,802
最終ジャッジ日時	2023-11-19 06:21:04
合計ジャッジ時間	42,117 ms
ジャッジサーバーID （参考情報）	judge12 / judge13
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	764 ms 6,676 KB
testcase_01	AC	733 ms 6,676 KB
testcase_02	AC	714 ms 6,676 KB
testcase_03	AC	523 ms 6,676 KB
testcase_04	AC	494 ms 6,676 KB
testcase_05	AC	485 ms 6,676 KB
testcase_06	AC	581 ms 6,676 KB
testcase_07	AC	800 ms 6,676 KB
testcase_08	AC	688 ms 6,676 KB
testcase_09	AC	770 ms 6,676 KB
testcase_10	AC	453 ms 6,676 KB
testcase_11	AC	576 ms 6,676 KB
testcase_12	AC	610 ms 6,676 KB
testcase_13	AC	551 ms 6,676 KB
testcase_14	AC	580 ms 6,676 KB
testcase_15	AC	509 ms 6,676 KB
testcase_16	AC	436 ms 6,676 KB
testcase_17	AC	517 ms 6,676 KB
testcase_18	AC	653 ms 6,676 KB
testcase_19	AC	653 ms 6,676 KB
testcase_20	AC	539 ms 6,676 KB
testcase_21	AC	622 ms 6,676 KB
testcase_22	AC	392 ms 6,676 KB
testcase_23	AC	612 ms 6,676 KB
testcase_24	AC	738 ms 6,676 KB
testcase_25	AC	605 ms 6,676 KB
testcase_26	AC	609 ms 6,676 KB
testcase_27	AC	567 ms 6,676 KB
testcase_28	AC	410 ms 6,676 KB
testcase_29	AC	485 ms 6,676 KB
testcase_30	AC	668 ms 6,676 KB
testcase_31	AC	563 ms 6,676 KB
testcase_32	AC	647 ms 6,676 KB
testcase_33	AC	572 ms 6,676 KB
testcase_34	AC	752 ms 6,676 KB
testcase_35	AC	628 ms 6,676 KB
testcase_36	AC	564 ms 6,676 KB
testcase_37	AC	478 ms 6,676 KB
testcase_38	AC	571 ms 6,676 KB
testcase_39	AC	457 ms 6,676 KB
testcase_40	AC	746 ms 6,676 KB
testcase_41	AC	710 ms 6,676 KB
testcase_42	AC	571 ms 6,676 KB
testcase_43	AC	631 ms 6,676 KB
testcase_44	AC	660 ms 6,676 KB
testcase_45	AC	572 ms 6,676 KB
testcase_46	AC	537 ms 6,676 KB
testcase_47	AC	647 ms 6,676 KB
testcase_48	AC	463 ms 6,676 KB
testcase_49	AC	702 ms 6,676 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll linf=1000000000000000000;
random_device seed_gen;
mt19937 rnd(seed_gen());

template <typename T>
bool chmax(T& a,T b){
    if(a<b){
        a=b;
        return true;
    }else return false;
}
template <typename T>
bool chmin(T& a,T b){
    if(a>b){
        a=b;
        return true;
    }else return false;
}
vector<int> dx={1,0,-1,0};
vector<int> dy={0,1,0,-1};
struct bomb{
    ll c,l;
    int id;
    vector<pair<int,int>> range;
    bomb(){}
    bomb(ll c,ll l,int id):c(c),l(l),id(id){range.resize(l);}
};
struct bomb_instance{
    int x,y;
    int id;
    set<int> blown_shops;
    bomb_instance(){}
    bomb_instance(int x,int y,int id):x(x),y(y),id(id){}
};

bool operator==(bomb_instance& a,bomb_instance &b){
    return a.x==b.x&&a.y==b.y&&a.id==b.id;
}
int n,m;
vector<bomb> bombs;
vector<bomb_instance> locates;
vector<string> grid;
string ans;
int ans_count;
map<pair<int,int>,int> shop_num;
vector<pair<int,int>> shop_location;
set<pair<int,int>> shops;
vector<int> blown_num;

void read_input(){
    cin>>n>>m;
    ans_count=0;
    bombs.resize(m);
    grid.resize(n);
    for(int i=0;i<n;i++)cin>>grid[i];
    for(int i=0;i<m;i++){
        ll c,l;
        cin>>c>>l;
        bombs[i]=bomb(c,l,i);
        for(int j=0;j<l;j++){
            int a,b;
            cin>>a>>b;
            bombs[i].range[j]=make_pair(a,b);
        }
    }
    sort(bombs.begin(),bombs.end(),[](bomb a,bomb b)->bool{
        return a.c<b.c;
    });
    for(int i=0;i<n;i++)for(int j=0;j<n;j++){
        if(grid[i][j]=='@'){
            shop_num[{i,j}]=shop_location.size();
            shop_location.push_back({i,j});
            shops.insert({i,j});
        }
        
    }
    blown_num.resize(shop_location.size(),0);
}

void greedy(){
    vector<string> copy_grid=grid;

    auto good_bomb=[&](int x,int y)->void{
        bomb_instance res;
        int max_score=-1000000000;
        int max_dist=-1000000000;
        for(int i=0;i<m;i++){
            for(int j=0;j<20;j++){
                int p=rnd()%bombs[i].range.size();
                int nx=bombs[i].range[p].first,ny=bombs[i].range[p].second;
                if(x-nx<0||x-nx>=n||y-ny<0||y-ny>=n)continue;

                int shop_dist=10000000;
                for(auto[sx,sy]:shops)chmin(shop_dist,abs(sx-(x-nx))+abs(sy-(y-ny)));
                int score=-bombs[i].c-shop_dist;
                for(auto [lx,ly]:bombs[i].range){
                    int mx=x-nx+lx,my=y-ny+ly;
                    if(mx<0||mx>=n||my<0||my>=n)continue;
                    if(copy_grid[mx][my]=='#')score+=100;
                    else if(copy_grid[mx][my]=='@')score--;
                }
                if(score>max_score){
                    max_score=score;
                    res=bomb_instance(x-nx,y-ny,bombs[i].id);
                }
            }
        }
        int index=0;
        for(int i=0;i<m;i++)if(bombs[i].id==res.id)index=i;

        for(auto [lx,ly]:bombs[index].range){
            if(res.x+lx<0||res.x+lx>=n||res.y+ly<0||res.y+ly>=n)continue;
            copy_grid[res.x+lx][res.y+ly]='.';
            if(shop_num.count({res.x+lx,res.y+ly})){
                res.blown_shops.insert(shop_num[{res.x+lx,res.y+ly}]);
            }
        }
        for(int x:res.blown_shops)if(blown_num[x]!=-1)blown_num[x]++;
       
        locates.push_back(res);
    };
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<=i;j++){
            if(j>=n/2||i-j>=n/2)continue;
            int x=j,y=i-j;
            if(copy_grid[x][y]!='.')good_bomb(x,y);
            if(copy_grid[n-1-x][y]!='.')good_bomb(n-1-x,y);
            if(copy_grid[x][n-1-y]!='.')good_bomb(x,n-1-y);
            if(copy_grid[n-1-x][n-1-y]!='.')good_bomb(n-1-x,n-1-y);

            //for(string s:copy_grid)cout<<s<<endl;
        }        
    }
    //cout<<endl;
    //for(string s:copy_grid)cout<<s<<endl;
}

void go_straight(int from,int to){
    if(from==to)return;
    int now_x=from/n,now_y=from%n,next_x=to/n,next_y=to%n;
    vector<vector<int>> dist(n,vector<int>(n,-1));
    dist[now_x][now_y]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push(make_pair(0,from));
    while(!pq.empty()){
        int nx=pq.top().second/n,ny=pq.top().second%n;
        int l=pq.top().first;
        pq.pop();
        if(dist[nx][ny]!=l)continue;
        if(nx*n+ny==to)break;
        for(int i=0;i<4;i++){
            int nnx=nx+dx[i],nny=ny+dy[i];
            if(nnx<0||nnx>=n||nny<0||nny>=n)continue;
            int nl=l+1;
            if(grid[nnx][nny]!='.')nl++;
            if(dist[nnx][nny]!=-1&&dist[nnx][nny]<=nl)continue;
            else dist[nnx][nny]=nl;
            pq.push(make_pair(nl,nnx*n+nny));
        }
    }

    string route;
    string direction="ULDR";
    int nx=next_x,ny=next_y;
    while(nx!=now_x||ny!=now_y){
        for(int i=0;i<4;i++){
            int nnx=nx+dx[i],nny=ny+dy[i];
            if(nnx<0||nnx>=n||nny<0||nny>=n)continue;
            if((grid[nx][ny]=='.'&&dist[nnx][nny]+1==dist[nx][ny])||(grid[nx][ny]!='.'&&dist[nnx][nny]+2==dist[nx][ny])){
                nx=nnx;ny=nny;
                route+=direction[i];
                break;
            }
        }
    }
    ans_count+=route.size();
    reverse(route.begin(),route.end());
    for(char c:route){
        ans+="1 ";
        ans+=c;
        ans+="\n";
    }

}

int delete_bombs(){
    vector<string> copy_grid=grid;
    vector<int> perm(locates.size());
    for(int i=0;i<locates.size();i++)perm[i]=locates.size()-i-1;
    auto random_perm=[&](auto random_perm,int p)->void{
        if(p+1==perm.size())return;
        int q=rnd()%(perm.size()-p);
        if(q!=0)swap(perm[p],perm[q+p]);
        random_perm(random_perm,p+1);
    };
    vector<int> sakuzyo;
    for(int index:perm){
        int id=locates[index].id;
        int x=locates[index].x,y=locates[index].y;
        for(int j=0;j<m;j++){
            if(bombs[j].id==id){
                bool ok=false;
                for(auto [dx,dy]:bombs[j].range){
                    if(x+dx<0||x+dx>=n||y+dy<0||y+dy>=n)continue;
                    if(copy_grid[x+dx][y+dy]!='.'){
                        ok=true;
                        copy_grid[x+dx][y+dy]='.';

                    }
                }
                if(!ok)sakuzyo.push_back(index);
                break;
            }

        }
    }
    sort(sakuzyo.rbegin(),sakuzyo.rend());
    int res=sakuzyo.size();
    for(int i=0;i<res;i++){
        if(sakuzyo[i]+1!=locates.size())swap(locates[sakuzyo[i]],locates[locates.size()-1]);
        locates.pop_back();
    }
    return res;
}

int main()
{
    read_input();
    int now_x=0,now_y=0;
    int min_index=-1;
    vector<bomb_instance> last_bomb;
    while(1){
        locates=vector<bomb_instance>();
        //for(string s:grid)cout<<s<<endl;
        for(int i=0;i<blown_num.size();i++)blown_num[i]=-1;
        for(auto [sx,sy]:shops)blown_num[shop_num[{sx,sy}]]=0;
        greedy();
        //if(locates.size()>0)delete_bombs();
        min_index=-1;
        int min_cnt=100000;
        for(int i=0;i<blown_num.size();i++){
            if(blown_num[i]<min_cnt&&blown_num[i]!=-1){
                min_index=i;
                min_cnt=blown_num[i];
            }
        }
        last_bomb=vector<bomb_instance>();
        for(bomb_instance b:locates){
            if(b.blown_shops.count(min_index))last_bomb.push_back(b);
        }
        for(bomb_instance b:last_bomb){
            for(int i=0;i<locates.size();i++){
                if(locates[i]==b){
                    if(i+1!=locates.size())swap(locates[i],locates[locates.size()-1]);
                    locates.pop_back();
                    break;
                }
            }
        }
        int q=min(1,(int)locates.size());
        for(int i=0;i<q;i++){
            int next_x=10000,next_y=100000;
            int next_shop_x=10000,next_shop_y=10000;
            int max_dist=1000000000;
            bomb_instance c;map<pair<int,int>,int> shop_score;
            for(auto [sx,sy]:shops){
                int score=0;
                for(auto b:locates)if((abs(sx-b.x)+abs(sy-b.y))<=100)score++;
                shop_score[{sx,sy}]=score;
            }
            for(bomb_instance b:locates){
                for(auto[sx,sy]:shops){ 
                    int score=abs(now_x-sx)+2*abs(sx-b.x)+abs(now_y-sy)+2*abs(sy-b.y);
                    for(auto p:b.blown_shops)score+=shop_score[shop_location[p]];
                    if(score<max_dist){
                        next_x=b.x;next_y=b.y;next_shop_x=sx;next_shop_y=sy;
                        c=b;
                        max_dist=score;
                    }
                }
            }

            go_straight(now_x*n+now_y,next_shop_x*n+next_shop_y);
            ans+="2 "+to_string(c.id+1)+"\n";
            ans_count++;
            go_straight(next_shop_x*n+next_shop_y,next_x*n+next_y);
            ans+="3 "+to_string(c.id+1)+"\n";
            ans_count++;

            now_x=next_x;now_y=next_y;
            for(int j=0;j<locates.size();j++){
                if(locates[j]==c){
                    if(j+1!=locates.size())swap(locates[j],locates[locates.size()-1]);
                    locates.pop_back();
                    break;
                }
            }
            for(int j=0;j<m;j++){
                if(bombs[j].id==c.id){
                    for(auto[x,y]:bombs[j].range){
                        if(now_x+x<0||now_x+x>=n||now_y+y<0||now_y+y>=n)continue;
                        grid[now_x+x][now_y+y]='.';
                    }
                }
            }
            for(int p:c.blown_shops){
                if(shops.count(shop_location[p]))shops.erase(shop_location[p]);
                for(bomb_instance& b:locates)if(b.blown_shops.count(p))b.blown_shops.erase(p);
            }



        }

        if(locates.size()==0)break;

    }

    int next_shop_x=shop_location[min_index].first,next_shop_y=shop_location[min_index].second;
    go_straight(now_x*n+now_y,next_shop_x*n+next_shop_y);
    now_x=next_shop_x;now_y=next_shop_y;
    for(bomb_instance c:last_bomb){
        ans+="2 "+to_string(c.id+1)+"\n";
        ans_count++;
    }
    for(bomb_instance c:last_bomb){
        go_straight(now_x*n+now_y,c.x*n+c.y);
        ans+="3 "+to_string(c.id+1)+"\n";
        ans_count++;
        now_x=c.x;now_y=c.y;
    }

    cout<<ans_count<<endl;
    cout<<ans;

    



    
    return 0;
}

yukicoder

結果

テストケース

ソースコード