結果
問題 | No.5019 Hakai Project |
ユーザー |
![]() |
提出日時 | 2023-11-23 19:49:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 25,231 bytes |
コンパイル時間 | 8,704 ms |
コンパイル使用メモリ | 346,512 KB |
実行使用メモリ | 6,676 KB |
スコア | 2,741,307,087 |
最終ジャッジ日時 | 2023-11-23 19:52:24 |
合計ジャッジ時間 | 161,841 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 49 RE * 1 |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/vector:64, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/functional:62, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:71, from main.cpp:2: In member function 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>]', inlined from 'void Bombplan::greedy_all()' at main.cpp:171:50: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:1124:32: warning: 'best_k' may be used uninitialized [-Wmaybe-uninitialized] 1124 | return *(this->_M_impl._M_start + __n); | ~~~~~~~~~~~~~~^~~~~~~~ main.cpp: In member function 'void Bombplan::greedy_all()': main.cpp:110:31: note: 'best_k' was declared here 110 | int best_i,best_j,best_k; | ^~~~~~ main.cpp:171:50: warning: 'best_j' may be used uninitialized [-Wmaybe-uninitialized] 171 | int broken_y = best_j+b[best_k][x]; | ^ main.cpp:110:24: note: 'best_j' was declared here 110 | int best_i,best_j,best_k; | ^~~~~~ main.cpp:170:50: warning: 'best_i' may be used uninitialized [-Wmaybe-uninitialized] 170 | int broken_x = best_i+a[best_k][x]; | ^ main.cpp:110:17: note: 'best_i' was declared here 110 | int best_i,best_j,best_k; | ^~~~~~
ソースコード
#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;int c[20],l[20];vector<int> 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<n && 0<=y && y<n;}struct Field{char A[50][50];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++) A[i][j] = AA[i][j];for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(A[i][j]=='.') continue;if(A[i][j]=='@') shop++;building++;}}void use(int k,int x,int y){for(int i=0;i<l[k];i++){int broken_x = x+a[k][i];int broken_y = y+b[k][i];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]='.';}}};struct Bombplan{char A[50][50];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++) A[i][j] = AA[i][j];cost = 0;}void update_cost(){cost = 0;for(auto [k,x,y]:explodes){cost += c[k];}}//すべての位置の爆破方法をgreedyに決めるvoid greedy_all(){int MAX_ITER = 20000;char AA[50][50];for(int i=0;i<n;i++)for(int j=0;j<n;j++) AA[i][j] = A[i][j];int building = 0;for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(AA[i][j]=='.') continue;building++;}explodes.clear();while(building>0){int best_i,best_j,best_k;double best = (double)INF;if(building<3){//建物のある位置を列挙vector<pii> building_pos;for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(AA[i][j]=='.') continue;building_pos.emplace_back(make_pair(i,j));}for(int iter=0;iter<MAX_ITER;iter++){int break_idx = randInt(0,building_pos.size()-1);int break_x = building_pos[break_idx].first;int break_y = building_pos[break_idx].second;int k = randInt(0,m-1);int t = randInt(0,l[k]-1);int i = break_x - a[k][t];int j = break_y - b[k][t];if(!is_valid(i,j)) continue;int broken_cnt = 0;for(int x=0;x<l[k];x++){int broken_x = i+a[k][x];int broken_y = j+b[k][x];if(is_valid(broken_x,broken_y) && AA[broken_x][broken_y]!='.'){broken_cnt++;}}if(broken_cnt==0) continue;double tmp = (double)c[k]/(double)(broken_cnt);if(chmin(best,tmp)){best_i = i;best_j = j;best_k = k;}}}else{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);int broken_cnt = 0;for(int x=0;x<l[k];x++){int broken_x = i+a[k][x];int broken_y = j+b[k][x];if(is_valid(broken_x,broken_y) && AA[broken_x][broken_y]!='.'){broken_cnt++;}}if(broken_cnt==0) continue;double tmp = (double)c[k]/(double)(broken_cnt);if(chmin(best,tmp)){best_i = i;best_j = j;best_k = k;}}}explodes.insert(make_tuple(best_k,best_i,best_j));for(int x=0;x<l[best_k];x++){int broken_x = best_i+a[best_k][x];int broken_y = best_j+b[best_k][x];if(!is_valid(broken_x,broken_y)) continue;if(AA[broken_x][broken_y]=='.') continue;AA[broken_x][broken_y] = '.';building--;}}update_cost();}void output(){cerr<<explodes.size()<<endl;for(auto [k,x,y]:explodes){cerr<<k<<" "<<x<<" "<<y<<endl;}}void compress(){set<tuple<int,int,int>> broken_hist[50][50];for(auto [k,x,y]:explodes){for(int i=0;i<l[k];i++){int broken_x = x+a[k][i];int broken_y = y+b[k][i];if(!is_valid(broken_x,broken_y)) continue;if(A[broken_x][broken_y]=='.') continue;broken_hist[broken_x][broken_y].insert(make_tuple(k,x,y));}}//bad_explodesの中から一つ選んで消せるようにするset<tuple<int,int,int>> bad_explodes = explodes;for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(A[i][j]=='.') continue;if(broken_hist[i][j].size()==1){bad_explodes.erase(*broken_hist[i][j].begin());}}while(bad_explodes.size()>0){int idx = randInt(0,bad_explodes.size()-1);auto it = bad_explodes.begin();for(int i=0;i<idx;i++) it++;auto [k,x,y] = *it;explodes.erase(make_tuple(k,x,y));bad_explodes.erase(make_tuple(k,x,y));cost -= c[k];for(int t=0;t<l[k];t++){int broken_x = x+a[k][t];int broken_y = y+b[k][t];if(!is_valid(broken_x,broken_y)) continue;if(A[broken_x][broken_y]=='.') continue;broken_hist[broken_x][broken_y].erase(make_tuple(k,x,y));if(broken_hist[broken_x][broken_y].size()==1){bad_explodes.erase(*broken_hist[broken_x][broken_y].begin());}}}}pair<vector<tuple<int,int,int>>,vector<tuple<int,int,int>>> explode_list(){vector<tuple<int,int,int>> res(all(explodes));//真ん中の店を破壊する爆発を区別するvector<tuple<int,int,int>> prior_plan;vector<tuple<int,int,int>> remain_plan;for(auto [k,x,y]:res){bool plan_valid = true;for(int i=0;i<l[k];i++){int broken_x = x+a[k][i];int broken_y = y+b[k][i];if(broken_x==center_shop_x && broken_y==center_shop_y){plan_valid = false;break;}}if(plan_valid){prior_plan.emplace_back(make_tuple(k,x,y));}else{remain_plan.emplace_back(make_tuple(k,x,y));}}return make_pair(prior_plan,remain_plan);}double eval_func(double penalty){Field field(A);for(auto [k,x,y]:explodes){field.use(k,x,y);}return (double)cost + (double)field.building * penalty;}void test(){}};struct State{char A[50][50];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;queue<pii> que;State(){}State(char AA[50][50]){for(int i=0;i<n;i++)for(int j=0;j<n;j++) A[i][j] = AA[i][j];vpii tmp;for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(A[i][j]=='.') continue;tmp.emplace_back(make_pair(i,j));building++;if(A[i][j]=='@'){shop++;}}sort(all(tmp),[](pii x, pii y){int x_dist = abs(x.first-n/2)+abs(x.second-n/2);int y_dist = abs(y.first-n/2)+abs(y.second-n/2);if(x_dist==y_dist) return atan2(x.second-n/2,x.first-n/2) < atan2(y.second-n/2,y.first-n/2);return x_dist>y_dist;});for(auto e:tmp){que.push(e);}}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]+(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<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]+(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<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(i>=0 && i<m);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));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--;}//爆弾を使ったときに壊れる建物の数,壊れる店の数,center_shopが壊れるかどうかを返すtuple<int,int,bool> use_simulate(int i,int x,int y){assert(i>=0 && i<m);int broken_building = 0;int broken_shop = 0;bool broken_center_shop = false;for(int j=0;j<l[i];j++){int broken_x = x+a[i][j];int broken_y = y+b[i][j];if(!is_valid(broken_x,broken_y)) continue;if(A[broken_x][broken_y]=='.') continue;if(A[broken_x][broken_y]=='@'){broken_shop++;if(broken_x==center_shop_x && broken_y==center_shop_y){broken_center_shop = true;}}broken_building++;}return make_tuple(broken_building,broken_shop,broken_center_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(A[i][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(A[i][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 one_step(){double best_eval = (double)INF+1;int best_i,best_j,best_k;while(best_eval>=(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<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; */}//爆破場所を決め打ちして1手進めるvoid one_step2(){int i,j;while(!que.empty()){tie(i,j) = que.front();que.pop();if(A[i][j]!='.') break;}if(A[i][j]=='.') return;double best_eval = (double)INF+1;int best_k,best_t;while(best_eval>=(double)INF){int max_iter = 1000;for(int iter=0;iter<max_iter;iter++){//爆弾の種類とどの爆風で破壊するか決めるint k,t,explode_x,explode_y;do{k = randInt(0,m-1);t = randInt(0,l[k]);//爆破場所explode_x = i-a[k][t];explode_y = j-b[k][t];}while(!is_valid(explode_x,explode_y));//爆破したらどうなるかint broken_building;int broken_shop;bool center_shop_broken;tie(broken_building,broken_shop,center_shop_broken) = use_simulate(k,explode_x,explode_y);if(broken_building==0) continue;//コストシミュレーションauto shop_pos = nearest_shop(explode_x,explode_y);int use_cost = 0;//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,explode_x,explode_y).first;double eval = eval_func(use_cost,broken_building,broken_shop,center_shop_broken);if(chmin(best_eval,eval)){best_k = k;best_t = t;}}}int best_explode_x = i-a[best_k][best_t];int best_explode_y = j-b[best_k][best_t];auto shop_pos = nearest_shop(best_explode_x,best_explode_y);move(shop_pos.first,shop_pos.second);buy(best_k);move(best_explode_x,best_explode_y);use(best_k);}//爆破場所と爆弾の種類を受け取ってその通り進める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,center_shop_broken] = 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);}}}void plan_exec(vector<tuple<int,int,int>> prior_plan, vector<tuple<int,int,int>> 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<<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];//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<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(){/* Bombplan bombplan(A);bombplan.greedy_all();cerr<<"cost:"<<bombplan.cost<<endl; */sa();}void sa(){Bombplan bombplan(A);bombplan.greedy_all();auto [prior_plan,remain_plan] = bombplan.explode_list();vector<tuple<int,int,int>> 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_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 LOCALcerr<<"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 LOCALcerr<<"total_cost:"<<pre_score<<endl;cerr<<"buy_cost:"<<best_state.buy_cost<<endl;cerr<<"move_cost:"<<best_state.move_cost<<endl;#endifbest_state.output();}};int main(){start_time = get_time();Solve solve;solve.IN();solve.solve();#ifdef LOCALcerr<<"time:"<<get_time()-start_time<<"ms\n";#endif}