結果

問題 No.5019 Hakai Project
ユーザー bin101
提出日時 2023-11-17 15:35:55
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 266 ms / 3,000 ms
コード長 21,176 bytes
コンパイル時間 5,194 ms
コンパイル使用メモリ 267,684 KB
実行使用メモリ 74,616 KB
スコア 162,831,140
最終ジャッジ日時 2023-11-17 15:36:17
合計ジャッジ時間 21,862 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
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<bits/stdc++.h>
using namespace std;
using ll=long long int;
//using Int=__int128;
#define mask(x) ((1LL<<x)-1)
#define ALL(A) A.begin(),A.end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
template<typename T> 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<int,int>;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using psi=pair<string,int>;
using pis=pair<int,string>;
using psl=pair<string,ll>;
using pls=pair<ll,string>;
using pss=pair<string,string>;
template<class T>
using minimum_queue=priority_queue<T,vector<T>,greater<T>>;
using Graph=vector<vector<int>>;
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<typename T>
inline istream &operator>>(istream &is,vector<T> &v) {
    for(size_t i=0;i<v.size();i++) is>>v[i];
    return is;
}
 
//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<vector<T>> &v) {
    for(size_t i=0;i<v.size();i++){
        is>>v[i];
    }
    return is;
}
struct Xor32{
    using u32=uint32_t;
 
    u32 x=1234567;
    inline u32 rnd_make(){
        x^=(x<<13);
        x=x^(x>>17);
        return x=x^(x<<5);
    }
    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つを選ぶ first<second
    inline pair<int,int> 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};
    }
};
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<chrono::milliseconds>(now-st).count();
    }
};
struct TestTimer{
    chrono::high_resolution_clock::time_point st;
    unordered_map<string,ll> sum_time;
    unordered_map<string,chrono::high_resolution_clock::time_point> 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<chrono::nanoseconds>(now-start_time[s]).count();
#endif
    }
    void output()const{
#ifndef ONLINE_JUDGE
        for(auto m:sum_time){
            cerr<<m.first<<": "<<m.second/1e6<<"ms"<<endl;
        }
#endif
    }
};
struct TestCounter{
    unordered_map<string,ll> cnt;
    TestCounter(){}
    void count(const string &s){
#ifndef ONLINE_JUDGE
        cnt[s]++;
#endif
    }
    void output()const{
#ifndef ONLINE_JUDGE
        for(auto m:cnt){
            cerr<<m.first<<": "<<m.second<<endl;
        }
#endif
    }    
};
Timer TIME;
Xor32 Rand32;
Xor64 Rand64;
TestTimer testTimer;
TestCounter testCounter;
//https://atcoder.jp/contests/asprocon9/submissions/34659956
template<class T,int CAPACITY>
class DynamicArray{
public:
    array<T,CAPACITY> 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<e.size_;i++){
            array_[i]=e[i];
        }
        size_=e.size_;
    }
    void clear(){
        size_=0;
    }
    //O(1)
    //末尾と入れ替える。順序が保持されないが高速
    void swap_remove(int idx){
        array_[idx]=array_[size_-1];
        size_--;
    }
    //O(size)
    //順序を気にしない場合、swap_removeの方がいい
    void remove(int idx){
        for(int i=idx;i<size_-1;i++){
            array_[i]=array_[i+1];
        }
        size_--;
    }
    void fill(T x){
        for(int i=0;i<size_;i++){
            array_[i]=x;
        }
    }
};
//ソート
template<typename T>
inline void vsort(vector<T> &v){
    sort(v.begin(),v.end());
}
//逆順ソート
template<typename T>
inline void rvsort(vector<T> &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<typename T>
inline void Compress(vector<T> &C){
    sort(C.begin(),C.end());
    C.erase(unique(C.begin(),C.end()),C.end());
}
//要素数n 初期値x
template<typename T>
inline vector<T> vmake(size_t n,T x){
    return vector<T>(n,x);
}
//a,b,c,x data[a][b][c] 初期値x
template<typename... Args>
auto vmake(size_t n,Args... args){
    auto v=vmake(args...);
    return vector<decltype(v)>(n,move(v));
}
//vは昇順
bool is_in(const vector<int> &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]<x) ng=mid;
        else ok=mid;
    }
    if(v[ok]==x) return true;
    return false;
}
template<typename T >
struct edge {
    int to;
    T cost;
    int id;
    edge()=default;
    edge(int to, T cost,int id) : to(to), cost(cost), id(id) {}
};
template<class T >
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<T> &e){
        return cost<e.cost;
    }
    bool operator<=(const Edge<T> &e){
        return cost<=e.cost;
    }
};
template<typename T>
using WeightGraph=vector<vector<edge<T>>>;
//vector cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<T> &v) {
    bool sp=true;
    if(string(typeid(T).name())=="c") sp=false;
    for(size_t i=0;i<v.size();i++){
        if(i and sp) os<<" ";
        os<<v[i];
    }
    return os;
}
//vector<vector> cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<vector<T>> &v) {
    for(size_t i=0;i<v.size();i++){
        os<<v[i];
        if(i+1!=v.size()) os<<"\n";
    }
    return os;
}
//pair cout
template<typename T, typename U>
inline ostream &operator<<(ostream &os,const pair<T,U> &p) {
    os<<p.first<<" "<<p.second;
    return os;
}
//map cout
template<typename F, typename S>
inline ostream &operator<<(ostream &os,const map<F,S> &M) {
    bool first=false;
    for(auto x:M){
        if(first) os<<endl;
        first=true;
        os<<x;
    }
    return os;
}
//set cout
template<typename T>
inline ostream &operator<<(ostream &os,const set<T> &S) {
    bool first=false;
    for(auto x:S){
        if(first) os<<endl;
        first=true;
        os<<x;
    }
    return os;
}
 
//pair cin
template<typename T, typename U>
inline istream &operator>>(istream &is,pair<T,U> &p) {
    is>>p.first>>p.second;
    return is;
}
template<typename T>
void append(vector<T> &v,const vector<T> &vp){
    for(auto p:vp){
        v.push_back(p);
    }
}
//Fisher–Yatesアルゴリズム
template<typename T>
void shuffle(vector<T> &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<int CAPACITY>
struct IntSet{
    DynamicArray<int,CAPACITY> set_;
    array<int,CAPACITY> pos_;
    IntSet(){
        for(int i=0;i<CAPACITY;i++){
            pos_[i]=-1;
        }
        set_.clear();
    }
    void insert(int v){
        //assert(pos_[v]==-1);
        if(pos_[v]!=-1) return;
        pos_[v]=set_.size();
        set_.push_back(v);
    }
    void remove(int v){
        assert(pos_[v]!=-1);
        int last=set_[set_.size()-1];
        set_[pos_[v]]=last;
        pos_[last]=pos_[v];
        set_.pop_back();
        pos_[v]=-1;
    }
    bool contains(int v)const{
        return pos_[v]!=-1;
    }
    int size()const{
        return set_.size();
    }
    int random()const{
        assert(set_.size());
        int x=set_[Rand32(set_.size())];
        assert(pos_[x]!=-1);
        return x;
    }
    int random_extract(){
        int v=set_[Rand32(set_.size())];
        remove(v);
        return v;
    }
    void clear(){
        while(size()){
            remove(set_.back());
        }
    }
};
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
template<class T,class U>
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<string> 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){
        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]<Height and w+dw[dir]<Width and 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;
    }
    //上下 左右
    bool operator<(Place &p){
        if(p.h!=h) return h<p.h;
        return w<p.w;
    }
    friend istream& operator>>(istream& is, Place& p){
        is>>p.h>>p.w;
        return is;
    }
    friend ostream& operator<<(ostream& os, Place& p){
        os<<p.h<<" "<<p.w;
        return os;
    }
    void move(Place p){
        h+=p.h;
        w+=p.w;
    }
    Place find_nearest(const vector<Place> &ps){
        int distance=MAX;
        Place nearest;
        for(auto p:ps){
            if(chmin(distance,dist(p))){
                nearest=p;
            }
        }
        return nearest;
    }
    template<class T>
    pair<Place,T> find_nearest(const vector<pair<Place,T>> &ps){
        int distance=MAX;
        pair<Place,T> nearest;
        for(auto p:ps){
            if(chmin(distance,dist(p.first))){
                nearest=p;
            }
        }
        return nearest;
    }
    void output_move(Place p){
        
        while(dist(p)){
            int now_dist=dist(p);
            for(int dir=0;dir<4;dir++){
                move(dir);
                int next_dist=dist(p);
                if(next_dist<now_dist){
                    string c="U";
                    if(dir==0) c="R";
                    if(dir==1) c="D";
                    if(dir==2) c="L";
                    ans.push_back("1 "+c);
                    break;
                }
                remove(dir);
            }
        }
    }
};
struct Bomb{
    int cost;
    vector<Place> ps;
};
constexpr int num_bomb=20;
auto map_input=vmake(Height,Width,'.');
vector<Bomb> bombs(num_bomb);
void input(){
    int dummy;
    cin>>dummy>>dummy;
    for(int h=0;h<Height;h++) for(int w=0;w<Width;w++){
        cin>>map_input[h][w];
    }
    for(int b=0;b<num_bomb;b++){
        cin>>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<class Name,class Cost>
struct SetCovering{
    struct Set{
        Name name;
        Cost cost;
        vector<int> elements;
    };
    int num_element;
    vector<Set> sets;
    SetCovering(int num_element):num_element(num_element){
    }
    void add_set(Name name,Cost cost,vector<int> elements){
        sets.push_back({name,cost,elements});
    }
    vector<vector<int>> make_sets_contain(){
        vector<vector<int>> 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+要素数の合計)
    vector<Name> solve_greedy(){
        int num_set=sets.size();
        vector<bool> is_covered(num_element,false);
        auto sets_contain=make_sets_contain();
        vector<int> num_uncovered(num_set);
        for(int s=0;s<num_set;s++){
            num_uncovered[s]=sets[s].elements.size();
        }
        vector<Name> ans;
        Cost cost_sum=0;
        while(true){
            //一番コスパ(num_uncovered/cost)が高いものを選ぶ
            int id_best=-1;
            double costper_best=-1;
            for(int i=0;i<num_set;i++){
                if(num_uncovered[i]==0) continue;
                if(chmax(costper_best,double(num_uncovered[i])/sets[i].cost)){
                    id_best=i;
                }
            }
            if(id_best==-1){
                //すべてのelementをカバーした
                break;
            }
            ans.push_back(sets[id_best].name);
            cost_sum+=sets[id_best].cost;
            //num_uncoveredとis_coveredを更新
            for(int element:sets[id_best].elements){
                if(is_covered[element]) continue;
                is_covered[element]=true;
                //cerr<<sets_contain.size()<<endl;
                for(int id_set:sets_contain[element]){
                    num_uncovered[id_set]--;
                }
            }
        }
        for(int i=0;i<num_element;i++){
            if(is_covered[i]) continue;
            cerr<<"uncovered: "<<i<<endl;
        }
        cerr<<"cost_sum: "<<cost_sum<<endl;
        return ans;
    }
};
//setの数が2500*20=5e4
//elementの数が2500*0.8=2000
//高々次数は1600
//どう考えても普通に貪欲したほうが強い
void solve(){
    input();
//set coveringのインスタンスを作る
    auto id_map=vmake(Height,Width,-1);
    vector<Place> place_shops;
    int num_hakai=0;
{
    int id=0;
    for(int h=0;h<Height;h++) for(int w=0;w<Width;w++){
        if(map_input[h][w]=='.') continue;
        id_map[h][w]=id++;
        if(map_input[h][w]=='@'){
            place_shops.emplace_back(h,w);
        }
    }
    num_hakai=id;
}
    using pPi=pair<Place,int>;
    SetCovering<pPi,int> SC(num_hakai);
    for(int ph=0;ph<Height;ph++){
        for(int pw=0;pw<Width;pw++){
            Place p(ph,pw);
            for(int b=0;b<num_bomb;b++){
                vector<int> ids;
                for(auto dp:bombs[b].ps){
                    auto np=p;
                    np.move(dp);
                    if(np.out_grid() or id_map[np.h][np.w]==-1){
                        continue;
                    }
                    ids.push_back(id_map[np.h][np.w]);
                }
                SC.add_set(pPi(p,b),bombs[b].cost,ids);
            }
        }
    }
    auto names=SC.solve_greedy();
    Place place_now(0,0);
    //一番近くの店に行って爆弾を全部買う
    Place nearest_shop=place_now.find_nearest(place_shops);
    place_now.output_move(nearest_shop);
    for(auto name:names){
        ans.push_back("2 "+to_string(name.second+1));
    }
    //一番近くのところに行って爆弾を落とすのを繰り返す
    while(names.size()){
        pPi name_nearest=place_now.find_nearest(names);
        place_now.output_move(name_nearest.first);
        ans.push_back("3 "+to_string(name_nearest.second+1));
        for(int i=0;i<names.size();i++){
            if(name_nearest.first==names[i].first and name_nearest.second==names[i].second){
                names.erase(names.begin()+i);
                break;
            }
        }
    }
    cout<<ans.size()<<endl;
    for(auto s:ans){
        cout<<s<<endl;
    }
    
#ifndef ONLINE_JUDGE
    testTimer.output();
    testCounter.output();
    cerr<<TIME.span()<<"ms"<<endl;
    //cerr<<"score: "<<simulate(best_grid,true)<<endl;
#endif
}
 
int main(const int argc,const char** argv){
#ifndef OPTUNA
    if(argc!=1){
    }
#endif
    FastIO();
    int T=1;
    //cin>>T;
    while(T--) solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0