#860271 (Rust) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	rhoo
提出日時	2023-04-16 17:45:59
言語	Rust (1.77.0)
結果	WA
実行時間	-
コード長	25,812 bytes
コンパイル時間	5,077 ms
コンパイル使用メモリ	184,876 KB
実行使用メモリ	131,140 KB
スコア	70,950
最終ジャッジ日時	2023-04-16 17:50:56
合計ジャッジ時間	290,775 ms
ジャッジサーバーID （参考情報）	judge13 / judge16

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	2,838 ms 88,104 KB
testcase_05	AC	2,861 ms 115,172 KB
testcase_06	WA	-
testcase_07	AC	2,850 ms 110,760 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	2,475 ms 112,608 KB
testcase_11	WA	-
testcase_12	AC	2,853 ms 106,632 KB
testcase_13	AC	2,871 ms 126,420 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	2,870 ms 85,548 KB
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	AC	2,852 ms 103,428 KB
testcase_35	AC	2,851 ms 112,904 KB
testcase_36	WA	-
testcase_37	AC	2,857 ms 120,248 KB
testcase_38	AC	2,861 ms 104,696 KB
testcase_39	AC	2,857 ms 111,440 KB
testcase_40	WA	-
testcase_41	WA	-
testcase_42	AC	2,853 ms 105,984 KB
testcase_43	WA	-
testcase_44	AC	1,874 ms 106,756 KB
testcase_45	WA	-
testcase_46	WA	-
testcase_47	AC	2,317 ms 110,380 KB
testcase_48	AC	2,856 ms 121,132 KB
testcase_49	WA	-
testcase_50	WA	-
testcase_51	AC	2,850 ms 104,196 KB
testcase_52	WA	-
testcase_53	AC	2,879 ms 101,860 KB
testcase_54	WA	-
testcase_55	WA	-
testcase_56	AC	2,854 ms 108,556 KB
testcase_57	WA	-
testcase_58	AC	2,852 ms 110,528 KB
testcase_59	AC	2,355 ms 106,764 KB
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	AC	2,874 ms 124,872 KB
testcase_68	WA	-
testcase_69	AC	2,854 ms 117,296 KB
testcase_70	WA	-
testcase_71	AC	2,854 ms 112,436 KB
testcase_72	WA	-
testcase_73	AC	2,856 ms 105,308 KB
testcase_74	AC	2,849 ms 102,128 KB
testcase_75	AC	2,861 ms 111,168 KB
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	AC	2,851 ms 106,544 KB
testcase_81	WA	-
testcase_82	WA	-
testcase_83	WA	-
testcase_84	WA	-
testcase_85	WA	-
testcase_86	WA	-
testcase_87	AC	2,854 ms 116,172 KB
testcase_88	AC	2,855 ms 112,412 KB
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-
testcase_92	RE	-
testcase_93	WA	-
testcase_94	AC	2,856 ms 109,228 KB
testcase_95	WA	-
testcase_96	WA	-
testcase_97	AC	2,852 ms 111,456 KB
testcase_98	WA	-
testcase_99	WA	-

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

コンパイルメッセージ

warning: variable `HP` is assigned to, but never used
   --> Main.rs:593:13
    |
593 |     let mut HP=H;
    |             ^^
    |
    = note: consider using `_HP` instead
    = note: `#[warn(unused_variables)]` on by default

warning: variable `I` is assigned to, but never used
   --> Main.rs:888:17
    |
888 |         let mut I=0;
    |                 ^
    |
    = note: consider using `_I` instead

warning: function `simulate` is never used
   --> Main.rs:592:4
    |
592 | fn simulate(input:&In,route:&[usize]){
    |    ^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 3 warnings emitted

ソースコード

raw source code

#![allow(non_snake_case)]
#[cfg(not(local))]macro_rules! eprintln{($($_:tt)*)=>{}}


const MAX_TURN:usize=N*2;

struct BUF{
    base:i64,
    dist:Vec<i64>,
    prev:Vec<Vec<usize>>,
    que:BinaryHeap<Reverse<S<i64,(usize,usize)>>>,
    que0:BinaryHeap<Reverse<S<(i64,i64),(usize,usize)>>>
}
impl BUF{
    fn new()->BUF{
        BUF{
            base:i64::MAX,
            dist:vec![i64::MAX;N2],
            prev:vec![vec![!0;MAX_TURN];N2],
            que:BinaryHeap::new(),
            que0:BinaryHeap::new()
        }
    }
    
    fn reset(&mut self){
        self.base-=100000;
        self.que.clear();
    }
}


// todo
// pinch_penalty
fn score(HP:i64,juwels:usize,key:bool)->f64{
    const KEY_BONUS0:f64=3.;
    const KEY_BONUS1:f64=30.;
    
    juwels as f64
    +if key{
        let r=(1500-HP) as f64/1500.;
        KEY_BONUS0*(KEY_BONUS1/KEY_BONUS0).powf(r)
    } else {
        0.
    }
}


// しょうがないから自明解
fn greedy(input:&In,start:usize,key:bool,seen:&mut [bool])->(usize,Vec<usize>){
    let find_path=|start:usize,goal:usize,seen:&[bool]|->(i64,Vec<usize>){
        let mut prev=vec![!0;N2];
        let mut que=BinaryHeap::new();
        prev[start]=!1;
        que.push(Reverse(S((0,0),start)));
        let mut ans=0;
        'outer: while let Some(Reverse(S((dist,juwels),pos)))=que.pop(){
            for &dd in &DD[..4]{
                let np=pos+dd;
                if np==goal{
                    prev[goal]=pos;
                    ans=juwels;
                    break 'outer;
                }
                let cell=input.grid[np];
                if cell.is_through() && prev[np]==!0{
                    prev[np]=pos;
                    let mut new_j=juwels;
                    if let Juwel(id)=cell{
                        new_j-=!seen[id] as i64;
                    }
                    que.push(Reverse(S((dist+1,new_j),np)));
                }
            }
        }

        let mut route=vec![];
        let mut pos=goal;
        loop{
            route.push(pos);
            pos=prev[pos];
            if pos==!1{
                break;
            }
        }
        route.pop();
        route.reverse();

        (-ans,route)
    };
    if key{
        let mut route=vec![];
        let (score0,mut route0)=find_path(start,input.goal,seen);
        route.append(&mut route0);

        (score0 as usize,route)
    }
    else{
        let mut route=vec![start];
        let (score0,mut route0)=find_path(start,input.key,seen);
        for &pos in &route0{
            if let Juwel(id)=input.grid[pos]{
                seen[id]=true;
            }
        }
        route.append(&mut route0);
        let (score1,mut route1)=find_path(input.key,input.goal,seen);
        route.append(&mut route1);

        ((score0+score1) as usize,route)
    }
}


#[derive(Clone)]
struct Node{
    hist:List<usize>,
    seen:Vec<u8>,
    pos:usize,
    turn:usize,
    HP:i64,
    juwels:usize,
}
impl Node{
    fn new(input:&In)->Node{
        Node{
            hist:Cons(input.start,Rc::new(Nil)),
            seen:vec![0;(input.I>>3)+1],
            pos:input.start,
            turn:0,
            HP:H,
            juwels:0,
        }
    }

    fn get(&self,id:usize)->bool{
        let (a,b)=(id>>3,id&7);
        self.seen[a]>>b&1==1
    }

    fn to_goal(&self,input:&In,best:&mut List<usize>,best_score:&mut usize,BF:&mut BUF){
        assert!(self.get(0));
        
        let old=BF.base;
        BF.reset();
        BF.que0.push(Reverse(S((BF.base,0),(self.pos,0))));
        BF.dist[self.pos]=BF.base;
        BF.prev[self.pos][0]=!0;

        let th=BF.base+self.HP;

        while let Some(Reverse(S((cost,juwels),(pos,t))))=BF.que0.pop(){
            let turn=(self.turn+t)%60;
            let nturn=(turn+1)%60;
            let nt=t+1;
            
            for dd in DX{
                let np=pos+dd;
                let cell=input.grid[np];
                let nc=input.damage[np][nturn]+cost;
                if cell==Goal{
                    let diff=cost-BF.base;
                    if dd==0 || self.HP<=diff{
                        continue;
                    }
                    let mut route=vec![np];
                    let mut pos=(pos,t);
                    loop{
                        route.push(pos.0);
                        pos=(BF.prev[pos.0][pos.1],pos.1-1);
                        if pos.0==!0{
                            break;
                        }
                    }
                    route.pop();
                    route.reverse();
                    
                    let juwels=self.juwels-juwels as usize;

                    assert!(0<self.HP-diff);
                    if *best_score<juwels{
                        *best_score=juwels;
                        *best=self.hist.append(&route);
                    }

                    return;
                }
                else if cell.is_through() && MAX_TURN>nt{
                    if old>BF.dist[np] && dd!=0{
                        continue;
                    }
                    BF.dist[np]=old-1;

                    if (BF.dist[np]>nc || dd==0) && th>nc{
                        BF.dist[np]=BF.dist[np].min(nc);
                        BF.que0.push(Reverse(S((nc,juwels-matches!(cell,Juwel(id) if !self.get(id)) as i64),(np,nt))));
                        BF.prev[np][nt]=pos;
                    }
                }
            }
        }
    }

    fn get_routes(&self,input:&In,BF:&mut BUF)->Vec<(Vec<usize>,i64,Cell)>{
        // todo
        const C:usize=3;
        let R:i64=70.min(self.HP+0);

        let old=BF.base;
        BF.reset();
        let mut ret=vec![];
        BF.que.push(Reverse(S(BF.base,(self.pos,0))));
        BF.dist[self.pos]=BF.base;
        BF.prev[self.pos][0]=!0;
        let th=BF.base+R;

        while let Some(Reverse(S(cost,(pos,t))))=BF.que.pop(){
            let turn=(self.turn+t)%60;
            let nturn=(turn+1)%60;
            let nt=t+1;
            
            for dd in DX{
                let np=pos+dd;
                let cell=input.grid[np];
                let nc=input.damage[np][nturn]+cost;
                if cell==Goal && self.get(0) || matches!(cell,Juwel(id) if !self.get(id)){
                    if dd==0{
                        continue;
                    }
                    let nc=if cell==Goal{cost}else{nc};
                    let mut route=vec![np];
                    let mut pos=(pos,t);
                    loop{
                        route.push(pos.0);
                        pos=(BF.prev[pos.0][pos.1],pos.1-1);
                        if pos.0==!0{
                            break;
                        }
                    }
                    route.pop();
                    route.reverse();
                    ret.push((route,nc-BF.base,cell));
                    if ret.len()>=C{
                        return ret;
                    }
                }
                else if cell.is_through() && 40>nt{ // todo
                    if old>BF.dist[np] && dd!=0{
                        continue;
                    }
                    BF.dist[np]=old-1;

                    if (BF.dist[np]>nc || dd==0) && th>nc{
                        BF.dist[np]=BF.dist[np].min(nc);
                        BF.que.push(Reverse(S(nc,(np,nt))));
                        BF.prev[np][nt]=pos;
                    }
                }
            }
        }
        
        ret
    }

    fn to_cand(&self,input:&In,id:(usize,usize),route:Vec<usize>,diff:i64)->Option<Cand>{
        let HP=self.HP-diff;
        
        let pos=*route.last().unwrap();
        let key=(self.seen[0]&1==1)|(input.id[pos]==0);

        let cost=input.cost(pos,key);
        if HP<=0 || cost>=HP as f64+0.{ // todo
            return None;
        }
        let juwels=self.juwels+1;

        Some(
            Cand{
                parent:id,
                HP,
                juwels,pos,
                turn:self.turn+route.len(),
                score:score(HP,juwels,key),
                op:route
            }
        )
    }
    
    fn append_cands(&self,input:&In,id:(usize,usize),cands:&mut Vec<Vec<Cand>>,best_score:&mut usize,best:&mut List<usize>,BF:&mut BUF){
        let routes=self.get_routes(input,BF);
        
        for (route,diff,cell) in routes{
            if let Some(cand)=self.to_cand(input,id,route,diff){
                if cell==Goal{
                    if *best_score<cand.juwels{
                        assert!(cand.HP>0);
                        *best_score=cand.juwels;
                        *best=self.hist.append(&cand.op);
                    }
                }
                else{
                    cands[cand.HP as usize].push(cand);
                }
            }
        }
    }
}


#[derive(Clone)]
struct Cand{
    parent:(usize,usize),
    op:Vec<usize>,
    pos:usize,
    turn:usize,
    HP:i64,
    juwels:usize,
    score:f64,
}
impl Cand{
    fn to_node(&self,input:&In,parent:&Node)->Node{
        let mut seen=parent.seen.clone();
        if let Juwel(id)=input.grid[self.pos]{
            seen[id>>3]|=1<<(id&7);
        }

        Node{
            seen,
            hist:parent.hist.append(&self.op),
            pos:self.pos,
            turn:self.turn,
            HP:self.HP,
            juwels:self.juwels,
        }
    }
}


struct Beam{
    nodes:Vec<Vec<Node>>,
    best_score:usize,
    best:List<usize>
}
impl Beam{
    fn new(node:Node)->Beam{
        let mut nodes=vec![vec![];H as usize+1];
        nodes[node.HP as usize].push(node);
        Beam{
            nodes,
            best_score:0,
            best:Nil
        }
    }

    fn enum_cands(&mut self,input:&In,HP:usize,cands:&mut Vec<Vec<Cand>>,BF:&mut BUF){
        for (i,node) in self.nodes[HP].iter().enumerate(){
            node.append_cands(input,(HP,i),cands,&mut self.best_score,&mut self.best,BF);
        }
    }

    fn update<'a,I:Iterator<Item=&'a Cand>>(&mut self,input:&In,HP:usize,it:I){
        // assert!(self.nodes[HP].is_empty());
        for cand in it{
            let (i,j)=cand.parent;
            let node=cand.to_node(input,&self.nodes[i][j]);
            self.nodes[HP].push(node);
        }
    }
}


fn beam_search(input:&In,beam:&mut Beam,HP:usize,TL:f64,BF:&mut BUF)->Option<(List<usize>,usize)>{
    let mut M=50;

    let mut cands=vec![vec![];H as usize+1];
    let mut cnt=vec![0;input.I];

    let mut prev=H as usize;
    let mut time0=get_time();

    for i in (1..=H as usize).rev(){
        if H as usize-1000>i && HP>i && i&15==0 || i==112 || i==80 || i==48 || i==16 || i==8 || i==4 || i==2{
            let time1=get_time();
            if TL<=time1{
                M=70;
            }
            else{
                let mut rate=(prev-i) as f64*(TL-time1)/i as f64/(time1-time0);
                rate=rate.cbrt();
                M=((M as f64*rate) as usize).max(70).min((input.I as f64) as usize);
                // eprintln!("# {M}");
                prev=i;
                time0=time1;
            }
        }
        
        beam.enum_cands(input,i,&mut cands,BF);
        if i==1{
            break;
        }

        cands[i-1].sort_unstable_by_key(|cand|Reverse(O(cand.score)));
        cnt.fill(0);
        let th=1; // todo
        let it=cands[i-1].iter().filter(|cand|cnt[input.id[cand.pos]]<th && {cnt[input.id[cand.pos]]+=1; true}).take(M);
        beam.update(input,i-1,it);
    }

    let best_score=beam.best_score;
    if best_score>0{
        Some((beam.best.clone(),best_score))
    }
    else{
        None
    }
}


fn binary_search(input:&In,beam:&Beam,best_score:&mut usize,best:&mut List<usize>)->usize{
    let mut ng=1;
    let mut ok=H as usize;

    while ok-ng>1{
        let m=ok+ng>>1;
        let node=&beam.nodes[m][0];

        let mut seen:Vec<_>=(0..input.I).map(|i|node.get(i)).collect();
        let (score,route)=greedy(input,node.pos,node.get(0),&mut seen);
        let score=score+node.juwels;
        let route=node.hist.append(&route);
        if isok(input,&route.to_vec()){
            if *best_score<score{
                *best_score=score;
                *best=route;
            }
            ok=m;
        }
        else{
            ng=m;
        }
    }

    ok
}


fn random_search(input:&In,beam:&Beam,ok:usize,TL:f64,best_score:&mut usize,best:&mut List<usize>,BF:&mut BUF){
    'outer: for i in ok..H as usize{
        for node in &beam.nodes[i]{
            if node.get(0){
                node.to_goal(input,best,best_score,BF);
            }
            if get_time()>=TL{
                break 'outer;
            }
        }
    }
}


// 魔法だけ
fn change_nop(input:&In,route:&[usize])->(In,Node){
    // Nopが来たらできるだけ攻撃間隔が短いやつを攻撃する

    let mut fire=0;
    let mut new_input=input.clone();
    let mut seen=vec![false;N2];
    let mut seen_juwels=vec![0;(input.I>>3)+1];
    let mut destroy=vec![false;input.M];

    let mut hist=Nil;
    let mut HP=1500+input.damage[input.start][0];
    let mut turn=0;
    let mut juwels=0;

    let mut prev=!0;
    for &pos in route{
        if input.grid[pos]==Fire && !seen[pos]{
            seen[pos]=true;
            fire+=1;
        }
        if let Juwel(id)=input.grid[pos]{
            let (a,b)=(id>>3,id&7);
            if seen_juwels[a]>>b&1==0{
                juwels+=1;
                seen_juwels[a]|=1<<b;
            }
        }
        if prev==pos{
            if fire>0{
                if let Some(&id)=input.reach[pos].iter().filter(|&i|!destroy[*i]).min_by_key(|&i|input.ienemy[*i].2){
                    destroy[id]=true;
                    let (i0,j0)=from(pos);
                    let (i1,j1,_)=input.ienemy[id];

                    let dir=if i0==i1{
                        if j0>j1{
                            0
                        }
                        else{
                            2
                        }
                    }
                    else if j0==j1{
                        if i0>i1{
                            1
                        }
                        else{
                            3
                        }
                    }
                    else{
                        panic!();
                    };

                    hist=Cons(dir<<10,Rc::new(hist));
                    fire-=1;
                }
                else{
                    hist=Cons(pos,Rc::new(hist));
                }
            }
            else{
                hist=Cons(pos,Rc::new(hist));
            }
        }
        else{
            hist=Cons(pos,Rc::new(hist));
        }
        HP-=input.reach[pos].iter().map(|id|(!destroy[*id] && turn%input.ienemy[*id].2==0) as i64).sum::<i64>()*input.D+1;
        turn+=1;
        prev=pos;
    }

    new_input.recalc(&destroy);

    (new_input,Node{hist,seen:seen_juwels,pos:prev,turn:route.len()-1,HP,juwels})
}


fn solve(input:&In)->Vec<usize>{
    let mut BF=BUF::new();
    let mut beam=Beam::new(Node::new(input));

    let mut best_score=0;
    let mut best=Nil;

    if let Some((res,score))=beam_search(input,&mut beam,H as usize,2.2,&mut BF){
        best_score=score;
        best=res;
    }

    let mut ok=0;
    if best_score==0{
        ok=binary_search(input,&beam,&mut best_score,&mut best);
    }
    else{
        let route=best.to_vec();
        let (input,node)=change_nop(input,&route[..route.len().saturating_sub(100)]);

        let mut beam=Beam::new(node);
        if let Some((res,score))=beam_search(&input,&mut beam,100,2.6,&mut BF){
            if best_score<=score{
                best_score=score;
                best=res;

                eprintln!("score = {}",best_score);
                random_search(&input,&beam,ok,2.8,&mut best_score,&mut best,&mut BF);
                return best.to_vec();
            }
        }
    }

    random_search(input,&beam,ok,2.8,&mut best_score,&mut best,&mut BF);
    eprintln!("score = {}",best_score);

    best.to_vec()
}


fn isok(input:&In,route:&[usize])->bool{
    let mut HP=H;
    for (i,p) in route.iter().cloned().enumerate(){
        if i==0 || i==route.len()-1{
            continue;
        }
        HP-=input.damage[p][i%60];
    }
    HP>0
}


fn simulate(input:&In,route:&[usize]){
    let mut HP=H;
    for (i,p) in route.iter().cloned().enumerate(){
        if i==0 || i==route.len()-1{
            continue;
        }
        HP-=input.damage[p][i%60];
    }
    // assert!(HP>0);
    // eprintln!("HP = {HP}");
}


fn main(){
    get_time();
    let input=In::input();
    eprintln!("I = {}",input.I);
    let ans=solve(&input);

    #[cfg(local)]{
        simulate(&input,&ans);
    }

    let mut prev=ans[0];

    for &next in &ans[1..]{
        if let Some(id)=(0..5).find(|i|DX[*i]==next-prev){
            prev=next;
            println!("{}",DS[id]);
        }
        else{
            println!("F {}",DC[next>>10]);
        }
    }

    eprintln!("time = {:.2}",get_time());
}


///////////////////////////////////


#[allow(unused)]
struct Scanner{
    stack:std::str::SplitAsciiWhitespace<'static>
}
#[allow(unused)]
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_rules! input{
    ($scan:ident, $($rest:tt)*)=>{
        input_inner!{$scan,$($rest)*}
    };
}
 
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_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>()
    };
}

use std::collections::*;
use std::cmp::Reverse;
use std::f64::INFINITY;


#[derive(Clone,Copy,PartialEq,Eq,Debug)]
enum Cell{
    Empty,
    Wall,
    Goal,
    Juwel(usize),
    Fire,
    Enemy
}
use Cell::*;
impl Cell{
    fn new(c:char,at:&mut usize)->Cell{
        match c{
            '.'|'S'=>Empty,
            '#'=>Wall,
            'G'=>Goal,
            'K'=>Juwel(0),
            'J'=>{*at+=1; Juwel(*at)},
            'F'=>Fire,
            'E'=>Enemy,
            _=>panic!(),
        }
    }

    fn is_through(&self)->bool{
        !matches!(*self,Wall|Goal|Enemy)
    }

    fn is_block(&self)->bool{
        matches!(self,Wall|Enemy)
    }
}

const N:usize=60;
const N2:usize=(N+2).pow(2);
const H:i64=1500;


fn get_cost(grid:&[Cell],costs:&[f64],start:usize)->Vec<f64>{
    let mut que=BinaryHeap::new();
    que.push(Reverse(S(0.,start)));
    let mut ret=vec![INFINITY;N2];
    ret[start]=0.;

    while let Some(Reverse(S(cost,pos)))=que.pop(){
        for dd in DD{
            let np=pos+dd;
            if ret[np].is_infinite(){
                let nc=if grid[np].is_through(){
                    cost+costs[np]
                }
                else{
                    continue;
                };

                ret[np]=nc;
                que.push(Reverse(S(nc,np)));
            }
        }
    }

    ret
}


#[derive(Clone)]
struct In{
    M:usize,
    I:usize,
    D:i64,
    grid:Vec<Cell>,
    id:Vec<usize>,
    start:usize,
    key:usize,
    goal:usize,
    cost_key:Vec<f64>,
    cost_goal:Vec<f64>,
    reach:Vec<Vec<usize>>,
    damage:Vec<Vec<i64>>,
    ienemy:Vec<(usize,usize,usize)>
}
impl In{
    fn input()->In{
        let mut scan=Scanner::new();
        input!{
            scan,
            n:usize,
            D:i64,
            h:i64,
            igrid:[Chars;n],
            M:usize,
            ienemy:[(usize,usize,usize);M]
        }

        assert_eq!((n,h),(N,H));
        let mut grid=vec![Wall;N2];
        let mut at=0;
        let mut start=!0;
        let mut key=!0;
        let mut goal=!0;
        
        for i in 1..=N{
            for j in 1..=N{
                let pos=to(i,j);
                let c=igrid[i-1][j-1];
                grid[pos]=Cell::new(c,&mut at);
                if c=='S'{
                    start=pos;
                }
                else if c=='K'{
                    key=pos;
                }
                else if c=='G'{
                    goal=pos;
                }
            }
        }
        assert!(start!=!0 && key!=!0 && goal!=!0);

        let mut enemy=vec![!0;M];
        let mut costf=vec![0.;N2];
        let mut reach=vec![vec![];N2];
        for (id,&(i,j,d)) in ienemy.iter().enumerate(){
            enemy[id]=d;

            let pos=to(i+1,j+1);
            let addf=D as f64/d as f64+1.;
            for dd in DD{
                let mut np=pos+dd;
                while !grid[np].is_block(){
                    costf[np]+=addf;
                    reach[np].push(id);
                    np+=dd;
                }
            }
        }

        let mut damage=vec![vec![0;60];N2];
        for i in 1..=N{
            for j in 1..=N{
                for k in 0..60{
                    let cost=reach[to(i,j)].iter().map(|id|(k%enemy[*id]==0) as i64).sum::<i64>()*D+1;
                    damage[to(i,j)][k]=cost;
                }
            }
        }

        let mut I=0;
        let mut id=vec![!0;N2];
        for i in 1..=N{
            for j in 1..=N{
                if let Juwel(idx)=grid[to(i,j)]{
                    id[to(i,j)]=idx;
                    I+=1;
                }
            }
        }

        In{
            cost_key:get_cost(&grid,&costf,key),
            cost_goal:get_cost(&grid,&costf,goal),
            grid,start,key,goal,
            damage,I,id,reach,M,ienemy,D,
        }
    }

    fn recalc(&mut self,destroy:&[bool]){
        let mut enemy=vec![!0;self.M];
        let mut costf=vec![0.;N2];
        let mut reach=vec![vec![];N2];
        for (id,&(i,j,d)) in self.ienemy.iter().enumerate(){
            if destroy[id]{
                continue;
            }
            enemy[id]=d;

            let pos=to(i+1,j+1);
            let addf=self.D as f64/d as f64+1.;
            for dd in DD{
                let mut np=pos+dd;
                while !self.grid[np].is_block(){
                    costf[np]+=addf;
                    reach[np].push(id);
                    np+=dd;
                }
            }
        }

        let mut damage=vec![vec![0;60];N2];
        for i in 1..=N{
            for j in 1..=N{
                for k in 0..60{
                    let cost=reach[to(i,j)].iter().map(|id|(k%enemy[*id]==0) as i64).sum::<i64>()*self.D+1;
                    damage[to(i,j)][k]=cost;
                }
            }
        }

        let mut I=0;
        let mut id=vec![!0;N2];
        for i in 1..=N{
            for j in 1..=N{
                if let Juwel(idx)=self.grid[to(i,j)]{
                    id[to(i,j)]=idx;
                    I+=1;
                }
            }
        }

        self.cost_key=get_cost(&self.grid,&costf,self.key);
        self.cost_goal=get_cost(&self.grid,&costf,self.goal);
        self.damage=damage;
        self.id=id;
        self.reach=reach;
    }

    fn cost(&self,pos:usize,key:bool)->f64{
        if key{
            self.cost_goal[pos]
        }
        else{
            self.cost_goal[self.key]+self.cost_key[pos]
        }
    }
}


fn from(i:usize)->(usize,usize){
    (i/(N+2)-1,i%(N+2)-1)
}

fn to(i:usize,j:usize)->usize{
    i*(N+2)+j
}

const DD:[usize;4]=[!0,(N+2).wrapping_neg(),1,N+2];
const DX:[usize;5]=[!0,(N+2).wrapping_neg(),1,N+2,0];
const DS:[&'static str;5]=["M L","M U","M R","M D","S"];
const DC:[char;4]=['L','U','R','D'];


#[derive(PartialEq,PartialOrd)]
struct O<T:PartialEq+PartialOrd>(T);
impl<T:PartialEq+PartialOrd> Eq for O<T>{} 
impl<T:PartialEq+PartialOrd> Ord for O<T>{
    fn cmp(&self,a:&O<T>)->std::cmp::Ordering{
        self.0.partial_cmp(&a.0).unwrap()
    }
}

struct S<T:PartialEq+PartialOrd,U>(T,U);
impl<T:PartialEq+PartialOrd,U> PartialEq for S<T,U>{
    fn eq(&self,a:&S<T,U>)->bool{
        self.0.eq(&a.0)
    }
}
impl<T:PartialEq+PartialOrd,U> PartialOrd for S<T,U>{
    fn partial_cmp(&self,a:&S<T,U>)->Option<std::cmp::Ordering>{
        self.0.partial_cmp(&a.0)
    }
}
impl<T:PartialEq+PartialOrd,U> Eq for S<T,U>{}
impl<T:PartialEq+PartialOrd,U> Ord for S<T,U>{
    fn cmp(&self,a:&S<T,U>)->std::cmp::Ordering{
        self.partial_cmp(a).unwrap()
    }
}


use std::rc::Rc;
#[derive(Clone)]
enum List<T>{
    Cons(T,Rc<List<T>>),
    Nil
}
use List::*;
impl<T:Clone> List<T>{
    fn to_vec(&self)->Vec<T>{
        let mut ret=vec![];
        let mut ptr=self.clone();

        while let Cons(v,prev)=ptr{
            ret.push(v.clone());
            ptr=(*prev).clone();
        }

        ret.reverse();
        ret
    }

    fn append(&self,new:&[T])->List<T>{
        let mut ret=self.clone();
        for n in new{
            ret=Cons(n.clone(),Rc::new(ret));
        }
        ret
    }
}


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)*1.5
        }
        #[cfg(not(local))]{
            time-START
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード