#956103 (C++23) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: ぴぃいいいい
• 提出日時: 2024-02-27 07:13:22
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 971 ms / 1,000 ms
• コード長: 7,789 bytes
• コンパイル時間: 3,861 ms
• コンパイル使用メモリ: 194,876 KB
• 実行使用メモリ: 62,548 KB
• スコア: 30,411,130
• 最終ジャッジ日時: 2024-02-27 07:14:14
• 合計ジャッジ時間: 51,283 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

ファイルパターン	結果
other	AC * 50

ソースコード

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <utility>
#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>
#include <optional>
#include <unordered_set>
#include <cassert>
#include <chrono>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using vll = vector<ll>;

inline double get_time() {
    using namespace std::chrono;
    return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
}
double start_time = get_time();

struct IO{
    int n;
    vll a,b;
    IO(){}
    void input(){
        cin >> n;
        a.resize(n);
        b.resize(n);
        for(int i=0;i<n;i++){
            cin >> a[i] >> b[i];
        }
    }
};

//操作を表す構造体
struct Operation{
    size_t x,y;
};
//操作を元に戻すための情報を表す構造体
struct RollbackOperation{
    size_t x,y;
    pair<ll,ll> x_val;
    pair<ll,ll> y_val;
};

struct State{
    IO *io;
    vll a,b;
    //初期状態の生成
    State(IO &_io) : io(&_io){
        a = io->a;
        b = io->b;
    };
    //スコア計算
    ull score(){
        ll diff_a = a[0] - 500000000000000000ll;
        ll diff_b = b[0] - 500000000000000000ll;
        return max(abs(diff_a),abs(diff_b));
    };
    //ハッシュ値計算
    ull hash(){
        ull h = 0;
        for(int i=0;i<io->n;i++){
            h ^= a[i];
            h ^= b[i];
        }
        return h;
    };
    //状態を更新せずスコアとハッシュのみを計算
    pair<ull,ull> try_apply(Operation op, ull score, ull hash){
        if(op.x==0 || op.y==0){
            ll a_ave = (a[op.x] + a[op.y])/2;
            ll b_ave = (b[op.x] + b[op.y])/2;
            ll a_diff = abs(a_ave-500000000000000000ll);
            ll b_diff = abs(b_ave-500000000000000000ll);
            score = max(a_diff,b_diff);
        }
        hash ^= a[op.x];
        hash ^= b[op.x];
        hash ^= a[op.y];
        hash ^= b[op.y];

        return {score,hash};
    };
    //状態を更新する
    //元の状態に戻すための情報を返す
    RollbackOperation apply(Operation op){
        ll a_ave = (a[op.x] + a[op.y])/2;
        ll b_ave = (b[op.x] + b[op.y])/2;
        RollbackOperation rop = {op.x,op.y,{a[op.x],b[op.x]},{a[op.y],b[op.y]}};
        a[op.x] = a_ave;
        b[op.x] = b_ave;
        a[op.y] = a_ave;
        b[op.y] = b_ave;

        return rop;
    }
    //applyから返された情報を元に状態を戻す
    void rollback(RollbackOperation op){
        a[op.x] = op.x_val.first;
        b[op.x] = op.x_val.second;
        a[op.y] = op.y_val.first;
        b[op.y] = op.y_val.second;
    }
};

struct Node;

struct Cand{
    Operation op;
    shared_ptr<Node> parent;
    ull score;
    ull hash;
    ull p; //優先度
};

using Parent = optional<pair<Operation,shared_ptr<Node>>>;
using Children = vector<pair<Operation,weak_ptr<Node>>>;

struct Node{
    Parent parent;
    Children child;
    ull score;
    ull hash;

    Node(Parent parent, Children child, ull score, ull hash):
        parent(parent),child(child),score(score),hash(hash){}
};

// 多スタート用に構造体にまとめておくと楽
struct Tree{
    State state;
    shared_ptr<Node> node;
    ull rank;

    // 注意: depthは深くなっていくごとに-1されていく
    void dfs(vector<Cand>& next_states,bool one,ull& p,ull depth){
        if(depth==0){
            ull score=node->score;
            ull hash=node->hash;

            // 検算
            // assert(score==state.score());
            // assert(hash==state.hash());

            vector<Operation> ops; //次の操作を列挙
            for(int i=0;i<state.io->n;i++){
                for(int j=i+1;j<state.io->n;j++){
                    if(i==j) continue;
                    ops.emplace_back(i,j);
                }
            }

            //次の操作を全部試す
            for(auto const& op:ops){
                auto [next_score,next_hash]=state.try_apply(op,score,hash);
                next_states.emplace_back(Cand{op,node,next_score,next_hash,p});
                p+=1;
            }
        }
        else{
            auto node_backup=node;
            auto child=&node_backup->child;
            // 有効な子だけにする
            child->erase(remove_if(child->begin(),child->end(),[](pair<Operation,weak_ptr<Node>>& x){return x.second.expired();}),child->end());

            bool next_one=one&child->size()==1;
            
            // 定数調整の必要あり
            if(depth==5){
                p=0;
            }
            ++rank;

            for(const auto& [op,ptr]:*child){
                node=ptr.lock();
                RollbackOperation backup=state.apply(op);
                dfs(next_states,next_one,p,depth-1);
                
                if(!next_one){
                    state.rollback(backup);
                }
            }
            
            if(!next_one){
                node=node_backup;
                --rank;
            }
        }
    }
};

vector<Operation> beam(IO &io){
    constexpr ull turn = 50;
    constexpr ull beam_width = 1000;

    State state(io);
    ull score = state.score();
    ull hash = state.hash();

    // 検算
    /* assert(score==state.score());
    assert(hash==state.hash()); */

    Tree tree{move(state), shared_ptr<Node>(new Node(Parent(),Children(),score,hash)),0};

    vector<shared_ptr<Node>> cur{tree.node};
    vector<Cand> next_states;

    unordered_set<ull> hash_set;

    for(ull i=0;i<turn;i++){
        next_states.clear();
        ull tmp = 0;
        tree.dfs(next_states,true,tmp,i-tree.rank);

        #ifndef ONLINE_JUDGE
        cerr << "turn : " << i << " size : " << next_states.size() << endl;
        #endif

        if(i+1!=turn){
            //上位beam_width個だけ残す
            if(next_states.size() > beam_width){
                nth_element(next_states.begin(),next_states.begin()+beam_width,next_states.end(), [](Cand& a, Cand& b){
                    if(a.score == b.score){ return a.p > b.p; }
                    else return a.score < b.score;
                });
                next_states.erase(next_states.begin()+beam_width,next_states.end());
            }
            
            cur.clear();
            hash_set.clear();
            for(const auto&[op,parent,next_score,next_hash,p]:next_states){
                //重複除去
                if(hash_set.count(next_hash)==0){
                    hash_set.insert(next_hash);
                    auto child_ptr=shared_ptr<Node>(new Node(Parent({op,parent}),Children(),score,hash));
                    parent->child.emplace_back(op,weak_ptr<Node>(child_ptr));
                    cur.emplace_back(child_ptr);
                }
            }
        }
    }

    //最良の状態を選択
    ull arg_min = -1;
    ull min = 1ull<<60;

    for(ull i=0;i<next_states.size();i++){
        if(next_states[i].score<=min){
            min=next_states[i].score;
            arg_min=i;
        }
    }
    auto [op,ptr,best_score,_,__]=next_states[arg_min];

    #ifndef ONLINE_JUDGE
    cerr << "best score : " << best_score << endl;
    cerr<<"rank: "<<turn-tree.rank<<endl;
    #endif

    vector<Operation> ret{op};

    // 操作の復元
    while(ptr->parent.has_value()){
        auto [op,parent]=ptr->parent.value();
        ret.emplace_back(op);
        ptr=parent;
    }

    reverse(ret.begin(),ret.end());
    return ret;
}

int main(){
    IO io;
    io.input();
    auto ops = beam(io);
    cout << ops.size() << endl;
    for(auto [x,y]:ops){
        cout << x+1 << " " << y+1 << endl;
    }

    #ifndef ONLINE_JUDGE
    cerr << "time : " << get_time()-start_time << "ms" << endl;
    #endif
}