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

• 問題: No.5019 Hakai Project
• ユーザー: ぴぃいいいい
• 提出日時: 2023-11-18 02:22:09
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 8,448 bytes
• コンパイル時間: 3,924 ms
• コンパイル使用メモリ: 281,504 KB
• 実行使用メモリ: 6,676 KB
• スコア: 0
• 最終ジャッジ日時: 2023-11-18 02:22:26
• 合計ジャッジ時間: 16,043 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

ファイルパターン	結果
other	TLE * 2 -- * 48

ソースコード

#include<bits/stdc++.h>
using namespace std;
#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;
vector<int> c(20),l(20);
vector<vector<int>> a(20),b(20);

bool is_valid(int x,int y){
    return 0<=x && x<n && 0<=y && y<n;
}

struct Bombplan{
    vector<vector<char>> A;

    Bombplan(){};
    Bombplan(vector<vector<char>> AA):A(AA){}
};

struct State{
    vector<vector<char>> A;
    int center_shop_x;
    int center_shop_y;
    vector<int> bomb;
    int bomb_sum=0;
    vector<pair<int,int>> hist;
    int building = 0;
    int shop = 0;
    ll cost=0;
    int nowx=0,nowy=0;

    State(){}
    State(vector<vector<char>> AA):A(AA){
        bomb.resize(m);
        int min_center_dist = inf;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(A[i][j]=='#' || A[i][j]=='@') building++;
            if(A[i][j]=='@'){
                shop++;
                if(chmin(min_center_dist,abs(i-n/2)+abs(j-n/2))){
                    center_shop_x = i;
                    center_shop_y = j;
                }
            }
        }
    }

    //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(A[nowx][nowy]=='.') cost += (bomb_sum+1)*(bomb_sum+1);
        else cost += 2*(bomb_sum+1)*(bomb_sum+1);
    }
    //x,y:目的地の座標
    void move(int x,int y){
        while(nowx!=x){
            if(nowx<x){
                move('D');
            }else{
                move('U');
            }
        }
        while(nowy!=y){
            if(nowy<y){
                move('R');
            }else{
                move('L');
            }
        }
    }
    void move(pii p){
        move(p.first,p.second);
    }
    //i:爆弾の種類
    void buy(int i){
        assert(i>=0 && i<m);
        hist.emplace_back(make_pair(2,i));
        bomb[i]++;
        bomb_sum++;
        cost+=c[i];
    }
    //i:爆弾の種類
    void use(int i){
        assert(i>=0 && i<m);
        hist.emplace_back(make_pair(3,i));
        for(int j=0;j<l[i];j++){
            int broken_x = nowx+a[i][j];
            int broken_y = nowy+b[i][j];
            if(!is_valid(broken_x,broken_y)) continue;
            if(A[broken_x][broken_y]=='.') continue;
            
            if(A[broken_x][broken_y]=='@'){
                shop--;
            }
            building--;
            A[broken_x][broken_y]='.';
        }
        bomb[i]--;
        bomb_sum--;
    }
    //最も近い店の座標を返す
    pii nearest_shop(){
        int min_dist=inf;
        pii res;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            if(A[i][j]=='@'){
                if(chmin(min_dist,abs(nowx-i)+abs(nowy-j))){
                    res = make_pair(i,j);
                }
            }
        }
        assert(min_dist!=inf);
        return res;
    }
    //最も近い店に移動する
    void move_nearest_shop(){
        pii p = nearest_shop();
        move(p);
    }
    //一手進める
    void one_step(){
        move_nearest_shop();
        assert(A[nowx][nowy]=='@');
        double best_eval = (double)INF+1;
        State best_state;
        while(best_eval>=(double)INF){
            for(int i=0;i<m;i++){
                State state = *this;
                state.buy(i);
                state.use(i);

                double eval = diff_eval(*this,state);
                if(chmin(best_eval,eval)){
                    best_state = state;
                }
            }
            for(int iter=0;iter<5000;iter++){
                int num = 1;
                vi i(num),j(num),k(num);
                for(int t=0;t<num;t++){
                    i[t] = randInt(0,n-1);
                    j[t] = randInt(0,n-1);
                    k[t] = randInt(0,m-1);
                }
                
                State state = *this;
                for(int t=0;t<num;t++){
                    state.buy(k[t]);
                }
                for(int t=0;t<num;t++){
                    state.move(i[t],j[t]);
                    state.use(k[t]);
                }

                double eval = diff_eval(*this,state);
                if(chmin(best_eval,eval)){
                    best_state = state;
                }
            }
        }
        
        /* for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            for(int k=0;k<m;k++){
                State state = *this;
                state.buy(k);
                state.move(i,j);
                state.use(k);
                int broken_building = building - state.building;
                int usecost = state.cost - cost;
                int eval;
                if(broken_building==0) eval = inf;
                else if(state.shop==0 && state.building!=0) eval = inf;
                else{
                    eval = usecost/broken_building;
                }
                if(chmin(best_eval,eval)){
                    best_i = i;
                    best_j = j;
                    best_k = k;
                }
            }
        } */
        *this = best_state;
    }
    //差分評価
    double diff_eval(State now, State nex){
        int broken_building = now.building - nex.building;
        int usecost = nex.cost - now.cost;
        if(broken_building==0) return (double)INF;
        else if(nex.shop==0 && nex.building!=0) return (double)INF;
        else{
            double eval = (double)usecost/(double)broken_building;
            if(nex.A[nex.center_shop_x][nex.center_shop_y]!='@') eval *= 10;
            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{
    vector<vector<char>> A;
    void IN(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cin>>n>>m;
        A.resize(n);
        for(int i=0;i<n;i++){
            A[i].resize(n);
            for(int j=0;j<n;j++){
                cin>>A[i][j];
            }
        }
        for(int i=0;i<m;i++){
            cin>>c[i]>>l[i];
            for(int j=0;j<l[i];j++){
                int tmpa,tmpb;
                cin>>tmpa>>tmpb;
                a[i].emplace_back(tmpa);
                b[i].emplace_back(tmpb);
            }
        }
    }

    void solve(){
        State state(A);
        while(state.building>0){
            state.one_step();
            cerr<<state.building<<" "<<state.shop<<" "<<state.cost<<endl;
        }
        state.output();
    }
};

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