結果

問題 No.5020 Averaging
ユーザー ぴぃいいいいぴぃいいいい
提出日時 2024-02-27 07:07:27
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 7,581 bytes
コンパイル時間 2,860 ms
コンパイル使用メモリ 177,788 KB
実行使用メモリ 126,024 KB
スコア 0
最終ジャッジ日時 2024-02-27 07:08:36
合計ジャッジ時間 27,732 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 TLE -
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 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

#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 = 2000;

    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);

        cerr << "turn : " << i << " size : " << next_states.size() << endl;

        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];

    cerr << "best score : " << best_score << endl;
    cerr<<"rank: "<<turn-tree.rank<<endl;

    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;
    }
    cerr << "time : " << get_time()-start_time << "ms" << endl;
}
0