結果
| 問題 | 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 | -- | - |
ソースコード
#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;
}