#865002 (Rust) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	rhoo
提出日時	2023-04-30 18:23:25
言語	Rust (1.77.0)
結果	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
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	981 ms 4,372 KB
testcase_01	AC	982 ms 4,368 KB
testcase_02	AC	982 ms 4,368 KB
testcase_03	AC	982 ms 4,372 KB
testcase_04	AC	982 ms 4,368 KB
testcase_05	AC	982 ms 4,372 KB
testcase_06	AC	982 ms 4,368 KB
testcase_07	AC	982 ms 4,372 KB
testcase_08	AC	982 ms 4,368 KB
testcase_09	AC	982 ms 4,372 KB
testcase_10	AC	981 ms 4,368 KB
testcase_11	AC	982 ms 4,500 KB
testcase_12	AC	982 ms 4,368 KB
testcase_13	AC	982 ms 4,372 KB
testcase_14	AC	981 ms 4,368 KB
testcase_15	AC	982 ms 4,368 KB
testcase_16	AC	982 ms 4,372 KB
testcase_17	AC	982 ms 4,372 KB
testcase_18	AC	982 ms 4,372 KB
testcase_19	AC	982 ms 4,368 KB
testcase_20	AC	982 ms 4,372 KB
testcase_21	AC	981 ms 4,368 KB
testcase_22	AC	982 ms 4,372 KB
testcase_23	AC	982 ms 4,368 KB
testcase_24	AC	982 ms 4,372 KB
testcase_25	AC	982 ms 4,368 KB
testcase_26	AC	982 ms 4,372 KB
testcase_27	AC	981 ms 4,368 KB
testcase_28	AC	982 ms 4,372 KB
testcase_29	AC	982 ms 4,372 KB

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

コンパイルメッセージ

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

ソースコード

raw source code

#![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
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード