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

提出ソース

結果

問題	No.5020 Averaging
ユーザー	ぴぃいいいい
提出日時	2024-02-29 02:02:48
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,000 bytes
コンパイル時間	5,231 ms
コンパイル使用メモリ	211,432 KB
実行使用メモリ	34,232 KB
スコア	1,593,964
最終ジャッジ日時	2024-02-29 02:03:57
合計ジャッジ時間	65,693 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	AC	939 ms 31,412 KB
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	TLE	-
testcase_31	TLE	-
testcase_32	TLE	-
testcase_33	TLE	-
testcase_34	TLE	-
testcase_35	TLE	-
testcase_36	TLE	-
testcase_37	TLE	-
testcase_38	TLE	-
testcase_39	TLE	-
testcase_40	TLE	-
testcase_41	TLE	-
testcase_42	TLE	-
testcase_43	TLE	-
testcase_44	TLE	-
testcase_45	TLE	-
testcase_46	TLE	-
testcase_47	TLE	-
testcase_48	TLE	-
testcase_49	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 HalfPow{
    double a[100];
    constexpr HalfPow(){
        a[0] = 1.0;
        for(int i=1;i<100;i++){
            a[i] = a[i-1] * 0.5;
        }
        return;
    }
};
constexpr auto p = HalfPow();


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);
        return h;
    };
    //状態を更新せずスコアとハッシュのみを計算
    pair<ull,ull> try_apply(Operation op, ull score, ull hash){
        double ave_a = a + p.a[cnt] * (double)io->a[op.i];
        double ave_b = b + p.a[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 += p.a[cnt] * io->a[op.i]; 
        b += p.a[cnt] * io->b[op.i];
        RollbackOperation rop = {op.i, p.a[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 = 10000;

    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
}

yukicoder

結果

テストケース

ソースコード