結果
問題 | No.5019 Hakai Project |
ユーザー |
![]() |
提出日時 | 2023-11-23 22:39:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
コンパイルメッセージ
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; | ^~~~~~
ソースコード
#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_DEBUGcerr<<"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_DEBUGcerr<<"greedy_all() header end"<<endl;#endifwhile(building>0){#ifdef LOG_DEBUGcerr<<"simulation building is "<<building<<endl;#endifint best_i,best_j,best_k;double best = (double)INF;//ランダムに爆発位置と種類を選ぶ#ifdef LOG_DEBUGint skip_zero = 0;#endiffor(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_cntint diff_bit = n*(i-20) + (j-20);int broken_cnt = (explode_wind(k,i,j) & (~is_broken)).count();if(broken_cnt==0){#ifdef LOG_DEBUGskip_zero++;#endifcontinue;}double tmp = (double)c[k]/(double)(broken_cnt);if(chmin(best,tmp)){best_i = i;best_j = j;best_k = k;#ifdef LOG_DEBUGcerr<<"update broken_cnt is "<<broken_cnt<<endl;#endif}}#ifdef LOG_DEBUGcerr<<"skip_zero is "<<skip_zero<<endl;#endif//bestなものを選ぶexplodes.insert(make_tuple(best_k,best_i,best_j));#ifdef LOG_DEBUGcerr<<"accepted is "<<(tmpran & (~is_broken)).count()<<endl;#endifis_broken |= explode_wind(best_k,best_i,best_j);is_shop &= ~is_broken;building = 2500 - is_broken.count();}#ifdef LOG_DEBUGcerr<<"simulation end"<<endl;cerr<<"greedy_all() end"<<endl;#endifupdate_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 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}