#pragma GCC optimize("O3") #include using namespace std; #define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl #define print(var) std::cout<<#var<<"="<<(var)< #define vvi vector #define vvvi vector #define ll long long #define vll vector #define vvll vector #define vvvll vector #define vmi vector #define vvmi vector #define vvvmi vector #define vs vector #define pii pair #define vpii vector> #define bit(x,i)(((x)>>(i))&1) #define inf (1<<30) #define INF (1ll<<60) template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template 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(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; int c[20],l[20]; vector a[20],b[20]; 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> explodes; int cost; Bombplan(){} Bombplan(char AA[50][50]){ for(int i=0;i0){ int best_i,best_j,best_k; double best = (double)INF; if(building<3){ //建物のある位置を列挙 vector building_pos; for(int i=0;i> broken_hist[50][50]; for(auto [k,x,y]:explodes){ for(int i=0;i> bad_explodes = explodes; for(int i=0;i0){ int idx = randInt(0,bad_explodes.size()-1); auto it = bad_explodes.begin(); for(int i=0;i>,vector>> explode_list(){ vector> res(all(explodes)); //真ん中の店を破壊する爆発を区別する vector> prior_plan; vector> remain_plan; for(auto [k,x,y]:res){ bool plan_valid = true; for(int i=0;i> hist; int building = 0; int shop = 0; int cost=0; int buy_cost=0; int move_cost=0; int nowx=0,nowy=0; queue que; State(){} State(char AA[50][50]){ for(int i=0;iy_dist; }); for(auto e:tmp){ que.push(e); } } pair> 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]+(A[sx+dx*(i+1)][sy+dy*j]!='.')+1); } if(j+1<=abs(gy-sy)){ chmin(dp[i][j+1],dp[i][j]+(A[sx+dx*i][sy+dy*(j+1)]!='.')+1); } } //dpから最短経路を復元 vector 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]+(A[sx+dx*i][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(A[nowx][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> 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(i>=0 && i=0 && i use_simulate(int i,int x,int y){ assert(i>=0 && i=(double)INF){ for(int iter=0;iter<5000;iter++){ int i,j,k; i = randInt(0,n-1); j = randInt(0,n-1); k = randInt(0,m-1); int broken_building; int broken_shop; bool center_shop_broken; tie(broken_building,broken_shop,center_shop_broken) = use_simulate(k,i,j); if(broken_building==0) continue; int use_cost = 0; auto shop_pos = nearest_shop(i,j); //shopまでの移動 use_cost += smart_route(nowx,nowy,shop_pos.first,shop_pos.second).first; //shopでの購入 use_cost += c[k]; //shopから爆破場所までの移動 use_cost += 4*smart_route(shop_pos.first,shop_pos.second,i,j).first; double eval = eval_func(use_cost,broken_building,broken_shop,center_shop_broken); if(chmin(best_eval,eval)){ best_i = i; best_j = j; best_k = k; } } } auto shop_pos = nearest_shop(best_i,best_j); move(shop_pos.first,shop_pos.second); buy(best_k); move(best_i,best_j); use(best_k); /* for(int i=0;i=(double)INF){ int max_iter = 1000; for(int iter=0;iter> plan){ //planを実行 int i=0; for(;i<(int)plan.size();i++){ auto [k,x,y] = plan[i]; auto [broken_building,broken_shop,center_shop_broken] = use_simulate(k,x,y); if(broken_building> prior_plan, vector> remain_plan){ //prior_planを実行 for(auto [k,x,y]:prior_plan){ auto shop_pos = nearest_shop(x,y); move(shop_pos.first,shop_pos.second); buy(k); move(x,y); use(k); } //remain_planを実行 move_nearest_shop(); for(auto [k,x,y]:remain_plan){ buy(k); } for(auto [k,x,y]:remain_plan){ move(x,y); use(k); } } //シミュレーション結果で評価 double eval_func(double usecost,double broken_building,double broken_shop,bool center_shop_broken){ 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; if(center_shop_broken) eval *= 10; return eval; } } //差分評価 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[center_shop_x][center_shop_y]!='@') eval *= 10; return eval; } } //出力 void output(){ cout<>n>>m; int center_shop_dist = inf; for(int i=0;i>A[i][j]; //center_shop_x,center_shop_yを決める if(A[i][j]=='@'){ 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>c[i]>>l[i]; for(int j=0;j>tmpa>>tmpb; a[i].emplace_back(tmpa); b[i].emplace_back(tmpb); } } } void solve(){ /* Bombplan bombplan(A); bombplan.greedy_all(); cerr<<"cost:"<> plan = prior_plan; plan.insert(plan.end(),all(remain_plan)); int pn = prior_plan.size(); int rn = remain_plan.size(); 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 = 20; double end_temp = 0.1; int iter = 0; int MAX_TIME = 2900; while(get_time()-start_timerandDouble(0,1)){ pre_score = next_score; best_state = state; #ifdef LOCAL cerr<<"iter:"<