結果

問題 No.5006 Hidden Maze
ユーザー rhoo
提出日時 2022-07-01 21:24:57
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 367 ms / 2,000 ms
コード長 5,535 bytes
コンパイル時間 2,907 ms
実行使用メモリ 22,876 KB
スコア 89,108
平均クエリ数 109.92
最終ジャッジ日時 2022-07-01 21:25:09
合計ジャッジ時間 10,382 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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,
    cnt:[[[i32;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,cnt:[[[0;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(&self)->Vec<(usize,usize,usize)>{
        let mut cur=vec![];
        
        let mut edge=[[[0.;4];N];N];
        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{
            for i in 0..N{
                for j in 0..N{
                    for k in 0..4{
                        edge[i][j][k]=self.map[i][j][k]*rnd::nextf();
                    }
                }
            }

            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{
                                que.push((Hoge((1.-edge[y][x][i])*f),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.map[y][x][r]=0.;
                self.map[y+DY[r]][x+DX[r]][r^1]=0.;
            }

            let (y,x,r)=cmds[result as usize];
            if self.map[y][x][r]!=0.{
                self.cnt[y][x][r]+=1;
                self.map[y][x][r]=S*(1.-self.p).powi(self.cnt[y][x][r]) / (S*(1.-self.p).powi(self.cnt[y][x][r]) + (1.-S)*self.p.powi(self.cnt[y][x][r]));
                
                let (ny,nx,nr)=(y+DY[r],x+DX[r],r^1);
                self.cnt[ny][nx][nr]+=1;
                self.map[ny][nx][nr]=self.map[y][x][r];
            }
            
            self.log.push(cmds);
            
            false
        }
    }
}

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

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