結果

問題 No.5006 Hidden Maze
ユーザー rhoo
提出日時 2022-07-02 11:24:30
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 91 ms / 2,000 ms
コード長 6,010 bytes
コンパイル時間 7,818 ms
実行使用メモリ 22,868 KB
スコア 91,333
平均クエリ数 87.67
最終ジャッジ日時 2022-07-02 11:24:51
合計ジャッジ時間 18,071 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused)]
mod rnd {
    static mut S:usize=88172645463325252;
    #[inline]
    pub fn next()->usize{
        unsafe{
            S=S^S<<7;
            S=S^S>>9;
            S
        }
    }

    #[inline]
    pub fn nextf()->f64{
        (next()&4294967295) as f64/4294967296.
    }
}


#[allow(unused)]
struct Scanner<'a>{
    stack:std::str::SplitAsciiWhitespace<'a>
}
#[allow(unused)]
impl<'a> Scanner<'a>{
    #[inline]
    fn new()->Self{
        Self{stack:"".split_ascii_whitespace()}
    }

    #[inline]
    fn read<T:std::str::FromStr>(&mut self)->T{
        loop{
            if let Some(v)=self.stack.next(){
                return v.parse::<T>().unwrap_or_else(|_|panic!("parse error"));
            }

            let mut tmp=String::new();
            std::io::stdin().read_line(&mut tmp).unwrap();
            assert!(!tmp.is_empty());
            self.stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace();
        }
    }
}


#[derive(PartialEq, PartialOrd)]
struct Hoge<T>(T);
impl<T:PartialEq> Eq for Hoge<T>{}

impl<T:PartialOrd> Ord for Hoge<T>{
    fn cmp(&self, other:&Self)->std::cmp::Ordering{
        self.0.partial_cmp(&other.0).unwrap()
    }
}


const N:usize=20;
const S:f64=0.19;


const DY:[usize;4]=[1,!0,0,0];
const DX:[usize;4]=[0,0,1,!0];
const DC:[char;4]=['D','U','R','L'];


struct Solver{
    p:f64,
    aru:[[[f64;4];N];N],
    nai:[[[f64;4];N];N],
    map:[[[f64;4];N];N],
    log:Vec<Vec<(usize,usize,usize)>> // y,x,r
}
impl Solver{
    #[inline]
    fn new(scan:&mut Scanner)->Solver{
        let h=scan.read();
        let w=scan.read();
        assert_eq!((h,w),(N,N));

        let p:usize=scan.read();
        let p=p as f64*0.01;

        Solver{
            p,
            aru:[[[S;4];N];N],
            nai:[[[1.-S;4];N];N],
            map:[[[S;4];N];N],
            log:vec![]
        }
    }

    #[inline]
    fn isok(&self,seen:&[[[usize;4];N];N],at:usize)->bool{
        'outer: for l in &self.log{
            for &(y,x,r) in l{
                if seen[y][x][r]!=at && self.map[y][x][r]!=0.{
                    continue 'outer;
                }
            }
            return false;
        }
        true
    }

    #[inline]
    fn next_cmds(&mut self)->Vec<(usize,usize,usize)>{
        let mut cur=vec![];
        
        let mut seen=[[0;N];N];
        let mut prev=[[!0;N];N];

        let mut at=0;
        let mut que=std::collections::BinaryHeap::new();

        let mut tmp=[[[0;4];N];N];

        let ret=loop{
            at+=1;
            que.clear();
            que.push((Hoge(1.),0,!0,(0,0)));

            while let Some((Hoge(f),_,r,(y,x)))=que.pop(){
                if seen[y][x]!=at{
                    seen[y][x]=at;
                    prev[y][x]=r;

                    if (y,x)==(N-1,N-1){
                        break;
                    }
                    else{
                        for (i,(&dy,&dx)) in DY.iter().zip(DX.iter()).enumerate(){
                            let ny=y+dy;
                            let nx=x+dx;
                            if ny<N && nx<N && seen[ny][nx]!=at{
                                let next=((1.-self.map[y][x][i]*rnd::nextf())*f-0.001*(y as f64-x as f64).abs()).max(0.);
                                que.push((Hoge(next),rnd::next(),i,(ny,nx)));
                            }
                        }
                    }
                }
            }

            cur.clear();
            let mut pos=(N-1,N-1);
            while{
                let r=prev[pos.0][pos.1];

                if r==!0{
                    false
                }
                else{
                    tmp[pos.0][pos.1][r^1]=at;
                    pos.0+=DY[r^1];
                    pos.1+=DX[r^1];
                    cur.push((pos.0,pos.1,r));
                    tmp[pos.0][pos.1][r]=at;
                    
                    true
                }
            }{}

            if self.isok(&tmp,at){
                cur.reverse();
                break cur;
            }
        };

        assert!(!ret.is_empty());

        ret
    }

    #[inline]
    fn run_cmds(&mut self,scan:&mut Scanner,cmds:Vec<(usize,usize,usize)>)->bool{
        for (_,_,r) in &cmds{
            print!("{}",DC[*r]);
        }
        println!();

        let result:i64=scan.read();
        if result==-1{
            true
        }
        else{
            for i in 0..result{
                let (y,x,r)=cmds[i as usize];
                self.aru[y][x][r]=0.;
                self.aru[y+DY[r]][x+DX[r]][r^1]=0.;
            }
            let (y,x,r)=cmds[result as usize];
            let (ny,nx,nr)=(y+DY[r],x+DX[r],r^1);
            self.aru[y][x][r]*=1.-self.p;
            self.aru[ny][nx][nr]=self.aru[y][x][r];
            self.nai[y][x][r]*=self.p;
            self.nai[ny][nx][nr]=self.nai[y][x][r];

            let mut sum=1.;
            for &(y,x,r) in &cmds{
                let aru=self.aru[y][x][r];
                let nai=self.nai[y][x][r];
                self.map[y][x][r]=aru/(aru+nai);
                sum*=1.-self.map[y][x][r];
                self.map[y+DY[r]][x+DX[r]][r^1]=self.map[y][x][r];
            }

            for &(y,x,r) in &cmds{
                self.nai[y][x][r]*=1.-sum/(1.-self.map[y][x][r]);
            }
            for &(y,x,r) in &cmds{
                let aru=self.aru[y][x][r];
                let nai=self.nai[y][x][r];
                self.map[y][x][r]=aru/(aru+nai);
                sum*=1.-self.map[y][x][r];
                self.map[y+DY[r]][x+DX[r]][r^1]=self.map[y][x][r];
            }

            self.log.push(cmds);
            
            false
        }
    }
}

fn main(){
    let mut scan=Scanner::new();
    let mut solver=Solver::new(&mut scan);
    
    let mut score=/*square*/1001;
    loop{
        score-=1;
        if score==0{break;}
        let next_cmds=solver.next_cmds();
        if solver.run_cmds(&mut scan,next_cmds){
            break;
        }
    }

    eprintln!("{:?}",score);
}
0