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

• 問題: No.5020 Averaging
• ユーザー: ぴぃいいいい
• 提出日時: 2024-02-29 01:55:06
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 892 ms / 1,000 ms
• コード長: 8,930 bytes
• コンパイル時間: 4,552 ms
• コンパイル使用メモリ: 211,648 KB
• 実行使用メモリ: 19,504 KB
• スコア: 79,542,937
• 最終ジャッジ日時: 2024-02-29 01:55:59
• 合計ジャッジ時間: 47,521 ms
• ジャッジサーバーID （参考情報）: judge13 / 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>
#include <numeric>
#include <queue>
#include <cmath>
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 IndexSet {
    vector<int> que;
    vector<int> pos;

    IndexSet() {}

    IndexSet(int n) : pos(n), que(n) {
        iota(pos.begin(),pos.end(),0);
        iota(que.begin(),que.end(),0);
    }

    void add(int v) {
        pos[v] = que.size();
        que.push_back(v);
    }

    void remove(int v) {
        int p = pos[v];
        int b = que.back();
        que[p] = b;
        que.pop_back();
        pos[b] = p;
        pos[v] = -1;
    }

    bool contains(int v) const {
        return pos[v] != -1;
    }

    int size() const {
        return que.size();
    }
};

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];
            a[i] -= 500000000000000000ll;
            b[i] -= 500000000000000000ll;
        }
    }
};

//操作を表す構造体
struct Operation{
    size_t i;
};
//操作を元に戻すための情報を表す構造体
struct RollbackOperation{
    size_t i;
    double mul;
};

struct State{
    IO *io;
    double a,b;
    IndexSet unused;
    int cnt;

    //初期状態の生成
    State(IO &_io) : io(&_io){
        a = 0, b = 0;
        unused = IndexSet(io->n);
        cnt = 1;
    };
    //スコア計算
    ull score(){
        return max(abs(a),abs(b));
    };
    //ハッシュ値計算
    ull hash(){
        ull h = ull(a)^ull(b);
        /* for(int i=0;i<io->n;i++){
            if(!unused.contains(i)){
                h^=i;
            }
        } */
        return h;
    };
    //状態を更新せずスコアとハッシュのみを計算
    pair<ull,ull> try_apply(Operation op, ull score, ull hash){
        double ave_a = a + pow(0.5,cnt) * (double)io->a[op.i];
        double ave_b = b + pow(0.5,cnt) * (double)io->b[op.i];
        hash = ull(ave_a) ^ ull(ave_b);
        score = max(abs(ave_a),abs(ave_b));
        if(score == 0){
            cerr << "a : " << a << endl;
            cerr << "b : " << b << endl;
            cerr << "ave_a : " << ave_a << endl;
            cerr << "ave_b : " << ave_b << endl;
            cerr << "abs(ave_a) : " << abs(ave_a) << endl;
            cerr << "abs(ave_b) : " << abs(ave_b) << endl;
            exit(1);
        }
        return {score,hash};
    };
    //状態を更新する
    //元の状態に戻すための情報を返す
    RollbackOperation apply(Operation op){
        a += pow(0.5,cnt) * io->a[op.i]; 
        b += pow(0.5,cnt) * io->b[op.i];
        RollbackOperation rop = {op.i, pow(0.5,cnt)};
        cnt++;
        unused.remove(op.i);

        
        return rop;
    }
    //applyから返された情報を元に状態を戻す
    void rollback(RollbackOperation op){
        a -= op.mul * io->a[op.i];
        b -= op.mul * io->b[op.i];
        cnt--;
        unused.add(op.i);
    }
};

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.unused.que.size();i++){
                ops.emplace_back(state.unused.que[i]);
            }

            //次の操作を全部試す
            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){
    ull turn = io.n;
    constexpr ull beam_width = 5000;

    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());
            }
            cerr << "best score : " << next_states[0].score << endl;
            
            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);
    bool zero_merged = false;
    int last = -1;
    reverse(ops.begin(),ops.end());
    cout << ops.size()-1 << endl;
    for(auto op:ops){
        if(last == -1){
            last = op.i;
        }
        else{
            if(zero_merged){
                cout << 1 << " " << op.i+1 << endl;
            }
            else{
                cout << last+1 << " " << op.i+1 << endl;
            }
            last = op.i;
        }
        if(last == 0){
            zero_merged = true;
        }
    }

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