結果
| 問題 |
No.5019 Hakai Project
|
| コンテスト | |
| ユーザー |
 ぴぃいいいい
|
| 提出日時 | 2023-11-19 00:24:04 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 16,864 bytes |
| コンパイル時間 | 4,636 ms |
| コンパイル使用メモリ | 312,548 KB |
| 実行使用メモリ | 10,644 KB |
| スコア | 48,538,976 |
| 最終ジャッジ日時 | 2023-11-19 00:24:20 |
| 合計ジャッジ時間 | 14,680 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 TLE * 1 -- * 48 |
コンパイルメッセージ
main.cpp: In member function 'void State::one_step2()':
main.cpp:407:18: warning: 'j' may be used uninitialized [-Wmaybe-uninitialized]
407 | if(A[i][j]=='.') return;
| ^
main.cpp:400:15: note: 'j' was declared here
400 | int i,j;
| ^
main.cpp:407:15: warning: 'i' may be used uninitialized [-Wmaybe-uninitialized]
407 | if(A[i][j]=='.') return;
| ^
main.cpp:400:13: note: 'i' was declared here
400 | int i,j;
| ^
ソースコード
#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;
int c[20],l[20];
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;
vector<vector<tuple<int,int,int>>> plan;
Bombplan(){}
Bombplan(vector<vector<char>> AA):A(AA){
plan.resize(n,vector<tuple<int,int,int>>(n));
greedy_all();
}
//a[i][j]の爆破方法をランダムに決める
void random_generate(int i,int j){
if(A[i][j]=='.') return;
int k,x;
do{
k = randInt(0,m-1);
x = randInt(0,l[k]);
}while(!is_valid(i-a[k][x],j-b[k][x]));
plan[i][j] = make_tuple(k,i-a[k][x],j-b[k][x]);
}
//すべての位置の爆破方法をランダムに決める
void random_all(){
for(int i=0;i<n;i++)for(int j=0;j<n;j++) random_generate(i,j);
}
//すべての位置の爆破方法をgreedyに決める
void greedy_all(){
vector<vector<char>> AA = A;
int building = 0;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(AA[i][j]=='.') continue;
building++;
}
while(building>0){
int best_i,best_j,best_k;
double best = (double)INF;
for(int iter=0;iter<10000;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;
}
}
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--;
plan[broken_x][broken_y] = make_tuple(best_k,best_i,best_j);
}
}
}
//ランダムな一か所の爆破方法を変更する
void random_trans_plan(){
int i,j;
do{
i = randInt(0,n-1);
j = randInt(0,n-1);
}while(A[i][j]=='.');
random_generate(i,j);
compress(i,j);
}
void compress(int i,int j){
if(A[i][j]=='.') return;
auto [k,x,y] = plan[i][j];
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;
plan[broken_x][broken_y] = plan[i][j];
}
}
void compress_all(){
vector<vector<bool>> dicided(n,vector<bool>(n));
vector<pii> que;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(A[i][j]=='.') continue;
que.push_back(make_pair(i,j));
}
//queを真ん中からの距離で並び替え
sort(all(que),[](pii a,pii b){
return abs(a.first-n/2)+abs(a.second-n/2) < abs(b.first-n/2)+abs(b.second-n/2);
});
//queを順番に見ていく
//queの中でまだ決まっていない建物を見つけて確定させる
for(auto [i,j]:que){
if(dicided[i][j]) continue;
auto [k,x,y] = plan[i][j];
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;
if(dicided[broken_x][broken_y]) continue;
dicided[broken_x][broken_y] = true;
plan[broken_x][broken_y] = make_tuple(k,x,y);
}
}
}
set<tuple<int,int,int>> explode_list(){
set<tuple<int,int,int>> res;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(A[i][j]=='.') continue;
res.insert(plan[i][j]);
}
return res;
}
double eval(){
Bombplan bombplan = *this;
double res = 0;
bombplan.compress_all();
auto bombplan_explode_list = bombplan.explode_list();
for(auto [k,x,y]:bombplan_explode_list){
res += c[k];
}
return res;
}
//出力
void output(){
auto res = explode_list();
for(auto [k,x,y]:res){
cerr<<x<<" "<<y<<" "<<k<<endl;
}
}
};
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;
queue<pii> que;
State(){}
State(vector<vector<char>> AA):A(AA){
bomb.resize(m);
vpii tmp;
int min_center_dist = inf;
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++;
if(chmin(min_center_dist,abs(i-n/2)+abs(j-n/2))){
center_shop_x = i;
center_shop_y = j;
}
}
}
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);
}
}
//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;
}
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(){
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;
}
//爆破場所を決め打ちして1手進める
void one_step2(){
int MAX_QUERY = 4;
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;
State best_state;
while(best_eval>=(double)INF){
int max_iter = (2500-building);
for(int iter=0;iter<max_iter;iter++){
State state = *this;
//爆弾の種類とどの爆風で破壊するか決める
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));
//実行する
auto shop_pos = nearest_shop(explode_x,explode_y);
state.move(shop_pos);
state.buy(k);
state.move(explode_x,explode_y);
state.use(k);
double eval = diff_eval(*this,state);
if(chmin(best_eval,eval)){
best_state = state;
}
}
}
*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;
Bombplan best_plan;
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_step2();
cerr<<state.building<<" "<<state.shop<<" "<<state.cost<<endl;
}
state.output();
}
void sa(){
Bombplan bombplan(A);
double start_temp = 1;
double end_tmp = 1;
double start = get_time();
cerr<<"start_sa\n";
int iter=0;
int trans_cnt = 0;
while(true){
iter++;
double now_time = get_time();
if(now_time-start>1900) break;
Bombplan new_bombplan = bombplan;
new_bombplan.random_trans_plan();
int pre_score = bombplan.eval();
int new_score = new_bombplan.eval();
//温度関数
double temp = start_temp + (end_tmp-start_temp)*(now_time-start)/1900;
//遷移確率関数
double prob = exp((pre_score-new_score)/temp);
//遷移回数
if(prob>randDouble(0,1)){
//遷移
bombplan = new_bombplan;
trans_cnt++;
if(iter%500==1){
cerr<<"iter:"<<iter<<endl;
cerr<<"trans_cnt:"<<trans_cnt<<endl;
cerr<<"time:"<<now_time-start<<"ms\n";
cerr<<"score:"<<new_score<<endl;
}
}
else{
if(iter%500==1){
cerr<<"iter:"<<iter<<endl;
cerr<<"trans_cnt:"<<trans_cnt<<endl;
cerr<<"time:"<<now_time-start<<"ms\n";
cerr<<"score:"<<pre_score<<endl;
}
}
}
best_plan = bombplan;
}
};
int main(){
start_time = get_time();
Solve solve;
solve.IN();
solve.solve();
cerr<<"time:"<<get_time()-start_time<<"ms\n";
}