#1162614 (Rust) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: rhoo
• 提出日時: 2026-05-02 17:59:22
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 1,398 ms / 2,000 ms
• コード長: 14,560 bytes
• コンパイル時間: 3,816 ms
• コンパイル使用メモリ: 219,240 KB
• 実行使用メモリ: 6,400 KB
• スコア: 2,158,678
• 最終ジャッジ日時: 2026-05-02 18:05:18
• 合計ジャッジ時間: 55,972 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

ファイルパターン	結果
other	AC * 50

コンパイルメッセージ

warning: unused label
   --> src/main.rs:172:9
    |
172 |         'a: for ddn in DD{
    |         ^^
    |
    = note: `#[warn(unused_labels)]` (part of `#[warn(unused)]`) on by default

warning: variable does not need to be mutable
   --> src/main.rs:167:13
    |
167 |         let mut skip=0;
    |             ----^^^^
    |             |
    |             help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` (part of `#[warn(unused)]`) on by default

warning: constant `DX` is never used
   --> src/main.rs:431:7
    |
431 | const DX:[P;8]=[P{i:0,j:!0},P{i:!0,j:!0},P{i:!0,j:0},P{i:!0,j:1},P{i:0,j:1},P{i:1,j:1},P{i:1,j:0},P{i:1,j:!0}];
    |       ^^
    |
    = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: associated items `id`, `from`, `manh`, and `dir` are never used
   --> src/main.rs:447:8
    |
438 | impl P{
    | ------ associated items in this implementation
...
447 |     fn id(self,w:usize)->usize{
    |        ^^
...
451 |     fn from(id:usize,w:usize)->P{
    |        ^^^^
...
455 |     fn manh(self,p:P)->usize{
    |        ^^^^
...
460 |     fn dir(self,p:P)->usize{
    |        ^^^

ソースコード

#![allow(non_snake_case)]



fn main(){
    let state=State::new();
    let initial=Cand{
        act:NULL,
        hash:0,
        score:0,
        rem:0,
        leaf:0,
        active:true,
    };
    let ans=beam_search(state,initial);
    
    let input=get_input();
    assert!(ans.len()<=input.t);
    println!("{}",ans.len());
    for node in &ans{
        let i=node.act.i;
        let j=node.act.j;
        println!("{} {}",i,j);
    }
}



fn beam_search(state:State,initial:Cand)->Vec<Node>{
    let input=get_input();
    let WIDTH=if input.t<=50{
        5
    } else if input.t<=100{
        3
    } else{
        2
    };
    let mut beam=BeamSearch::new(state,initial);
    let mut is=vec![vec![vec![];N];N];
    let mut set=std::collections::HashSet::new();
    
    let mut best_score=0;
    let mut best=vec![];
    
    for turn in 0..input.t{
        if turn!=0{
            let arg=(0..beam.cand.len()).max_by_key(|&i|beam.cand[i].score).unwrap();
            if best_score<beam.cand[arg].score{
                best_score=beam.cand[arg].score;
                best=beam.restore(arg);
            }
            
            for i in 0..N{
                for j in 0..N{
                    is[i][j].clear();
                }
            }
            for i in 0..beam.cand.len(){
                is[beam.cand[i].act].push(i);
            }
            
            let eval=|cand:&Cand|->i64{
                cand.score+(cand.rem.min(input.t-turn)) as i64*200 // todo
            };
            
            for p in iterp(N,N){
                is[p].sort_unstable_by_key(|&i|-eval(&beam.cand[i]));
                set.clear();
                
                let mut cnt=0;
                for &i in &is[p]{
                    if set.insert(beam.cand[i].hash){
                        beam.select(i);
                        cnt+=1;
                        if cnt>=WIDTH{
                            break;
                        }
                    }
                }
            }
        }
        
        beam.run();
        if beam.cand.is_empty(){
            eprintln!("end = {}",turn);
            break;
        }
    }
    
    if !beam.cand.is_empty(){
        let arg=(0..beam.cand.len()).max_by_key(|&i|beam.cand[i].score).unwrap();
        if best_score<beam.cand[arg].score{
            best_score=beam.cand[arg].score;
            best=beam.restore(arg);
        }
    }
    eprintln!("score = {}",best_score);
    
    best
}



const NULL:P=P{i:!0,j:!0};



static_data!{
    get_zob:[[u64;N];N]|{
        let mut zob=[[0;N];N];
        for i in 0..N{
            for j in 0..N{
                zob[i][j]=rnd::next64();
            }
        }
        zob
    }
}



fn expand(state:&mut State,cand:&Cand,leaf:usize,next_cand:&mut Vec<Cand>){
    let mut add_cand=|new:Cand|{
        assert!(new.leaf==leaf);
        assert!(!new.active);
        next_cand.push(new);
    };
    
    let a=&get_input().a;
    let zob=get_zob();
    
    if cand.act==NULL{
        let mut hash=0;
        for p in iterp(N,N){
            hash^=zob[p];
        }
        
        // 最初のマスは自由
        for p in iterp(N,N){
            let new=Cand{
                act:p,
                hash:hash^zob[p],
                score:a[p],
                rem:N*N-1,
                leaf,active:false,
            };
            add_cand(new);
        }
        
        return;
    }
    
    for dd in DD{
        let np=cand.act+dd;
        if !np.in_range(N,N) || state.vis[np]{
            continue;
        }
        
        // rem,hashの計算
        // bfs
        
        state.vis[np]=true;
        
        state.at+=1;
        let mut hash=cand.hash^zob[np];
        let mut rem=cand.rem-1;
        let mut skip=0;
        
        let mut max=0;
        let mut max_hash=0;
        
        'a: for ddn in DD{
            let nnp=np+ddn;
            
            if !nnp.in_range(N,N) || state.vis[nnp] || state.seen[nnp]==state.at{
                continue;
            }
            
            state.que.clear();
            state.que.push_back(nnp);
            state.seen[nnp]=state.at;
            let mut cnt=0;
            let mut new=0;
            
            while let Some(v)=state.que.pop_front(){
                // if cnt>=10{
                //     for ddm in DD{
                //         let nnp=np+ddm;
                //         if nnp.in_range(N,N) && state.vis[nnp] && state.seen[nnp]!=state.at{
                //             skip+=1;
                //             continue 'a;
                //         }
                //     }
                // }
                
                cnt+=1;
                new^=zob[v];
                
                for ddx in DD{
                    let nv=v+ddx;
                    if nv.in_range(N,N) && !state.vis[nv] && state.seen[nv]!=state.at{
                        state.seen[nv]=state.at;
                        state.que.push_back(nv);
                    }
                }
            }
            
            rem-=cnt;
            hash^=new;
            if max<cnt{
                max=cnt;
                max_hash=new;
            }
        }
        
        if skip<=1{
            if skip==0{
                // assert!(rem==0);
                rem=max;
                hash=max_hash;
            }
            
            let new=Cand{
                act:np,
                score:cand.score+a[np],
                rem,hash,
                
                leaf,active:false,
            };
            add_cand(new);
        }
        
        state.vis[np]=false;
    }
}



use std::collections::*;

struct State{
    vis:[[bool;N];N],
    que:VecDeque<P>,
    at:usize,
    seen:[[usize;N];N],
}
impl State{
    fn new()->State{
        State{
            vis:[[false;N];N],
            que:VecDeque::new(),
            at:0,
            seen:[[0;N];N],
        }
    }
    
    fn apply(&mut self,node:&Node){
        self.vis[node.act]=true;
    }
    
    fn revert(&mut self,node:&Node){
        self.vis[node.act]=false;
    }
}



#[derive(Clone)]
struct Cand{
    act:P,
    hash:u64, // 訪れることができるマスのハッシュ
    score:i64,
    rem:usize,
    leaf:usize,
    active:bool,
}
impl Cand{
    fn to_node(&self)->Node{
        Node{
            act:self.act,
        }
    }
}



#[derive(Clone,Copy)]
struct Node{
    act:P,
}



struct BeamSearch{
    state:State,
    trace:Vec<Node>,
    tour:Vec<Node>,
    leaf:Vec<usize>,
    cand:Vec<Cand>,
    next_tour:Vec<Node>,
    next_leaf:Vec<usize>,
    next_cand:Vec<Cand>,
}
impl BeamSearch{
    fn new(state:State,initial:Cand)->Self{
        Self{
            state,
            trace:vec![],
            tour:vec![],
            leaf:vec![0],
            cand:vec![initial],
            next_tour:vec![],
            next_leaf:vec![],
            next_cand:vec![],
        }
    }
    
    fn run(&mut self){
        let turn=self.trace.len();
        self.trace.push(self.cand.last().unwrap().to_node());
        
        if turn==0{
            expand(&mut self.state,&self.cand[0],0,&mut self.next_cand);
            std::mem::swap(&mut self.cand,&mut self.next_cand);
            return;
        }
        
        self.next_tour.clear();
        self.next_leaf.clear();
        self.next_cand.clear();
        
        let mut f=0;
        let mut li=self.leaf.len()-1;
        
        for cand in self.cand.iter().rev().filter(|cand|cand.active){
            let lca=self.leaf[cand.leaf..li].iter().rev()
                .fold((0,self.leaf[li]),|(a,b),&x|(a.max(b-x),x)).0;
            self.trace[turn-lca..turn+f].iter().rev().for_each(|node|self.state.revert(node));
            f=1;
            self.next_tour.extend_from_slice(&self.trace[turn-lca..]);
            
            self.trace[turn]=cand.to_node();
            let mut prog=0;
            for w in self.leaf[cand.leaf..=li].windows(2){
                let rank=w[1]-w[0];
                if prog<rank{
                    self.trace[turn-rank..turn-prog].copy_from_slice(&self.tour[w[0]..w[1]-prog]);
                    prog=rank;
                }
            }
            
            self.trace[turn-lca..].iter().for_each(|node|self.state.apply(node));
            expand(&mut self.state,cand,self.next_leaf.len(),&mut self.next_cand);
            self.next_leaf.push(self.next_tour.len());
            li=cand.leaf;
        }
        
        std::mem::swap(&mut self.tour,&mut self.next_tour);
        std::mem::swap(&mut self.leaf,&mut self.next_leaf);
        std::mem::swap(&mut self.cand,&mut self.next_cand);
    }
    
    fn restore(&self,idx:usize)->Vec<Node>{
        let mut ret=self.trace[1..].to_vec();
        
        let len=ret.len();
        let mut prog=0;
        for w in self.leaf[self.cand[idx].leaf..].windows(2){
            let rank=w[1]-w[0];
            if prog<rank{
                ret[len-rank..len-prog].copy_from_slice(&self.tour[w[0]..w[1]-prog]);
                prog=rank;
            }
        }
        
        ret.push(self.cand[idx].to_node());
        ret
    }
    
    fn select(&mut self,i:usize){
        self.cand[i].active=true;
    }
}



const N:usize=20;



struct Input{
    t:usize,
    a:[[i64;N];N],
}


static_data!{
    get_input:Input|{
        proconio::input!{
            _n:usize,
            t:usize,
            a_:[[i64;N];N],
        }
        let mut a=[[0;N];N];
        for i in 0..N{
            for j in 0..N{
                a[i][j]=a_[i][j];
            }
        }
        Input{t,a}
    }
}



#[macro_export]
macro_rules! static_data{
    ($a:ident:$t:ty|$e:expr)=>{
        fn $a()->&'static $t{
            use std::sync::OnceLock;
            static D:OnceLock<$t>=OnceLock::new();
            D.get_or_init(||$e)
        }
    }
}



// LURD
const DD:[P;4]=[P{i:0,j:!0},P{i:!0,j:0},P{i:0,j:1},P{i:1,j:0}];
const DX:[P;8]=[P{i:0,j:!0},P{i:!0,j:!0},P{i:!0,j:0},P{i:!0,j:1},P{i:0,j:1},P{i:1,j:1},P{i:1,j:0},P{i:1,j:!0}];

#[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash,Default)]
struct P{
    i:usize,
    j:usize,
}
impl P{
    fn new(i:usize,j:usize)->P{
        P{i,j}
    }
    
    fn in_range(self,h:usize,w:usize)->bool{
        self.i<h && self.j<w
    }
    
    fn id(self,w:usize)->usize{
        self.i*w+self.j
    }
    
    fn from(id:usize,w:usize)->P{
        P::new(id/w,id%w)
    }
    
    fn manh(self,p:P)->usize{
        let abs_diff=|a,b|(a as i64-b as i64).abs() as usize;
        abs_diff(self.i,p.i)+abs_diff(self.j,p.j)
    }
    
    fn dir(self,p:P)->usize{
        if self.i==p.i{
            if self.j-1==p.j{
                0
            } else{
                assert!(self.j+1==p.j);
                2
            }
        } else{
            if self.i-1==p.i{
                1
            } else{
                assert!(self.i+1==p.i);
                3
            }
        }
    }
}
impl std::fmt::Debug for P{
    fn fmt(&self,f:&mut std::fmt::Formatter)->std::fmt::Result{
        write!(f,"({}, {})",self.i,self.j)
    }
}
impl std::ops::Add for P{
    type Output=P;
    fn add(self,a:P)->P{
        P{
            i:self.i+a.i,
            j:self.j+a.j,
        }
    }
}
impl std::ops::Sub for P{
    type Output=P;
    fn sub(self,a:P)->P{
        P{
            i:self.i-a.i,
            j:self.j-a.j,
        }
    }
}
impl std::ops::Mul<usize> for P{
    type Output=P;
    fn mul(self,a:usize)->P{
        P{
            i:self.i*a,
            j:self.j*a,
        }
    }
}
impl std::ops::Div<usize> for P{
    type Output=P;
    fn div(self,a:usize)->P{
        P{
            i:self.i/a,
            j:self.j/a,
        }
    }
}
impl std::ops::Neg for P{
    type Output=P;
    fn neg(self)->P{
        P{
            i:self.i.wrapping_neg(),
            j:self.j.wrapping_neg(),
        }
    }
}


macro_rules! impl_p_ops{
    ($t:ty,$assign_trait:ident,$assign_func:ident,$op:tt)=>{
        impl std::ops::$assign_trait<$t> for P{
            fn $assign_func(&mut self,a:$t){
                *self=*self $ op a;
            }
        }
    }
}
impl_p_ops!(P,AddAssign,add_assign,+);
impl_p_ops!(P,SubAssign,sub_assign,-);
impl_p_ops!(usize,MulAssign,mul_assign,*);
impl_p_ops!(usize,DivAssign,div_assign,/);


macro_rules! impl_p_index{
    ($t:ty)=>{
        impl<T:std::ops::Index<usize>> std::ops::Index<P> for $t{
            type Output=T::Output;
            fn index(&self,idx:P)->&T::Output{
                &self[idx.i][idx.j]
            }
        }
        impl<T:std::ops::IndexMut<usize>> std::ops::IndexMut<P> for $t{
            fn index_mut(&mut self,idx:P)->&mut T::Output{
                &mut self[idx.i][idx.j]
            }
        }
    }
}
impl_p_index!([T]);
impl_p_index!(Vec<T>);


fn iterp(h:usize,w:usize)->impl Iterator<Item=P>{
    (0..h).map(move|i|(0..w).map(move|j|P::new(i,j))).flatten()
}



#[allow(unused)]
mod rnd{
    static mut X2:u32=12345;
    static mut X3:u32=0xcafef00d;
    static mut C_X1:u64=0xd15ea5e5<<32|23456;
    
    pub fn set_seed(seed:u64){
        unsafe{
            C_X1^=seed as u64;
        }
    }
    
    pub fn next()->u32{
        unsafe{
            let x=X3 as u64*3487286589;
            let ret=(X3^X2)+(C_X1 as u32^(x>>32) as u32);
            X3=X2;
            X2=C_X1 as u32;
            C_X1=x+(C_X1>>32);
            ret
        }
    }
    
    pub fn next64()->u64{
        (next() as u64)<<32|next() as u64
    }
    
    pub fn nextf()->f64{
        f64::from_bits(0x3ff0000000000000|(next() as u64)<<20)-1.
    }
    
    pub fn get(n:usize)->usize{
        assert!(0<n && n<=u32::MAX as usize);
        next() as usize*n>>32
    }
    
    pub fn range(a:usize,b:usize)->usize{
        assert!(a<b);
        get(b-a)+a
    }
    
    pub fn range_skip(a:usize,b:usize,skip:usize)->usize{
        assert!(a<=skip && skip<b);
        let n=range(a,b-1);
        n+(skip<=n) as usize
    }
    
    pub fn rangei(a:i64,b:i64)->i64{
        assert!(a<b);
        get((b-a) as usize) as i64+a
    }
    
    pub fn shuffle<T>(a:&mut [T]){
        for i in (1..a.len()).rev(){
            a.swap(i,get(i+1));
        }
    }
    
    pub fn shuffle_iter<T:Copy>(a:&mut [T])->impl Iterator<Item=T>{
        (0..a.len()).rev().map(|i|{
            a.swap(i,get(i+1));
            a[i]
        })
    }
}


#[allow(unused)]
trait RandomChoice{
    type Output;
    fn choice(&self)->&Self::Output;
}
impl<T> RandomChoice for [T]{
    type Output=T;
    fn choice(&self)->&T{
        &self[rnd::get(self.len())]
    }
}