結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 rhoo
|
| 提出日時 | 2023-04-30 18:23:25 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 982 ms / 1,000 ms |
| コード長 | 21,342 bytes |
| コンパイル時間 | 8,880 ms |
| コンパイル使用メモリ | 184,076 KB |
| 実行使用メモリ | 4,500 KB |
| スコア | 9,070,532 |
| 最終ジャッジ日時 | 2023-04-30 18:24:12 |
| 合計ジャッジ時間 | 36,649 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
warning: variable `iter_sum` is assigned to, but never used
--> Main.rs:266:13
|
266 | let mut iter_sum=0;
| ^^^^^^^^
|
= note: consider using `_iter_sum` instead
= note: `#[warn(unused_variables)]` on by default
warning: variable `valid` is assigned to, but never used
--> Main.rs:267:13
|
267 | let mut valid=0;
| ^^^^^
|
= note: consider using `_valid` instead
warning: function `to` is never used
--> Main.rs:451:4
|
451 | fn to(score:i64)->i64{
| ^^
|
= note: `#[warn(dead_code)]` on by default
warning: 3 warnings emitted
ソースコード
#![allow(non_snake_case)]
fn optimize(input:&In,pos:&[P],id:usize,route:&[usize],target:&[usize])->(P,i64){
let mut coeff=[(0,0,0);2];
let mut update=|n:usize|{
// k(a-x)^2=kx^2-2kax+ka^2
let (pos,k)=if n<N{
(input.pos[n],ALPHA)
} else {
(pos[n-N],1)
};
coeff[0].0+=k;
coeff[0].1+=-2*k*pos.0;
coeff[0].2+=k*pos.0*pos.0;
coeff[1].0+=k;
coeff[1].1+=-2*k*pos.1;
coeff[1].2+=k*pos.1*pos.1;
};
for &i in target{
assert_eq!(route[i],id);
update(route[i-1]);
update(route[i+1]);
}
let cost=|pos:P|{
coeff[0].0*pos.0*pos.0+coeff[0].1*pos.0+coeff[0].2
+coeff[1].0*pos.1*pos.1+coeff[1].1*pos.1+coeff[1].2
};
let best=P(-coeff[0].1/coeff[0].0/2,-coeff[1].1/coeff[1].0/2);
let diff=cost(best)-cost(pos[id-N]);
(best,diff)
}
#[derive(Clone)]
struct State{
pos:[P;M],
cnt:[usize;N],
route:Vec<usize>,
}
impl State{
fn new()->State{
let mut route:Vec<_>=(0..N).chain(once(0)).collect();
rnd::shuffle(&mut route[1..N]);
let mut cnt=[1;N];
cnt[0]=2;
let pos=[();M].map(|_|P::rand(0,L));
State{pos,cnt,route}
}
fn score(&self,input:&In)->i64{
self.route.windows(2).map(|w|self.dist(input,w[0],w[1])).sum()
}
fn dist(&self,input:&In,a:usize,b:usize)->i64{
if a<N && b<N{
input.dist[a][b]
}
else if a>=N && b>=N{
(self.pos[a-N]-self.pos[b-N]).abs2()
}
else if a>=N{
ALPHA*(self.pos[a-N]-input.pos[b]).abs2()
}
else{
ALPHA*(self.pos[b-N]-input.pos[a]).abs2()
}
}
// idxは+Nされたあと
fn change(&mut self,input:&In,id:usize,new:P,add:i64,score:&mut i64,BF:&mut BUF)->bool{
BF.V.clear();
BF.target.clear();
let mut prev=self.route[0];
BF.V.push(prev);
let mut new_score=0;
let backup=self.pos[id-N];
self.pos[id-N]=new;
let mut f=false;
for &n in &self.route[1..]{
if n!=id{
let diff0=self.dist(input,prev,n);
let diff1=self.dist(input,prev,id)+self.dist(input,id,n);
if diff1<diff0{
f=true;
BF.target.push(BF.V.len());
BF.V.push(id);
}
new_score+=diff0.min(diff1);
BF.V.push(n);
prev=n;
}
}
if !f{
self.pos[id-N]=backup;
return false;
}
let (best,diff)=optimize(input,&self.pos,id,&BF.V,&BF.target);
new_score+=diff;
if new_score-*score<=add{
*score=new_score;
std::mem::swap(&mut BF.V,&mut self.route);
self.pos[id-N]=best;
true
}
else{
self.pos[id-N]=backup;
false
}
}
fn try_two_opt(&self,input:&In,a:usize,b:usize)->i64{
assert!(a+2<=b);
let (a0,a1)=(self.route[a-1],self.route[a]);
let (b0,b1)=(self.route[b-1],self.route[b]);
self.dist(input,a0,b0)+self.dist(input,a1,b1)-self.dist(input,a0,a1)-self.dist(input,b0,b1)
}
fn two_opt(&mut self,a:usize,b:usize){
self.route[a..b].reverse();
}
fn try_insert(&self,input:&In,a:usize,b:usize)->i64{
let (a0,a1)=(self.route[a-1],self.route[a]);
self.dist(input,a0,b)+self.dist(input,b,a1)-self.dist(input,a0,a1)
}
fn insert(&mut self,a:usize,b:usize){
self.route.insert(a,b);
if b<N{
self.cnt[b]+=1;
}
}
fn try_remove(&self,input:&In,a:usize)->i64{
let (a0,a1,a2)=(self.route[a-1],self.route[a],self.route[a+1]);
assert!(a1>=N || self.cnt[a1]>1);
self.dist(input,a0,a2)-self.dist(input,a0,a1)-self.dist(input,a1,a2)
}
fn remove(&mut self,idx:usize){
let n=self.route.remove(idx);
if n<N{
self.cnt[n]-=1;
}
}
}
fn trans(input:&In,state:&mut State,it:usize,add:i64,D:i64,score:&mut i64,BF:&mut BUF)->bool{
if it%20==0{
let id=rnd::next()%M;
let pos=state.pos[id];
let mut np;
loop{
np=pos+P::rand(-D,D);
if np.in_range(){
break;
}
}
state.change(input,id+N,np,add,score,BF)
}
else{
let n=[0,0,0,0,0,0,1,1,2,2].choice();
match n{
0=>{
let mut a=rnd::range(1,state.route.len());
let mut b;
loop{
b=rnd::range(1,state.route.len());
if 2<a-b+1{
break;
}
}
if a>b{
std::mem::swap(&mut a,&mut b);
}
let diff=state.try_two_opt(input,a,b);
if diff<=add{
*score+=diff;
state.two_opt(a,b);
true
}
else{
false
}
}
1=>{
let idx=rnd::range(1,state.route.len());
let mut n;
let mut diff;
loop{
n=rnd::next()%(N+M);
diff=state.try_insert(input,idx,n);
if diff!=0{
break;
}
}
if diff<=add{
*score+=diff;
state.insert(idx,n);
true
}
else{
false
}
}
2=>{
let mut ty=0;
let mut idx;
loop{
idx=rnd::range(1,state.route.len()-1);
if state.route[idx]>=N || state.cnt[state.route[idx]]>1{
break;
}
else{
ty+=1;
if ty>=10{
return false;
}
}
}
let diff=state.try_remove(input,idx);
if diff<=add{
*score+=diff;
state.remove(idx);
true
}
else{
false
}
}
_=>panic!()
}
}
}
fn sa_tsp(input:&In,TL:f64)->([P;M],Vec<usize>){
let mut BF=BUF::default();
let mut ans_score=i64::MAX;
let mut ans_state=([P(0,0);M],vec![]);
let mut iter_sum=0;
let mut valid=0;
let mut th=[0;64];
let mut D=0;
const I:usize=6;
for i in 0..I{
let mut state=State::new();
let mut score=state.score(input);
let start=get_time();
let TL=TL*(i+1) as f64/I as f64-start;
let mut iter=0;
let mut best=i64::MAX;
let mut best_state=state.clone();
let mut ty=0;
loop{
if iter&255==0{
let time=(get_time()-start)/TL;
if time>=1.{
break;
}
const T:f64=35000.;
let heat=T*(1.-time.powf(0.5));
th.fill_with(||(-heat*rnd::nextf().ln()) as i64);
const D0:f64=300.;
const D1:f64=10.;
D=(D0+(D1-D0)*time.powf(1.5)).round() as i64;
}
iter+=1;
valid+=trans(input,&mut state,iter,th[iter&63],D,&mut score,&mut BF) as usize;
if best>score{
best=score;
best_state=state.clone();
ty=0;
}
else{
ty+=1;
if ty>=150000{
ty=0;
state=best_state.clone();
score=best;
}
}
}
eprintln!("# try{}: {}",i,to(score));
assert_eq!(score,state.score(input));
iter_sum+=iter;
if ans_score>best{
ans_score=best;
ans_state=(best_state.pos,best_state.route);
}
}
eprintln!("iter = {}",iter_sum);
eprintln!("ratio = {:.4}",valid as f64/iter_sum as f64);
eprintln!("best = {}",to(ans_score));
eprintln!("len = {}",ans_state.1.len());
ans_state
}
fn solve(input:&In)->([P;M],Vec<usize>){
let (mut pos,route)=sa_tsp(&input,0.9);
let mut dists=[[-1;N+M];N+M];
let mut next=[[0;N+M];N+M];
for i in 0..N+M{
let (p0,k0)=if i<N{
(input.pos[i],ALPHA)
} else {
(pos[i-N],1)
};
for j in 0..N+M{
let (p1,k1)=if j<N{
(input.pos[j],ALPHA)
} else {
(pos[j-N],1)
};
dists[i][j]=(p0-p1).abs2()*k0*k1;
next[i][j]=j;
}
}
for k in 0..N+M{
for i in 0..N+M{
for j in 0..N+M{
let new=dists[i][k]+dists[k][j];
if new<dists[i][j]{
dists[i][j]=new;
next[i][j]=next[i][k];
}
}
}
}
let mut seen=[false;N];
let route:Vec<_>=route.into_iter().filter(|&n|n<N && !seen[n] && {seen[n]=true; true}).chain(once(0)).collect();
let mut dist=vec![vec![-1;N];N];
for i in 0..N{
for j in 0..N{
dist[i][j]=dists[i][j];
}
}
let best_route=tsp(&dist,route,0.98);
let mut route=vec![];
for w in best_route.windows(2){
let (mut s,t)=(w[0],w[1]);
while s!=t{
route.push(s);
s=next[s][t];
}
}
route.push(*best_route.last().unwrap());
let mut target=vec![];
for _ in 0..3{
for id in 0..M{
target.clear();
target.extend((0..route.len()).filter(|&i|route[i]==id+N));
(pos[id],_)=optimize(input,&pos,id+N,&route,&target);
}
}
(pos,route)
}
fn main(){
get_time();
let input=In::input();
let (pos,route)=solve(&input);
#[cfg(local)]{
let mut score=0;
for w in route.windows(2){
let (p0,k0)=if w[0]<N{
(input.pos[w[0]],ALPHA)
} else {
(pos[w[0]-N],1)
};
let (p1,k1)=if w[1]<N{
(input.pos[w[1]],ALPHA)
} else {
(pos[w[1]-N],1)
};
score+=(p1-p0).abs2()*k0*k1;
}
eprintln!("score = {}",to(score));
}
for pos in pos{
println!("{} {}",pos.0,pos.1);
}
println!("{}",route.len());
for n in route{
if n<N{
println!("1 {}",n+1);
}
else{
println!("2 {}",n-N+1);
}
}
}
use std::iter::*;
fn to(score:i64)->i64{
(1e9/(1e3+(score as f64).sqrt())).round() as i64
}
const N:usize=100;
const M:usize=8;
const L:i64=1001;
const ALPHA:i64=5;
struct In{
pos:[P;N],
dist:[[i64;N];N]
}
impl In{
fn input()->In{
let mut scan=Scanner::new();
input!{
scan,
n:usize,
m:usize,
tp:[(usize,usize);N]
}
assert_eq!((n,m),(N,M));
let pos:[P;N]=tp.iter().map(|&(a,b)|P(a as i64,b as i64)).collect::<Vec<_>>().try_into().unwrap();
let mut dist=[[-1;N];N];
for i in 0..N{
for j in 0..N{
dist[i][j]=(pos[i]-pos[j]).abs2()*ALPHA*ALPHA;
}
}
for k in 0..N{
for i in 0..N{
for j in 0..N{
dist[i][j]=dist[i][j].min(dist[i][k]+dist[k][j]);
}
}
}
In{pos,dist}
}
}
#[derive(Default)]
struct BUF{
V:Vec<usize>,
target:Vec<usize>
}
#[macro_export]#[cfg(not(local))]macro_rules! eprint{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! eprintln{($($_:tt)*)=>{}}
fn get_time()->f64{
static mut START:f64=-1.;
let time=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
unsafe{
if START<0.{
START=time;
}
#[cfg(local)]{
(time-START)*2.
}
#[cfg(not(local))]{
time-START
}
}
}
struct Scanner{
stack:std::str::SplitAsciiWhitespace<'static>
}
impl Scanner{
fn new()->Self{
use std::io::Read;
let mut tmp=String::new();
std::io::stdin().read_to_string(&mut tmp).unwrap();
Self{stack:Box::leak(tmp.into_boxed_str()).split_ascii_whitespace()}
}
fn read<T:std::str::FromStr>(&mut self)->T{
self.stack.next().unwrap().parse::<T>().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::<T>()))
}
}
#[macro_export]
macro_rules! input{
($scan:ident, $($rest:tt)*)=>{
input_inner!{$scan,$($rest)*}
};
}
#[macro_export]
macro_rules! input_inner{
($scan:ident $(,)?)=>{};
($scan:ident, $name:ident:$t:tt $($rest:tt)*)=>{
let $name=read_value!($scan,$t);
input_inner!{$scan $($rest)*}
};
}
#[macro_export]
macro_rules! read_value{
($scan:ident, ($($t:tt),*))=>{
($(read_value!($scan, $t)),*)
};
($scan:ident, [$t:tt;$len:expr])=>{
(0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
};
($scan:ident, Chars)=>{
read_value!($scan,String).chars().collect::<Vec<char>>()
};
($scan:ident, Usize1)=>{
read_value!($scan,usize)-1
};
($scan:ident, $t:ty)=>{
$scan.read::<$t>()
};
}
mod rnd {
static mut S:usize=88172645463325252;
pub fn next()->usize{
unsafe{
S^=S<<7;
S^=S>>9;
S
}
}
pub fn nextf()->f64{
f64::from_bits((0x3ff0000000000000|next()&0xfffffffffffff) as u64)-1.
}
pub fn range(a:usize,b:usize)->usize{
next()%(b-a)+a
}
pub fn rangei(a:i64,b:i64)->i64{
(next()%((b-a) as usize)) as i64+a
}
pub fn shuffle<T>(list:&mut [T]){
for i in (0..list.len()).rev(){
list.swap(i,next()%(i+1));
}
}
}
trait RandomChoice{
type Output;
fn choice(&self)->&Self::Output;
}
impl<T> RandomChoice for [T]{
type Output=T;
fn choice(&self)->&T{
&self[rnd::next()%self.len()]
}
}
#[derive(Clone,Copy,PartialEq,Default,Debug)]
struct P(i64,i64);
impl P{
fn rand(a:i64,b:i64)->P{
P(rnd::rangei(a,b),rnd::rangei(a,b))
}
fn in_range(self)->bool{
(self.0 as usize)<L as usize && (self.1 as usize)<L as usize
}
fn abs2(self)->i64{
self.0*self.0+self.1*self.1
}
}
use std::ops::*;
impl Add for P{
type Output=P;
fn add(self,a:P)->P{
P(self.0+a.0,self.1+a.1)
}
}
impl Sub for P{
type Output=P;
fn sub(self,a:P)->P{
P(self.0-a.0,self.1-a.1)
}
}
impl AddAssign for P{
fn add_assign(&mut self,a:P){
*self=*self+a;
}
}
impl SubAssign for P{
fn sub_assign(&mut self,a:P){
*self=*self-a;
}
}
// wataさんのTSPSolver
fn compute_cost(dist:&Vec<Vec<i64>>,route:&[usize])->i64{
route.windows(2).map(|w|dist[w[0]][w[1]]).sum()
}
// mv: (i, dir)
fn apply_move<const K:usize>(tour:&mut [usize],idx:&mut [usize],mv:&[(usize,usize);K],BF:&mut Vec<usize>){
let mut ids=[!0;K];
let mut it=0..;
ids.fill_with(||it.next().unwrap());
ids.sort_unstable_by_key(|&i|mv[i].0);
let mut order=[0;K];
for i in 0..K{
order[ids[i]]=i;
}
let mut i=ids[0];
let mut dir=0;
BF.clear();
loop{
let (j,rev)=if dir==mv[i].1{
((i+1)%K,0)
}
else{
((i+K-1)%K,1)
};
if mv[j].1==rev{
if order[j]==K-1{
break;
}
i=ids[order[j]+1];
dir=0;
BF.extend_from_slice(&tour[mv[j].0+1..mv[i].0+1]);
}
else{
i=ids[order[j]-1];
dir=1;
BF.extend(tour[mv[i].0+1..mv[j].0+1].iter().rev().cloned());
}
}
assert_eq!(BF.len(),mv[ids[K-1]].0-mv[ids[0]].0);
tour[mv[ids[0]].0+1..mv[ids[K-1]].0+1].copy_from_slice(&BF);
for i in mv[ids[0]].0+1..mv[ids[K-1]].0+1{
idx[tour[i]]=i;
}
}
const FEASIBLE3:[bool;64]=[false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false];
fn tsp(dist:&Vec<Vec<i64>>,mut route:Vec<usize>,TL:f64)->Vec<usize>{
let n=dist.len();
assert_eq!(n,route.len()-1);
let mut f=vec![vec![];n];
for i in 0..n{
for j in 0..n{
if i!=j{
f[i].push((dist[i][j],j));
}
}
f[i].sort_unstable_by(|&(a,_),&(b,_)|a.partial_cmp(&b).unwrap());
}
let mut idx=vec![!0;n];
let (mut min_score,mut best)=(compute_cost(&dist,&route),route.clone());
let mut BF=vec![];
while get_time()<TL{
let mut cost=compute_cost(&dist,&route);
for i in 0..n{
idx[route[i]]=i;
}
loop {
let mut ok=false;
for i in 0..n{
for di in 0..2{
'outer: for &(ij,vj) in &f[route[i+di]]{
if dist[route[i]][route[i+1]]-ij<=0{
break;
}
for dj in 0..2{
let j=if idx[vj]==0 && dj==0{
n-1
} else {
idx[vj]-1+dj
};
let gain=dist[route[i]][route[i+1]]-ij+dist[route[j]][route[j+1]];
let diff=gain-dist[route[j+dj]][route[i+1-di]];
if di!=dj && diff>0{
cost-=diff;
apply_move(&mut route,&mut idx,&[(i,di),(j,dj)],&mut BF);
ok=true;
break 'outer;
}
for &(jk,vk) in &f[route[j+dj]]{
if gain-jk<=0{
break;
}
for dk in 0..2{
let k=if idx[vk]==0 && dk==0{
n-1
} else {
idx[vk]-1+dk
};
if i==k || j==k{
continue;
}
let diff=gain-jk+dist[route[k]][route[k+1]]-dist[route[k+dk]][route[i+1-di]];
if diff>0{
let mask=((i<j) as usize)<<5 | ((i<k) as usize)<<4 | ((j<k) as usize)<<3 | di<<2 | dj<<1 | dk;
if FEASIBLE3[mask]{
cost-=diff;
apply_move(&mut route,&mut idx,&[(i,di),(j,dj),(k,dk)],&mut BF);
ok=true;
break 'outer;
}
}
}
}
}
}
}
}
if !ok{
break;
}
}
if min_score>cost{
min_score=cost;
best=route;
}
route=best.clone();
loop{
if rnd::next()&1==0{
// double bridge
let mut is=[!0;4];
is.fill_with(||rnd::next()%n+1);
is.sort_unstable();
if is[0]==is[1] || is[1]==is[2] || is[2]==is[3]{
continue;
}
BF.clear();
let it=route[is[2]..is[3]].iter().chain(&route[is[1]..is[2]]).chain(&route[is[0]..is[1]]);
BF.extend(it.cloned());
route[is[0]..is[3]].copy_from_slice(&BF);
}
else{
for _ in 0..6{
loop{
let i=rnd::next()%(n-1);
let j=rnd::next()%(n-1);
if i<j && j-i<n-2{
route[i+1..j].reverse();
break;
}
}
}
}
break;
}
}
best
}