/* TODO: */ //#define NDEBUG //#define ONLINE_JUDGE #ifndef ONLINE_JUDGE //#define OPTUNA #endif #ifdef ONLINE_JUDGE #define NDEBUG #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include using namespace std; using ll=long long int; //using Int=__int128; #define mask(x) ((1LL< bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;} template bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;} template int bitUP(T x,int a){return (x>>a)&1;} enum Dir{ Right, Down, Left, Up }; //→ ↓ ← ↑ int dh[4]={0,1,0,-1}, dw[4]={1,0,-1,0}; //上から時計回り //int dx[8]={0,1,1,1,0,-1,-1,-1}, dy[8]={1,1,0,-1,-1,-1,0,1}; long double EPS = 1e-6; const ll INF=(1LL<<62); const int MAX=(1<<30); using pii=pair; using pil=pair; using pli=pair; using pll=pair; using psi=pair; using pis=pair; using psl=pair; using pls=pair; using pss=pair; template using minimum_queue=priority_queue,greater>; using Graph=vector>; using i8=int8_t; using i16=int16_t; using i32=int32_t; using i64=int64_t; using u8=uint8_t; using u16=uint16_t; using u32=uint32_t; using u64=uint64_t; void FastIO(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); } //0-indexed vector cin template inline istream &operator>>(istream &is,vector &v) { for(size_t i=0;i>v[i]; return is; } //0-indexed vector cin template inline istream &operator>>(istream &is,vector> &v) { for(size_t i=0;i>v[i]; } return is; } struct Xor32{ using u32=uint32_t; u32 x=1234567; inline u32 rnd_make(){ x^=(x<<13); x^=(x>>17); x^=(x<<5); return x; } inline u32 operator()(){ return rnd_make(); } //[a,b) inline int operator()(int a,int b){ int dis=b-a; int add=rnd_make()%dis; return a+add; } //[0,b) inline int operator()(int b){ return rnd_make()%b; } //http://web.archive.org/web/20200105011004/https://topcoder.g.hatena.ne.jp/tomerun/20171216/ //[0,b)の中から異なる2つを選ぶ [0]の値<[1]の値 inline array two(int b){ assert(b>=2); int v1=rnd_make()%b; int v2=rnd_make()%(b-1); if (v2>=v1) return {v1,v2+1}; else return {v2,v1}; } inline float random01(){ return float(rnd_make())/mask(32); } inline double random_double(double a,double b){ double sa=b-a; a+=random01()*sa; return a; } //確率pでtrueを返す inline bool gen_bool(float p){ return p>random01(); } }; struct Xor64{ u64 x=1234567; inline u64 rnd_make(){ x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; } inline u64 operator()(){ return rnd_make(); } }; struct Timer{ chrono::high_resolution_clock::time_point st; float local; Timer(){ #ifndef ONLINE_JUDGE local=1.0; #endif start(); } void start(){ st=chrono::high_resolution_clock::now(); } int span()const{ auto now=chrono::high_resolution_clock::now(); return chrono::duration_cast(now-st).count(); } }; struct TestTimer{ chrono::high_resolution_clock::time_point st; unordered_map sum_time; unordered_map start_time; TestTimer(){} void start(const string &s){ #ifndef ONLINE_JUDGE start_time[s]=chrono::high_resolution_clock::now(); #endif } void end(const string &s){ #ifndef ONLINE_JUDGE auto now=chrono::high_resolution_clock::now(); sum_time[s]+=chrono::duration_cast(now-start_time[s]).count(); #endif } void output()const{ #ifndef ONLINE_JUDGE for(auto m:sum_time){ cerr< cnt; TestCounter(){} void count(const string &s){ #ifndef ONLINE_JUDGE cnt[s]++; #endif } void output()const{ #ifndef ONLINE_JUDGE for(auto m:cnt){ cerr< class DynamicArray{ public: array array_={}; int size_=0; DynamicArray(){} DynamicArray(int n){ resize(n); } void push_back(const T &e){ array_[size_++]=e; } void pop_back(){ size_--; } inline T& operator[](int index){ return array_[index]; } inline const T& operator[](int index) const { return array_[index]; } inline int size()const{ return size_; } inline T& back(){ return array_[size_-1]; } inline auto begin() -> decltype(array_.begin()) { return array_.begin(); } inline auto end() -> decltype(array_.begin()) { return array_.begin() + size_; } inline auto begin() const -> decltype(array_.begin()) { return array_.begin(); } inline auto end() const -> decltype(array_.begin()) { return array_.begin() + size_; } inline void resize(int new_size){ size_=new_size; } void operator=(const DynamicArray &e){ for(int i=0;i inline void vsort(vector &v){ sort(v.begin(),v.end()); } //逆順ソート template inline void rvsort(vector &v){ sort(v.rbegin(),v.rend()); } //1ビットの数を返す inline int popcount(int x){ return __builtin_popcount(x); } //1ビットの数を返す inline int popcount(ll x){ return __builtin_popcountll(x); } template inline void Compress(vector &C){ sort(C.begin(),C.end()); C.erase(unique(C.begin(),C.end()),C.end()); } //要素数n 初期値x template inline vector vmake(size_t n,T x){ return vector(n,x); } //a,b,c,x data[a][b][c] 初期値x template auto vmake(size_t n,Args... args){ auto v=vmake(args...); return vector(n,move(v)); } //vは昇順 bool is_in(const vector &v,int x){ int n=v.size(); if(n==0) return false; int ng=-1,ok=n-1; while(ok-ng!=1){ int mid=(ok+ng)/2; if(v[mid] struct edge { int to; T cost; int id; edge()=default; edge(int to, T cost,int id) : to(to), cost(cost), id(id) {} }; template struct Edge { int from, to,id; T cost; Edge(int from,int to,T cost,int id):from(from),to(to),cost(cost),id(id){} Edge()=default; bool operator<(const Edge &e){ return cost &e){ return cost<=e.cost; } }; template using WeightGraph=vector>>; //vector cout template inline ostream &operator<<(ostream &os,const vector &v) { bool sp=true; if(string(typeid(T).name())=="c") sp=false; for(size_t i=0;i cout template inline ostream &operator<<(ostream &os,const vector> &v) { for(size_t i=0;i inline ostream &operator<<(ostream &os,const pair &p) { os< inline ostream &operator<<(ostream &os,const map &M) { bool first=false; for(auto x:M){ if(first) os< inline ostream &operator<<(ostream &os,const set &S) { bool first=false; for(auto x:S){ if(first) os< inline istream &operator>>(istream &is,pair &p) { is>>p.first>>p.second; return is; } template void append(vector &v,const vector &vp){ for(auto p:vp){ v.push_back(p); } } //Fisher–Yatesアルゴリズム template void shuffle(vector &v){ int sz=v.size(); for(int i=sz-1;i>0;i--){ swap(v[Rand32()%(i+1)],v[i]); } } //[0,n)の集合を管理 //値の追加・削除・存在確認: O(1) //空間計算量: O(n) //重複は許さない //https://topcoder-tomerun.hatenablog.jp/entry/2021/06/12/134643 template struct IntSet{ DynamicArray set_; array pos_; IntSet(){ for(int i=0;i T linear_function(U x,U start_x,U end_x,T start_value,T end_value){ if(x>=end_x) return end_value; if(x<=start_x) return start_value; return start_value+(end_value-start_value)*(x-start_x)/(end_x-start_x); } //http://gasin.hatenadiary.jp/entry/2019/09/03/162613 struct SimulatedAnnealing{ float startTemp; //差の最大値(あくまでも参考) float endTemp; //差の最小値(あくまでも参考) float startTime; float endTime; bool yama; bool minimum; //SimulatedAnnealing(){} SimulatedAnnealing(float startTemp,float endTemp,float startTime,float endTime,bool yama,bool minimum): startTemp(startTemp),endTemp(endTemp),startTime(startTime),endTime(endTime),yama(yama),minimum(minimum){ } float calc_temp(){ return linear_function(float(TIME.span()),startTime,endTime,startTemp,endTemp); //線形 //https://atcoder.jp/contests/ahc014/submissions/35326979 /*float progress=(TIME.span()-startTime)/(endTime-startTime); if(progress>1.0) progress=1.0; return pow(startTemp,1.0-progress)*pow(endTemp,progress);*/ } float calc_prob(float diff){ if(minimum) diff*=-1; if(diff>0) return 1; float temp=calc_temp(); return exp(diff/temp); } float calc_diff(float prob){ float diff=log(prob)*calc_temp(); if(minimum) diff*=-1; return diff; } inline bool operator()(float diff){ testCounter.count("try_cnt"); if(minimum) diff*=-1; if(diff>0){ testCounter.count("plus_change"); return true; } if(yama) return false; float prob; if(minimum) prob=calc_prob(diff*-1); else prob=calc_prob(diff); if(prob>float(Rand32()&mask(30))/mask(30)){ testCounter.count("minus_change"); return true; } else return false; } }; ///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //https://atcoder.jp/contests/asprocon9/submissions/34659956 #ifndef OPTUNA #define REGIST_PARAM(name, type, defaultValue) constexpr type name = defaultValue #else #define REGIST_PARAM(name, type, defaultValue) type name = defaultValue #endif namespace OP{ REGIST_PARAM(yama,bool,false); REGIST_PARAM(startTemp,double,500000); REGIST_PARAM(endTemp,float,0); REGIST_PARAM(TIME_END,int,1900); }; constexpr int Height=50; constexpr int Width=50; vector ans; struct Place{ int h,w; Place(){} Place(int h,int w):h(h),w(w){ } Place(int idx):h(idx/Width),w(idx%Width){ } int dist(const Place &np)const{ return abs(np.h-h)+abs(np.w-w); } Place pre_place(int dir){ return Place(h-dh[dir],w-dw[dir]); } Place next_place(int dir){ return Place(h+dh[dir],w+dw[dir]); } void move(int dir){ h+=dh[dir]; w+=dw[dir]; } void remove(int dir){ h-=dh[dir]; w-=dw[dir]; } bool ok_move(int dir){ return h+dh[dir]=0 and w+dw[dir]>=0; } bool out_grid(){ return h>=Height or w>=Width or h<0 or w<0; } bool operator==(const Place &p){ return h==p.h and w==p.w; } bool operator!=(const Place &p){ return h!=p.h or w!=p.w; } int idx(){ return h*Width+w; } int id(){ return idx(); } //上下 左右 bool operator<(Place &p){ if(p.h!=h) return h>(istream& is, Place& p){ is>>p.h>>p.w; return is; } friend ostream& operator<<(ostream& os, Place& p){ os< struct GridDistance{ using pti=pair; int Height; int Width; vector> cost_grid; GridDistance(int Height,int Width):Height(Height),Width(Width){ cost_grid=vmake(Height,Width,Cost()); } void set_cost(int h,int w,Cost cost){ cost_grid[h][w]=cost; } vector dijkstra(Place start){ vector dist(Height*Width,numeric_limits::max()); priority_queue,greater> que; dist[start.id()]=0; que.emplace(dist[start.id()],start.id()); while(que.size()){ Place now_place; Cost now_cost; tie(now_cost,now_place)=que.top(); que.pop(); if(now_cost>dist[now_place.id()]) continue; for(int dir=0;dir<4;dir++){ auto next_place=now_place.next_place(dir); if(next_place.out_grid()) continue; Cost next_cost=dist[now_place.id()]+cost_grid[next_place.h][next_place.w]; if(chmin(dist[next_place.id()],next_cost)){ que.emplace(next_cost,next_place.id()); } } } return dist; } pair> query_path(Place start,Place goal){ auto dist=dijkstra(start); vector path; auto now_place=goal; path.push_back(now_place); while(now_place!=start){ for(int dir=0;dir<4;dir++){ auto np=now_place.next_place(dir); if(np.out_grid()) continue; if(dist[np.id()]+cost_grid[now_place.h][now_place.w]==dist[now_place.id()]){ now_place=np; break; } } path.push_back(now_place); } reverse(path.begin(),path.end()); vector path_dir; for(int i=0;i+1 Distance(Height,Width); Place find_nearest(const Place &p,const vector &ps,bool easy=true){ int distance=MAX; Place nearest; for(auto np:ps){ int dist; if(easy) dist=p.dist(np); else dist=Distance.query_path(p,np).first; if(chmin(distance,dist)){ nearest=np; } } return nearest; } template pair find_nearest(Place &p,vector> &ps,bool easy=true){ int distance=MAX; pair nearest; for(auto np:ps){ int dist; if(easy) dist=p.dist(np.first); else dist=Distance.query_path(p,np.first).first; if(chmin(distance,dist)){ nearest=np; } } return nearest; } void output_move(Place &start,Place goal){ auto path_dir=Distance.query_path(start,goal).second; start=goal; for(int dir:path_dir){ string s="1 "; string c="U"; if(dir==0) c="R"; if(dir==1) c="D"; if(dir==2) c="L"; s+=c; ans.push_back(s); } } struct Bomb{ int cost; vector ps; }; constexpr int num_bomb=20; auto map_input=vmake(Height,Width,'.'); vector bombs(num_bomb); void input(){ int dummy; cin>>dummy>>dummy; for(int h=0;h>map_input[h][w]; } for(int b=0;b>bombs[b].cost; int size; cin>>size; bombs[b].ps.resize(size); cin>>bombs[b].ps; } } //https://www.sciencedirect.com/science/article/pii/0305054881900174 //AlgorithmA 一番コスパが高いものを選ぶ貪欲 //TODO:https://scmopt.github.io/opt100/74scp.html を参考にしてもっと書く(weightedがついてないけど重み付きっぽい) template struct SetCovering{ struct Set{ Name name; Cost cost; vector elements; }; int num_element; vector sets; SetCovering(int num_element):num_element(num_element){ } void add_set(Name name,Cost cost,vector elements){ sets.push_back({name,cost,elements}); } vector> make_sets_contain(){ vector> sets_contain(num_element); int id=0; for(auto &set:sets){ for(int element:set.elements){ sets_contain[element].push_back(id); } id++; } return sets_contain; } //k(出力する解のサイズ) N(setの数) //O(Nk+要素数の合計) //[1,rate]倍する pair,Cost> greedy(double rate=1){ int num_set=sets.size(); vector is_covered(num_element,false); auto sets_contain=make_sets_contain(); vector num_uncovered(num_set); for(int s=0;s ans; Cost cost_sum=0; while(true){ //一番コスパ(num_uncovered/cost)が高いものを選ぶ int id_best=-1; double costper_best=-1; for(int i=0;i,Cost> greedy_random(int loop,double rate){ Cost best_cost; vector best_names; tie(best_names,best_cost)=greedy(1); for(int i=0;i names; tie(names,cost)=greedy(rate); if(chmin(best_cost,cost)){ best_names=names; } } return {best_names,best_cost}; } }; /* 店は最後に爆破する */ void solve(){ input(); //set coveringのインスタンスを作る auto id_map=vmake(Height,Width,-1); vector place_shops; int num_hakai=0; Place center_shop; { int min_center_dist=10000; int id=0; for(int h=0;h; SetCovering SC(num_hakai); for(int ph=0;ph ids; bool ok=true; for(auto dp:bombs[b].ps){ auto np=p; np.move(dp); if(np==center_shop){ ok=false; } if(np.out_grid() or id_map[np.h][np.w]==-1){ continue; } ids.push_back(id_map[np.h][np.w]); } if(not ok) continue; SC.add_set(pPi(p,b),bombs[b].cost+4*dist*2,ids); } } } auto names=SC.greedy_random(10,1.01).first; Place place_now(0,0); while(names.size()){ //次のターゲット pPi name_nearest=find_nearest(place_now,names); //一番近くの店に行って必要な爆弾を買う Place nearest_shop=find_nearest(place_now,place_shops); output_move(place_now,nearest_shop); ans.push_back("2 "+to_string(name_nearest.second+1)); //ターゲットのところに行って爆弾を落とす output_move(place_now,name_nearest.first); ans.push_back("3 "+to_string(name_nearest.second+1)); //ターゲットを消す for(int i=0;i next_place_shops; for(auto shop:place_shops){ bool hakai=false; for(auto dp:bombs[name_nearest.second].ps){ auto np=place_now; np.move(dp); if(shop==np) hakai=true; } if(not hakai) next_place_shops.push_back(shop); } for(auto dp:bombs[name_nearest.second].ps){ auto np=place_now; np.move(dp); if(np.out_grid()) continue; if(Distance.cost_grid[np.h][np.w]==2){ Distance.set_cost(np.h,np.w,1); } } place_shops=next_place_shops; } cerr<<-1< next_place_shops; for(auto shop:place_shops){ bool hakai=false; for(auto dp:bombs[cheapest_bomb].ps){ auto np=nearest_shop; np.move(dp); if(shop==np) hakai=true; } if(not hakai) next_place_shops.push_back(shop); } place_shops=next_place_shops; } cout<>T; while(T--) solve(); }