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

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	ぴぃいいいい
提出日時	2023-11-23 22:39:50
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,903 ms / 3,000 ms
コード長	16,701 bytes
コンパイル時間	8,811 ms
コンパイル使用メモリ	345,452 KB
実行使用メモリ	6,676 KB
スコア	2,816,704,769
最終ジャッジ日時	2023-11-23 22:42:33
合計ジャッジ時間	162,586 ms
ジャッジサーバーID （参考情報）	judge11 / judge13
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,902 ms 6,676 KB
testcase_01	AC	2,902 ms 6,676 KB
testcase_02	AC	2,902 ms 6,676 KB
testcase_03	AC	2,902 ms 6,676 KB
testcase_04	AC	2,903 ms 6,676 KB
testcase_05	AC	2,900 ms 6,676 KB
testcase_06	AC	2,901 ms 6,676 KB
testcase_07	AC	2,901 ms 6,676 KB
testcase_08	AC	2,902 ms 6,676 KB
testcase_09	AC	2,901 ms 6,676 KB
testcase_10	AC	2,901 ms 6,676 KB
testcase_11	AC	2,901 ms 6,676 KB
testcase_12	AC	2,901 ms 6,676 KB
testcase_13	AC	2,900 ms 6,676 KB
testcase_14	AC	2,902 ms 6,676 KB
testcase_15	AC	2,901 ms 6,676 KB
testcase_16	AC	2,902 ms 6,676 KB
testcase_17	AC	2,901 ms 6,676 KB
testcase_18	AC	2,901 ms 6,676 KB
testcase_19	AC	2,902 ms 6,676 KB
testcase_20	AC	2,901 ms 6,676 KB
testcase_21	AC	2,901 ms 6,676 KB
testcase_22	AC	2,902 ms 6,676 KB
testcase_23	AC	2,902 ms 6,676 KB
testcase_24	AC	2,902 ms 6,676 KB
testcase_25	AC	2,902 ms 6,676 KB
testcase_26	AC	2,902 ms 6,676 KB
testcase_27	AC	2,901 ms 6,676 KB
testcase_28	AC	2,902 ms 6,676 KB
testcase_29	AC	2,901 ms 6,676 KB
testcase_30	AC	2,902 ms 6,676 KB
testcase_31	AC	2,900 ms 6,676 KB
testcase_32	AC	2,901 ms 6,676 KB
testcase_33	AC	2,901 ms 6,676 KB
testcase_34	AC	2,902 ms 6,676 KB
testcase_35	AC	2,901 ms 6,676 KB
testcase_36	AC	2,901 ms 6,676 KB
testcase_37	AC	2,902 ms 6,676 KB
testcase_38	AC	2,901 ms 6,676 KB
testcase_39	AC	2,901 ms 6,676 KB
testcase_40	AC	2,903 ms 6,676 KB
testcase_41	AC	2,902 ms 6,676 KB
testcase_42	AC	2,902 ms 6,676 KB
testcase_43	AC	2,901 ms 6,676 KB
testcase_44	AC	2,901 ms 6,676 KB
testcase_45	AC	2,900 ms 6,676 KB
testcase_46	AC	2,902 ms 6,676 KB
testcase_47	AC	2,903 ms 6,676 KB
testcase_48	AC	2,902 ms 6,676 KB
testcase_49	AC	2,901 ms 6,676 KB

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

コンパイルメッセージ

main.cpp: In member function 'void Bombplan::greedy_all()':
main.cpp:188:38: warning: 'best_k' may be used uninitialized [-Wmaybe-uninitialized]
  188 |             is_broken |= explode_wind(best_k,best_i,best_j);
      |                          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:144:31: note: 'best_k' was declared here
  144 |             int best_i,best_j,best_k;
      |                               ^~~~~~
main.cpp:188:38: warning: 'best_j' may be used uninitialized [-Wmaybe-uninitialized]
  188 |             is_broken |= explode_wind(best_k,best_i,best_j);
      |                          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:144:24: note: 'best_j' was declared here
  144 |             int best_i,best_j,best_k;
      |                        ^~~~~~
main.cpp:188:38: warning: 'best_i' may be used uninitialized [-Wmaybe-uninitialized]
  188 |             is_broken |= explode_wind(best_k,best_i,best_j);
      |                          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:144:17: note: 'best_i' was declared here
  144 |             int best_i,best_j,best_k;
      |                 ^~~~~~

ソースコード

raw source code

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define print(var) std::cout<<#var<<"="<<(var)<<std::endl
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vmi vector<mint>
#define vvmi vector<vmi>
#define vvvmi vector<vvmi>
#define vs vector<string>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define bit(x,i)(((x)>>(i))&1)
#define inf (1<<30)
#define INF (1ll<<60)
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

inline double get_time() {
    using namespace std::chrono;
    return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
}
unsigned long xor128(void){
    static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned long t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
long long randInt(long long a,long long b){return a+xor128()%(b-a+1);}
double randDouble(double a,double b){return a+(b-a)*xor128()/(double)ULONG_MAX;}

double start_time;
int n,m;
char init_A[50][50];
int c[20],l[20];
bitset<2500> explode_range[20];
bitset<2500> mask_bit_x[50];
bitset<2500> mask_bit_y[50];
bitset<2500> init_broken;
bitset<2500> init_shop;

int center_shop_x,center_shop_y;
vpii around{{0,-1},{-1,0},{1,0},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};

bool is_valid(int x,int y){
    return 0<=x && x<n && 0<=y && y<n;
}
bitset<2500> explode_wind(int k, int x, int y){
    int diff_bit = n*(x-20) + (y-20);
    bitset<2500> tmpran = (diff_bit>0) ? (explode_range[k]<<diff_bit) : (explode_range[k]>>(-diff_bit));
    tmpran &= mask_bit_x[x] & mask_bit_y[y];
    return tmpran;
}

struct Field{
    bitset<2500> is_broken;
    bitset<2500> is_shop;
    int building = 0;
    int shop = 0;
    Field(){}
    Field(char AA[50][50]){
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(AA[i][j]=='.'){
                is_broken[i*n+j] = 1;
                is_shop[i*n+j] = 0;
            }
            if(AA[i][j]=='#'){
                is_broken[i*n+j] = 0;
                is_shop[i*n+j] = 0;
            }
            if(AA[i][j]=='@'){
                is_broken[i*n+j] = 0;
                is_shop[i*n+j] = 1;
            }
        }
        building = 2500 - is_broken.count();
        shop = is_shop.count();
    }
    void use(int k,int x,int y){
        is_broken |= explode_wind(k,x,y);
        is_shop &= ~is_broken; 
    }
};

struct Bombplan{
    bitset<2500> is_broken;
    bitset<2500> is_shop;
    set<tuple<int,int,int>> explodes;
    int cost;
    
    Bombplan(){}
    Bombplan(char AA[50][50]){
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(AA[i][j]=='.'){
                is_broken[i*n+j] = 1;
                is_shop[i*n+j] = 0;
            }
            if(AA[i][j]=='#'){
                is_broken[i*n+j] = 0;
                is_shop[i*n+j] = 0;
            }
            if(AA[i][j]=='@'){
                is_broken[i*n+j] = 0;
                is_shop[i*n+j] = 1;
            }
        }
        cost = 0;
        #ifdef LOG_DEBUG
        cerr<<"bombplan construct"<<endl;
        #endif 
    }
    
    void update_cost(){
        cost = 0;
        for(auto [k,x,y]:explodes){
            cost += c[k];
        }
    }

    //すべての位置の爆破方法をgreedyに決める
    void greedy_all(){
        int MAX_ITER = 40000;
        
        is_broken = init_broken;
        is_shop = init_shop;
        int building = 2500-init_broken.count();
        explodes.clear();
        #ifdef LOG_DEBUG
        cerr<<"greedy_all() header end"<<endl;
        #endif

        while(building>0){
            #ifdef LOG_DEBUG
            cerr<<"simulation building is "<<building<<endl;
            #endif
            int best_i,best_j,best_k;
            double best = (double)INF;
            //ランダムに爆発位置と種類を選ぶ
            #ifdef LOG_DEBUG
            int skip_zero = 0;
            #endif
            for(int iter=0;iter<MAX_ITER;iter++){
                int i = randInt(0,n-1);
                int j = randInt(0,n-1);
                int k = randInt(0,m-1);
                
                //もし爆弾を爆発させたら建物が何個壊れるかを計算 -> broken_cnt
                int diff_bit = n*(i-20) + (j-20);
                int broken_cnt = (explode_wind(k,i,j) & (~is_broken)).count();

                if(broken_cnt==0){
                    #ifdef LOG_DEBUG
                    skip_zero++;
                    #endif
                    continue;
                }

                double tmp = (double)c[k]/(double)(broken_cnt);
                if(chmin(best,tmp)){
                    best_i = i;
                    best_j = j;
                    best_k = k;
                    #ifdef LOG_DEBUG
                    cerr<<"update broken_cnt is "<<broken_cnt<<endl;
                    #endif
                }
            }
            
            #ifdef LOG_DEBUG
            cerr<<"skip_zero is "<<skip_zero<<endl;
            #endif

            //bestなものを選ぶ
            explodes.insert(make_tuple(best_k,best_i,best_j));

            #ifdef LOG_DEBUG
            cerr<<"accepted is "<<(tmpran & (~is_broken)).count()<<endl;
            #endif

            is_broken |= explode_wind(best_k,best_i,best_j);
            is_shop &= ~is_broken;

            building = 2500 - is_broken.count();
        }
        #ifdef LOG_DEBUG
        cerr<<"simulation end"<<endl;
        cerr<<"greedy_all() end"<<endl;
        #endif
        update_cost();
    }
    
    void output(){
        cerr<<explodes.size()<<endl;
        for(auto [k,x,y]:explodes){
            cerr<<k<<" "<<x<<" "<<y<<endl;
        }
    }

    vector<tuple<int,int,int>> explode_list(){
        vector<tuple<int,int,int>> res(all(explodes));
        return res;
    }
    
};

struct State{
    bitset<2500> is_broken, is_shop;
    int bomb[20];
    int bomb_sum=0;
    vector<pair<int,int>> hist;
    int building = 0;
    int shop = 0;
    int cost=0;
    int buy_cost=0;
    int move_cost=0;
    int nowx=0,nowy=0;

    State(){}
    State(char AA[50][50]){
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(AA[i][j]=='.'){
                is_broken[i*n+j] = 1;
                is_shop[i*n+j] = 0;
            }
            if(AA[i][j]=='#'){
                is_broken[i*n+j] = 0;
                is_shop[i*n+j] = 0;
            }
            if(AA[i][j]=='@'){
                is_broken[i*n+j] = 0;
                is_shop[i*n+j] = 1;
            }
        }
        building = 2500 - is_broken.count();
        shop = is_shop.count();
    }

    pair<int,vector<char>> smart_route(int sx,int sy,int gx,int gy){
        char x_ope = gx>sx ? 'D' : 'U';
        int dx = gx>sx ? 1 : -1;
        char y_ope = gy>sy ? 'R' : 'L';
        int dy = gy>sy ? 1 : -1;
        vvi dp(abs(gx-sx)+1,vi(abs(gy-sy)+1,inf));
        dp[0][0] = 0;
        for(int i=0;i<=abs(gx-sx);i++)for(int j=0;j<=abs(gy-sy);j++){
            if(i+1<=abs(gx-sx)){
                chmin(dp[i+1][j],dp[i][j]+(!is_broken[(sx+dx*(i+1))*n + (sy+dy*j)])+1);
            }
            if(j+1<=abs(gy-sy)){
                chmin(dp[i][j+1],dp[i][j]+(!is_broken[(sx+dx*i)*n + (sy+dy*(j+1))])+1);
            }
        }
        //dpから最短経路を復元
        vector<char> res(abs(gx-sx) + abs(gy-sy));
        int i=abs(gx-sx),j=abs(gy-sy);
        int index = res.size() - 1;
        while(i>0 || j>0){
            if(i>0 && dp[i-1][j]+(!is_broken[(sx+dx*i)*n + (sy+dy*j)])+1==dp[i][j]){
                res[index] = x_ope;
                i--;
            }
            else{
                res[index] = y_ope;
                j--;
            }
            index--;
        }
        int cost = dp[abs(gx-sx)][abs(gy-sy)];
        return make_pair(cost,res);
    }
    
    //d:方向
    void move(char d){
        if(d=='U'){
            hist.emplace_back(make_pair(1,0));
            nowx--;
        }
        if(d=='D'){
            hist.emplace_back(make_pair(1,1));
            nowx++;
            
        }
        if(d=='L'){
            hist.emplace_back(make_pair(1,2));
            nowy--;
        }
        if(d=='R'){
            hist.emplace_back(make_pair(1,3));
            nowy++;
        }
        if(is_broken[nowx*n+nowy]){
            cost += (bomb_sum+1)*(bomb_sum+1);
            move_cost += (bomb_sum+1)*(bomb_sum+1);
        }
        else{
            cost += 2*(bomb_sum+1)*(bomb_sum+1);
            move_cost += 2*(bomb_sum+1)*(bomb_sum+1);
        }
    }
    //x,y:目的地の座標
    void move(int x,int y){
        pair<int, vector<char>> route_result = smart_route(nowx, nowy, x, y);
        for (char direction : route_result.second) {
            move(direction);
        }
    }
    //piiに対応する座標に移動する
    void move(pii p){
        move(p.first,p.second);
    }
    //爆弾を買う
    //i:爆弾の種類
    void buy(int i){
        assert(is_shop[nowx*n+nowy]);
        hist.emplace_back(make_pair(2,i));
        bomb[i]++;
        bomb_sum++;
        cost+=c[i];
        buy_cost+=c[i];
    }
    //爆弾を使う
    //i:爆弾の種類
    void use(int i){
        assert(i>=0 && i<m);
        hist.emplace_back(make_pair(3,i));

        is_broken |= explode_wind(i,nowx,nowy);
        is_shop &= ~is_broken;

        building = 2500 - is_broken.count();
        shop = is_shop.count();

        bomb[i]--;
        bomb_sum--;
    }
    //爆弾を使ったときに壊れる建物の数,壊れる店の数,center_shopが壊れるかどうかを返す
    pair<int,int> use_simulate(int i,int x,int y){
        assert(i>=0 && i<m);

        int diff_bit = n*(x*20) + (y-20);
        bitset<2500> tmpran = explode_wind(i,x,y);
        int broken_building = (tmpran & (~is_broken)).count();
        int broken_shop = (tmpran & is_shop).count();
        

        return make_pair(broken_building,broken_shop);
    }
    //最も近い店の座標を返す
    pii nearest_shop(){
        int min_dist=inf;
        pii res;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(is_shop[i*n+j]){
                if(chmin(min_dist,abs(nowx-i)+abs(nowy-j))){
                    res = make_pair(i,j);
                }
            }
        }
        assert(min_dist!=inf);
        return res;
    }
    pii nearest_shop(int x, int y){
        int min_dist=inf;
        pii res;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(is_shop[i*n+j]){
                if(chmin(min_dist,abs(x-i)+abs(y-j))){
                    res = make_pair(i,j);
                }
            }
        }
        assert(min_dist!=inf);
        return res;
    }
    //最も近い店に移動する
    void move_nearest_shop(){
        pii p = nearest_shop();
        move(p);
    }
    
    //爆破場所と爆弾の種類を受け取ってその通り進める
    void plan_exec(vector<tuple<int,int,int>> plan){
        //planを実行
        int i=0;
        for(;i<(int)plan.size();i++){
            auto [k,x,y] = plan[i];
            auto [broken_building,broken_shop] = use_simulate(k,x,y);
            if(broken_building<building && broken_shop == shop){
                break;
            }
            auto shop_pos = nearest_shop(x,y);
            move(shop_pos);
            buy(k);
            move(x,y);
            use(k);
        }
        if(i<(int)plan.size()){
            //残りのplanを実行
            auto[k,x,y] = plan[i];
            auto shop_pos = nearest_shop(x,y);
            move(shop_pos);
            for(int j=i;j<(int)plan.size();j++){
                auto [k,x,y] = plan[j];
                buy(k);
            }
            for(int j=i;j<(int)plan.size();j++){
                auto [k,x,y] = plan[j];
                move(x,y);
                use(k);
            }
        }
    }
    
    //シミュレーション結果で評価
    double eval_func(double usecost,double broken_building,double broken_shop){
        if(broken_building==0) return (double)INF;
        else if(shop==broken_shop && building>broken_building) return (double)INF;
        else{
            double eval = (double)usecost/(double)broken_building;
            return eval;
        }

    }
    
    //出力
    void output(){
        cout<<hist.size()<<endl;
        for(auto p:hist){
            if(p.first==1){
                cout<<1<<" ";
                if(p.second==0) cout<<"U";
                if(p.second==1) cout<<"D";
                if(p.second==2) cout<<"L";
                if(p.second==3) cout<<"R";
                cout<<'\n';
            }
            else cout<<p.first<<" "<<p.second+1<<"\n";
        }
    }
};

struct Solve{
    char A[50][50];
    Bombplan best_plan;
    void IN(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);

        //入力
        cin>>n>>m;
        int center_shop_dist = inf;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>A[i][j];
                if(A[i][j]=='.'){
                    init_broken[i*n+j] = 1;
                    init_shop[i*n+j] = 0;
                }
                if(A[i][j]=='#'){
                    init_broken[i*n+j] = 0;
                    init_shop[i*n+j] = 0;
                }
                if(A[i][j]=='@'){
                    init_broken[i*n+j] = 0;
                    init_shop[i*n+j] = 1;
                    if(chmin(center_shop_dist,abs(i-n/2)+abs(j-n/2))){
                        center_shop_x = i;
                        center_shop_y = j;
                    }
                }
            }
        }
        for(int i=0;i<n;i++)for(int j=0;j<n;j++) init_A[i][j] = A[i][j];

        for(int i=0;i<m;i++){ //i番目の爆弾
            cin>>c[i]>>l[i];
            for(int j=0;j<l[i];j++){ //j番目の爆風
                int tmpa,tmpb;
                cin>>tmpa>>tmpb;
                tmpa+=20,tmpb+=20;
                explode_range[i][tmpa*n + tmpb] = 1;
            }
        }

        //mask-bitの計算
        bitset<2500> tate(0),yoko(0);
        for(int i=0;i<50;i++){
            tate[n*i] = 1;
            yoko[i] = 1;
        }
        for(int i=0;i<50;i++){
            mask_bit_x[i].reset();
            mask_bit_y[i].reset();
            for(int j=max(0,i-20);j<=min(49,i+20);j++){
                mask_bit_x[i] |= yoko<<(n*j);
                mask_bit_y[i] |= tate<<(j);
            }
        }
    }

    void solve(){
        /* cerr<<"start"<<endl;
        Bombplan bombplan(A);
        bombplan.greedy_all();
        cerr<<"cost:"<<bombplan.cost<<endl; */
        sa();
    }

    void sa(){
        Bombplan bombplan(A);
        bombplan.greedy_all();
        vector<tuple<int,int,int>> plan = bombplan.explode_list();
        int nn = plan.size();
        State best_state;
        State init_state(A);
        State state = init_state;
        state.plan_exec(plan);
        int pre_score = state.cost;
        double start_temp = 30;
        double end_temp = 0.1;
        int iter = 0;
        int MAX_TIME = 2900;

        while(get_time()-start_time<MAX_TIME){
            iter++;

            int i = randInt(0,nn-1);
            int j = randInt(0,nn-2);
            if(i<=j) j++;
            swap(plan[i],plan[j]);
            state = init_state;
            state.plan_exec(plan);
            int next_score = state.cost;
            double temp = start_temp + (end_temp-start_temp)*(get_time()-start_time)/MAX_TIME;
            double prob = exp((pre_score-next_score)/temp);
            if(prob>randDouble(0,1)){
                pre_score = next_score;
                best_state = state;
                #ifdef LOCAL
                cerr<<"iter:"<<iter<<endl;
                cerr<<"best_score:"<<pre_score<<endl;
                cerr<<"time:"<<get_time()-start_time<<"ms\n";
                #endif
            }
            else{
                swap(plan[i],plan[j]);
            }
        }
        #ifdef LOCAL
        cerr<<"total_cost:"<<pre_score<<endl;
        cerr<<"buy_cost:"<<best_state.buy_cost<<endl;
        cerr<<"move_cost:"<<best_state.move_cost<<endl;
        #endif
        
        best_state.output();
    }
};

int main(){
    start_time = get_time();
    Solve solve;
    solve.IN();
    solve.solve();
    #ifdef LOCAL
    cerr<<"time:"<<get_time()-start_time<<"ms\n";
    #endif
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード